Hierarchies of Reward Machines
Authors: Daniel Furelos-Blanco
Mark Law
Anders Jonsson
Krysia Broda
Alessandra Russo
Venue: Submitted to ICLR 2023 (2023)
Keywords: Hierarchical Reinforcement Learning
Reward Machines

Abstract: Reward machines (RMs) are a recent formalism for representing the reward function of a reinforcement learning task through a finite-state machine whose edges encode landmarks of the task using high-level events. The structure of RMs enables the decomposition of a task into simpler and independently solvable subtasks that help tackle long-horizon and/or sparse reward tasks. We propose a formalism for further abstracting the subtask structure by endowing an RM with the ability to call other RMs, thus composing a hierarchy of RMs (HRM). We exploit HRMs by treating each call to an RM as an independently solvable subtask using the options framework, and describe a curriculum-based method to learn HRMs from traces observed by the agent. Our experiments reveal that exploiting a handcrafted HRM leads to faster convergence than with a flat HRM, and that learning an HRM remains feasible in cases where its equivalent flat representation is not.

Under review as a conference paper at ICLR 2023
HIERARCHIES OF REWARD MACHINES
Anonymous authors
Paper under double-blind review
ABSTRACT
Reward machines (RMs) are recent formalism for representing the reward fune- tion of a reinforcement learning task through a finite-state machine whose edges encode landmarks of the task using high-level events. The structure of RMs en- ables the decomposition of task into simpler and independently solvable subtasks that help tackle long-horizon and/or sparse reward tasks. We propose a formalism for further abstracting the subtask structure by endowing an RM with the ability to call other RMs,, thus composing a hierarchy of RMs (HRM). We exploit HRMs by treating each call to an RM as an independently solvable subtask using the options framework, and describe a curriculum-base method to learn HRMs from traces observed by the agent. Our experiments reveal that exploiting a handcrafted HRM leads to faster convergence than with a flat HRM, and that learning an HRM is feasible in cases where its equivalent flat representation is not.
INTRODUCTION
More than a decade ago, Dietterich et al. (2008) argued for the need to "learn at multiple time scales simultaneously, and with a rich sfructure of events and durations". Finite-state machines (FSMs) are a simple yet powerful formalism for abstractly representing temporal tasks in a structured manner. One of the most prominent types of FSMs used in reinforcement learning (RL; /Sutton & Barto, 2018) are reward machines (RMs; Toro Icarte et al. 2018 2022), where each edge is labeled with (i) formula over set of high-level events that capture task's subgoal, and (ii) reward for satisfying the formula. Hence, RMs fulfill the need for structuring events and durations. Hierarchical reinforcement learning (HRL: Barto & Mahadevan] 2003) frameworks, such options (Sutton al., 1999). have been applied over R.Ms to learn policies at two levels of abstraction: (i) select a formula (i.e.. subgoal) from a given RM state to complete the overall task, and (ii) select an action to satisfy the chosen formula (Toro Icarte et al.) 2018, Furelos-Blamm learning at multiple scales simultaneously. The subtask decomposition powered by HRL eases the handling of long-horizon and sparse reward tasks. Besides, RMs can act as an external memory in partially observable tasks by keeping track of the subgoals achieved so far and those to be achieved.
et al. 202T). Thus, RMs also allow
In this work, we make the following contributions:
1. Enhance the abstraction power of RMs by defining hierarchies of RMs (HRMs), where con- stituent RMs can call other RMs (Section 3). We prove that any HRM can be transformed into an equivalent flat HRM that behaves exactly like the original RMs. We show that under certain conditions, the equivalent flat HRM can have exponentially more states and edges.
2. Propose an HRL algorithm to explois HRMs by treating each call as subtask (Section 4 Learning policies in HRMs further fulfills the desiderata posed by Dietterich et al. since (i) there is an arbitrary number of time scales to learn across (not only two), and (ii) there is a richer range of increasingly abstract events and durations. Besides, hierarchies enable modularity and, hence, the reusability of the RMs and policies. Empirically, show that leveraging a handcrafted HRM enables faster convergence than an equivalent flat HRM.
3. Introduce a curriculum-bar based method for learning HRMs from traces given a set of hierar- chically composable tasks (Section 5). In line with the theory (Contribution D. our exper- iments reveal that decomposing an RM into several is crucial to make its learning feasible (i.e., the flat HRM cannot be efficiently learned from scratch) since (i) the constituent RMs are simpler (i.c.. they have fewer states and edges), and (ii) previously learned RMs can be used to efficiently explore the environment in the search for traces in more complex tasks.

---

Under review as a conference paper at ICLR 2023
2 BACKGROUND
Given finite set X, we use ( denote the probability simplex over X, X' to denote (possibly empty) sequences of elements from X, and X+ to denote non-empty sequences. We also use I and T to denote the truth values false and true, respectively. 1 [A] is the indicator function of event A.
We represent RL tasks as episodic labeled Markov decision processes (MDDs..Xuerall al. 2020), each consisting of set of states S, set of actions A, transition function p : : x A (S)) reward function r : (S x A)+ x S + R. a discount factor 7 E [0. 1), a finite set of propositions P representing high-level events, a labeling function 1 S + 2 mapping states to proposition subsets called labels, and a termination function T : (S x AA)* x S + (1, T} X {1, T.. Hence the transition function p is Markovian, but the reward function I' and termination function 7 are not. Given a history h4 (Su. ag....,.i) St) E (S x AA)' x S, a label trace (or trace, for short) d = (I66))..... {(x)) E (2*)+ assigns labels to all states h4. We assume (Ax, 84) captures all relevant information about h4; thus, the reward and transition information can be written r r(h,, at, 8t-1) = r(h++1) = r r(Ac+1, $1+1) and rhtt) = T(t,, st), respectively. We aim to find a policy π : (2**+ x - A. mapping from traces-states to actions, that maximizes the expected cumulative discounted reward (or return) Rs = 18 IER== " "r(A++,, SK+1)], where n is the last episode's step.
At time L, the trace is X₂ E (2P)+, and the agent observes a tuple 8, = (s,, " +8), where 8, E is the state and (s] ) whether or not the history (t) is terminal or a goal, respectively. If the history is non-terminal, the agent runs action at E A, and the environment transitions state 8t+1 p(-1s1, at). The agent then extends the trace as A441 = d @ ((++1), receives reward rt+1 = r r()+11,844)) and observes new tuple 8e+1. A trace de is goal trace if (sf st) (T, T), dead-end trace if (() = LT, and an incomplete trace if sf = 1. We assume that the reward is (Ae+1, [T(+++1 81+1) (T. i.e. for goal histories and 0 otherwise.
T(,,, st) is the termination information, with 8 and 2e indicating
A (simple) reward machine (RM: Toro Icarte et al. 2018 2022) is a tuple (2, P, s,, ur,u,, 2 ) where Ut is a finite set of states; P is a finite set propositions: o x 2 - DNFp is a state transition function such that sol,, u') denotes the disjunctive normal form (DNF) formula over P to be satisfied to transition from u to u²: r x - IR is reward transition function such that r(u, v') is the reward for transitioning from to u'; u E lI is an initial state; ZIA C u is set of accepting states denoting the task's goal achievement; and 2 C U is a set of rejecting states denoting the unfeasibility of achieving the goal. Ideally, RM states should capture traces, such that (i) pairs (u, s) of an RM state and an MDP state are sufficient to predict the future, and (ii) the reward r(u, x²) matches the underlying MDP's reward. The state transition function is deterministic, i.c. at most one formula from each state is satisfied. To verify if a formula is satisfied by a label L C P, L is used truth assignment where propositions in L are true, and false otherwise (e.g., {a} F a A -b).
Options (Sutton et af. 1999) address temporal abstraction in RL. Given an episodic labeled MDP, (Z... Tw, B_), where I_ C S is the option's 's initiation set, Th S - A is
an option is tuple the option's 's policy, and B. : S + [o, 1] is the option's 's termination condition. An option is available in S if Iyj selects actions according Tw. and terminates in S with probability (s).
3 FORMALIZATION OF HIERARCHIES OF REWARD MACHINES
We here introduce our formalism for hierarchically composing reward machines, and propose the TRAFTWORLE domain (cf. Figure la to illustrate it. In this domain, the agent (A) can move forward or rotate 90", staying put if it moves towards wall. Locations are labeled with propositions from P = (0,m
4, $ (**) in the left corner). Table lists tasks that consist of observing a sequence of propositions, where the reward is 1 if the sequence is observed and 0 otherwise. These tasks are based on those by Andreas et al. (0117) and Toro Iearte et al. (2018), but they can be defined in terms of each other.
W 2t A... The agent observes propositions that it steps on (e.g.,
Reward machines (RMs) are the building blocks of our formalism. To constitute hierarchy of RMs, we need to endow RMs with the ability to call each other. We redefine the state transition function sp 2 x U x M + DNFp, where M is a set of RMs. The expression sp(u, u' .M) denotes the disjunctive normal form (DNF) formula over P that must be satisfied to transition from E l u' U by calling RM M M. We refer to the formulas y(u, u', M) contexts
2

---

Under review as a conference paper at ICLR 2023
%
M4
M2
+
MT
25
M
1/
+
M1
MT
%
Mr
4G
(root)
(a)
(b)
(c)
Figure 1: A CRAFTWORLD grid (a), an HRM for BoOk (b), and an equivalent flat HRM (c). An edge from state to u' of an RM Mj is of the form Mj pi(u, u', Mj). double circled states are accepting states, and loop transitions are omitted. Calls to the leaf RM MT are omitted (c).
Table I: List of CRAFTWORLD tasks. Descriptions "x ; y" express sequential order (observe/do x then y), and descriptions "x & y" express that and y can be observed/done in any order.
Tisk
Description
Description
Task
Description
BATTER
(#f & # A
QUILL
& #
BOORQUiLL MILKB.
Book & QUILL
BUCKET
8:
SUGAR
MILKB.SUGAR SUGAR
MILK BUCKET & SUGAR
COMPASS
LEATHER);
BATTER MILKB. SUGAAR
LEATHER
W:A
MAP
(PAPER COMPASS): ;
PAPER
7:
MILKBUCKET
BUCKET:
since they represent conditions under which calls are made. As we will see later, contexts help preserve determinism and must be satisfied to start call (a necessary but not sufficient condition). The hierarchies we consider contain an RM MT called the leaf RM, which solely consists of an accepting state (i.e., = u4 = {u4 }), and immediately returns control to the RM that calls it.
Definition 1. A hierarchy of reward machines (HRR) is tuple H = (M, My, P), where M = (Mo.... Mn U [MT} is a of m RMs and the leaf RM MT. M, E M \ {MT} is the root RM. and P is finite set of propositions used by all constituent RMs.
We make the following assumptions: (i) HRMs do not have circular dependencies (i.e., an RM cannot be called back from itself, including recursion), (ii) rejecting states are global (i.e., cause the root task to fail), (iii) accepting and rejecting states do not have transitions to other states, and (iv) the reward function of the root corresponds to the reward obtained in the underlying MDP. Given assumption (i), each RM M, has a height h4, which corresponds to the maximum number of nested calls needed to reach the leaf. Formally, if T, then h; = 0: otherwise, h; + max, hy. where j ranges over all RMs called by M; (i.e., there exists (u, v) E U4 x U; such that (u, v, M,) * L).
Figure 1b shows BOOK's HRM, whose root has height 2. The PAPER and LEATHER RMs, which have height and consist of observing a two-proposition sequence, can be run in any order followed by observing 4r. The context - in the call to M1 preserves determinism, detailed later.
In the following paragraphs, we describe how an HRM processes label trace. To indicate where the agent is in an HRM, we define the notion of hierarchy states.
Definition 2. Given an HRM H (M, M,, P), hierarchy state is tuple (M, u. T, where M, E M is an RM, u. E U4 is a state, & E DNF-p is an accumulated context, and I' is call stack. Definition 3. Given HRM H (M, Mr, P).
call stack I contains tuples (u, u, Mi, Mj, Φ, $) each denoting a call where u E 24; is the state from which the call is made; v E U4 is the next state in the calling RM M, E M after reaching an accepting state of the called RM Mj E M; Φ DNFp are the disjuncts of (u, v, M,) satisfied by a label; and &o DNFp is the accumulated context.
Call stacks determine where to resume the execution. Each RM appears in the stack at most once since, by assumption, HRMs have no circular dependencies. We use I' @ (u, M,, M,, o, Q) to denote a stack recursively defined by a stack I' and top element (u, v, M,, My, o. 4). where the accumulated context & is the condition under which call from state u is made. The initial hierarchy state of an HRM И = M, P) is (M, u., T, D): we are in the initial state of the root, there is no accumulated context, and the stack is empty.
3

---

Under review as a conference paper at ICLR 2023
At the beginning of this section, mention that satisfying the context of call is a necessary but not sufficient condition to start the call. We now introduce a sufficient condition, called exit condition. Definition 4. Given an HRM H = (M, M,, P) and a hierarchy state (M,, 2 I'), the exit condi- rion fi, E DNFp is the formula that must be satisfied to leave that hierarchy state. Formally,
i; otherwise,
V d=pi(u.v Sj,ug. (NF( of UEL, EM
where DNF( A Φ) is A Φ in DNF. The formula is & if M, MT since it always returns control once called. Otherwise, the formula recursively defined as the disjunction of the exit conditions from the initial state of the called RM. For instance, the exit condition for the initial hierarchy state Figure lb is
We now have everything needed to define the hierarchical transition function 8н, which maps a hierarchy state (M,, u, Φ r) into another given a label C. There are three cases:
1. If u is an accepting state of M, and the stack I is non-empty, pop the top element of I and return control to the previous RM, recursively applying бн in case several accepting states are reached simultancously. Formally, the next hierarchy state is 8н ((M,, n', T, ;, 1) if u E 24,2. || > O, where I = 1 @ (-, u', MMg.M,, ,), 1 denotes label that cannot satisfy any formula, and denotes something unimportant for the case.
2. If L satisfies the context of call and the exit condition from the initial state of the called RM, push the call onto the stack and recursively apply δн until M- is reached. Formally, the next hierarchy state is 8 ((M)) uf, Φ', I' @ (u, u', M,, Mj, o, 4)) if L | Eg. 4* where ø = (u, u', (C) and &' = DNF(O A Φ). Here, (CC denotes the disjuncts of DNF formula i DNFp satisfied by L.
3. If none of the previous conditions holds, the hierarchy state remains unchanged.
The state transition functions & of the RMs must be such that 8y is deterministic, i.e. label cannot simultaneously satisfy the contexts and exit conditions associated with two triplets (u, v, M.) and (u, u', M2) such that either (i) 0 o' and i + j. (ii) # v'. Contexts help enforce determinism by making formulas mutually exclusive. For instance, if the call to Mi from the initial state of Mo in Figure [b had context T instead of -W, then Mj and M2 could be both started if { } was observed, thus making the HRM non-deterministic. Finally, we introduce hierarchy traversals, which determine how a label trace processed by an HRM using őn.
Definition 5. Given a label trace À = (Co....,C.)) hierarchy traversal H()) = (vo. U1... (a41) is a unique sequence of hierarchy states such that (i) vo (ii) (2;, f.) = fi+1 for i O,..., An HRM H accepts À if Un+1 (M,, T, (] and u E U.A (i.e., an accepting state of the root is reached). Analogously, H rejects if un+1 = (Ms, .. and E t for any l E [0, - 1] (i.e., rejecting state in the HRM is reached).
(M,, u., T, [). and
Example 1. The HRM in Figure 1b accepts label trace À ((7), (m)) 0.
since 1)) (Mo. up T, D),
(M),
the traversal is (A)
((Mo, "g: T,), (M1, w1. T, Kuy u Mo. M,
(Mo, up: T, [)), (M2, uh, T, [(ug unj Mo, M2, T, T)), (Mo, ug: T, D), (Mo, ug T. T. The step-
by-step application of the hierarchical transition function dh is shown in Appendix A
The behavior of an HRM H can be reproduced by an equivalent flat HRM H: that is, (i) the root of Il has height I and, (ii) H accepts a trace iff H accepts it, rejects trace iff H rejects it, and neither accepts nor rejects a trace iff H does not accept nor reject it. Flat HRMs thus capture the original RM definition. Figure Ic shows flat HRM for the BOOK task. We formally define equivalence and prove the equivalence theorem below by construction in Appendix [.I
Theorem 1. Given HRM H. there exists equivalent flat HRM H.
Given the construction used in Theorem I we show that the number of states and edges of the resulting flat HRM can be exponential in the height of the root (see Theorem 2 We prove this result in Appendix B.2 through an instance of a general HRM parametrization where the constituent RMs highly reused, hence illustrating the convenience of HRMs to succinetly compose existing knowledge. In line with the theory, learning a non-flat HRM can take few seconds, whereas learning equivalent flat HRM is often unfeasible (see Section
4

---

Under review as a conference paper at ICLR 2023
Theorem 2. Let = M,, be an HRM and let h, be the height of its root M,. The number of states and edges in an equivalent flat HRM H can be exponential in hy-
4 POLICY LEARNING IN HIERARCHIES OF REWARD MACHINES
In what follows, we explain how to exploit the temporal structure of an HRM H = (M, M, P) using two types of options. We describe (i) how to learn the policies of these options, (ii) when these options terminate, and (iii) an option selection algorithm that ensures the currently running options and the current hierarchy state are aligned. We discuss implementation details in Appendix C
Types. Given an RM M, E M, a state u E U4 and a context +, an option wa: is derived for each 1,u, non-false disjunct & of each transition (r u. My where v E U4 and M, E M. An option is either (i a formula option if attempts to reach a label that satisfies & A 4 through primitive actions, whereas a call option aims to reach an accepting state of the called RM M, under context & A $ by invoking other options.
T (i.e., MT is called), or (ii) call option otherwise. A formula option
Policies. Policies are <-greddy during training, and greedy during evaluation. A formula option's 's policy derived from a Q-function (sn a; (ana) approximated by deep Q-network (DQN; Mnih et al. 2015) with parameters Oere, which outputs the Q-value of each action given an MDP state. We store all options' experiences (st, a, s(+1) in a single replay buffer D, thus performing intra-option learning (Sutton et al. 1998). The Q-learning update uses the following loss function:
(rane((tei) + max 4on (6400 d'; ) - 90nn a: 1 Oere)) }
E ((
(1)
where ran (8 ([)++(+)) F A T). i.e. the reward is if Φ A t is satisfied and 0 otherwise; the term Psr (S a'; 0% )r is O when 6 A 4 is satisfied or a dead-end is reached (i.e., s T and s = 1); and 05 are the parameters of a fixed target network.
A call option's 's policy is induced by a Q-function q:(8, u, t; (Mj, Ø); 0:) associated with the called RM Mj and approximated by a DQN with parameters O, that outputs the Q-value of each call in the RM given an MDP state, an RM state and a context. We store experiences (st, w St+k) in replay buffer D. associated with M1, and perform SMDP Q-learning using the following loss:
E (o 1e.0 W)DD; (1- 2 max q: (8 ,/, (My, (i u, D (M, 0): jo
(1+
where le is the number of steps between s; and st+k; r the sum of discounted rewards during this time; u' and o' are the RM state and context after running the option; Mj and ø correspond to an outgoing transition from u', i.e. ø' E (u' Mj and 0,- are the parameters of fixed target network. The term ($t4s.....) is O u' is accepting or rejecting. Following the definition of öh '' is T if the hierarchy state changes; thus, o' = T if u' A and &' = & otherwise. Following our assumption on the MDP reward, we define reward transition functions as ry(u, u') 11 [[u & U A Au' E U1"") Learning call option's policy and lower-level option policies simultancously can be unstable due to non-stational non-stationarity (Levy et al.] 2019). c.g. the same lower-level option may only sometimes achieve its goal. To relax this problem, experiences are added to the buffer only when options achieve their goal (i.e., call options assume low-level options to terminate successfully). Due to the hierarchical structure, the policies will be recursively optimal (Dietterich) 2000) at best.
Termination. An option terminates in two cases. First, if the episode ends in a goal state or in a dead-end state. Second, if the hierarchy state changes and either successfully completes the option or interrupts the option. Concretely, a formula option wit a is only applicable in a hierarchy state (M; u, + r), while call option wi; always corresponds to stack item (u, M,, Mj, d +). We can thus analyze the hierarchy state to see if option is still executing or should terminate.
Algorithm. An option stack QH stores the currently executing options. Initially, QH is empty. At each step, QH is filled by repeatedly choosing options starting from the current hierarchy state using call option policies until a formula option is selected. Since HRMs have, by assumption, no circular dependencies, formula option will eventually be chosen. After action is selected using the
5

---

Under review as a conference paper at ICLR 2023
formula option's ' policy and applied, the DQNs associated with formula options are updated. The new hierarchy state is then used to determine which options in Qz have terminated. Experiences for the terminated options that achieved their goal are pushed into the corresponding buffers, and the DQNs associated with the call options are updated. Finally, 22 is updated to match the call stack of the new hierarchy state (if needed) by mapping each call stack item into an option, and adding it to A if it is not already there. By aligning the option stack with the call stack, we can update DQNs for options that ended up being run in hindsight and which would have been otherwise ignored.
5 LEARNING HIERARCHIES OF REWARD MACHINES FROM TRACES
In the previous section, we explained how a given HRM can be exploited using options; however, engineering an HRM is impractical. We here describe LHRM, method that interleaves policy learning with HRM learning from interaction. We consider a multi-task setting. Given T tasks and I instances (e.g., grids) of an environment, the agent learns (i) an HRM for each task using traces from several instances for better accuracy, and (ii) general policies to reach the goal in each task-instance pair. Namely, the agent interacts with T x I MDPs Maj. where i E [1, []] and j E [1, /]. The learning proceeds from simpler to harder tasks such that HRMs for the latter build on the former.
In what follows, detail the components of LHRM. We assume that (i) all MDPs share proposi- tions P and actions A, while those defined on a given instance share states S and labeling function I; (ii) to stabilize policy learning, dead-end traces must be common across tasks [ (iii) the root's height of a task's 's HRM (or task level, for brevity) is known (see Table D for CRAFT WORLD); and (iv) without loss of generality, each RM has single accepting state and single rejecting state.
Curriculum Learning (Bengio et al., 2009). LHRM learns the tasks' HRMs from lower to higher levels akin to Pierrot al. (2019). Before starting an episode, LHRM selects an MDP Maj. where i E [1, 7] and E (. The probability of selecting an MDP M.j is determined by an estimate of its average undiscounted return Riy such that lower returns are mapped into higher probabilities (see details in Appendix D) Initially, only level 1 MDPs can be chosen. When the minimum average return across MDPs up to the current level surpasses given threshold, the current level increases by 1, hence ensuring the learned HRMs and their associated policies are reusable in higher level tasks.
Learning an HRM. The learning of an HRM is analogous to learning flat RM (Toro learte al., 2019 Xu et al., 2020 Furelos-Blaaaae
et al.) 2021 Hasanbeig et al.. 202T). The objective is to learn the state transition function fo, of the root M, with height h,r given (i) a set of states U4, (ii) a set of label traces A- = AGUAPUA U.A, (iii) set of propositions PP (iv) a set of RMs M with lower heights than ht. (v) a set of callable RMs Mc C .M (by default, MM = .M), and (vi) the maximum number of disjuncts in the DNF formulas labeling the edges. The learned state transition function yo, is such that the resulting HRM H = (M U [, P)) accepts all goal traces A rejects all dead- end traces A P. and neither accepts rejects incomplete traces A', The transition functions can be represented as sets of logic rules, which are learned using the ILASP (Law et al. 2015) inductive logic programming system (see Appendix F. for details on the ILASP encoding).
Interleaving Algorithm. LHRM interleaves the induction of HRMs with policy learning akin to Furelos-Bland Blanco al. 2021)) Initially, the HRM's root of each task
[1, consists of 3 states (the initial, accepting, and rejecting states) and neither accepts nor rejects anything. A new HRM is learned when an episode's label trace is not correctly recognized by the current HRM (i.e., if goal trace is not accepted, dead-end trace is not rejected, or an incomplete trace is accepted or rejected). The number of states in Ur increases by when an HRM that covers the examples cannot be learned, hence guaranteeing that the root has the smallest possible number of states (i.e., it is minimal) for specific value of k. When an HRM for task i learned, the returns Rey in the curriculum are set to 0 for all j []. Analogously to some RM learning methods (Toro Iearte et al. 2019: Xu et al. 2020 |Hasanbig et al. (02I)) the first HRM for a task is learned using a set of traces; in our case, the P. shortest traces from set of p goal traces are used (empirically, short traces speed up learning). Finally, LHRM leverages learned options to explore the environment during the collection of the p goal traces, speeding up the process when labels are sparse. Specifically, options from lower height RMs are sequentially selected uniformly at random, and their greedy policy is run until termination.
.) in Equation 1 is Of (sT+1, s(+1) = (T, 1). Since experiences (#e, a, 8t+1) are shared through the replay buffer, evaluating the condition differently can produce instabilittes.
'The term qave (st+1 (s

---

Under review as a conference paper at ICLR 2023
6 EXPERIMENTAL RESULTS
We evaluate the policy and HRM learning components of our approach using two domains described below. We report the average performances across 5 runs, each consisting of different set of 10 random instances. Learning curves show the average undiscounted return obtained by the greedy policy every 100 episodes across instances. For other metrics (e.g., learning times), present the average and the standard error, with the latter in brackets. In HRM learning experiments, we set a 2-hour timeout to learn the HRMs. See Appendix Ffor experimental details and extended results.
Domains. We consider four grid types for the CRAFTWORLA domain introduced in Section 3 an open plan 7 7 grid (OP, Figure aa). open plan 7 grid with lava location (OPL), 13 x 13 four rooms grid (FR: [Sutton et al.) 1999). and a 13 x 13 four rooms grid with a lava location per room (FRL). The lava proposition must always be avoided. WATERWOR WORD (Karpathy 2015 Sidor 2016 Toro Icarte et al.; 2018) consists of a 2D box containing 12 balls of 6 different colors (2 per color) each moving at a constant speed in a fixed direction. The agent ball can change its velocity in any cardinal direction. The propositions P = {r" g. b, m. y are the balls' colors. Labels consist of the color of the balls the agent overlaps with and, unlike CRAFTWORLD they may contain multiple propositions. The tasks consist in observing color sequences. We consider two settings: without dead-ends (WOD) and with dead-ends (WD). In WD, the agent must avoid 2 balls of an extra color.
Policy Learning in Handcrafted HRMs. We compare the performance of policy learning in hand- crafted non-flat HRMS against in flat equivalents. Remember that an equivalent flat HRM always exists for any HRM (see Theorem MT. For fairness, the flat HRMs are minimal. Figure 2 shows the learning curves for some WRAFTWORLD tasks in the FRL setting. The convergence rate is similar in the simplest task (MILKBUCKET)) but higher for non-flat HRMs in the hardest ones. As both approaches use the same set of formula option policies, differences arise from the lack of modular- ity in flat HRMs. Call options, which not present in flat HRMs, constitute independent modules that help reduce reward sparsity. MILKBUCKET involves less high-level steps than BOOK QUILL and CAKE, thus reward is less sparse and non-flat HRMs are not as beneficial. The effectiveness of non-flat HRMs is also limited when (i) the task's s goal is reachable regardless of the chosen options (e.g., if the are no edges to rejecting states, like in OP and FR), and (ii) the reward is not too sparse, like in OPL (the grid is small) or WATERWORLA (the balls can easily get near the agent).
Mirgisswwer
BOORQUiLL
CANR
1.0-
0.8-
3.8-
Avonngo ichun
Averggi minun
0.5-
2UG
RG
Aveegg
0.4-
0.2-
Naa
3.2
Noo-Plai
0.0
0.0
5.0
16.0
12.0
20
2U0
3.0
6.0
10.0
15.0
00.0 000
6.0
10.0
15.00
70
Number of epinodes
Number of epioooess
x100
Number of epicodes
Figure 2: Learning curves for three CRAFTWORL.D (FRL. tasks using handcrafted HRMs.
Learning of Non-Flat HRMs. Figure 3 shows the LHRM learning curves for CRAFTWORLD (FRL) and WATERWORLD (WD). These settings are the most challenging due to the inclusion of dead-ends since (i) they hinder the observation of goal examples in level tasks using random walks, (ii) the RMs must include rejecting states, (iii) formula options must avoid dead-ends, and (iv) call options must avoid invoking options leading to rejecting states. In line with the curriculum method, LHRM does not start learning task of a given level until tasks in previous levels are mastered. The convergence for high-level tasks is often fast due to the reuse of lower level HRMs and policies.
The average time (in seconds) exclusively spent on learning all HRMs is 1009.8 (122.3) for OP, 1622.6 (328.7) for OPL, 1031.6 (150.3) for FR, 1476.8 (175.3) for FRL, 35.4 (2.0) for WOD, and 67.0 (6.2) for WD. Including dead-ends (OPL, FRL, WD) incurs longer executions since (i) there is one more proposition, (ii) there are edges to the rejecting state(s), and (iii) there are dead-end traces to cover. We observe that the complexity of learning an HRM does not necessarily correspond with the task complexity (c.g., the times for OP and FRL are similar). Learning in WATERWORD is faster than in CRAFTW ORLD since the RMs have fewer states and there are fewer callable RMs.
7

---

Under review as a conference paper at ICLR 2023
10
Barma
RO E-iisl
Bocket
BC Bi
LEACHER
Nvmm returo
11.1
ROABIC Mobbar
Aoom
MAP
MILKBUCKGE
BARaicaa (ocis cNAV)
0.2
BookO
MILKB SUGAR
0.0
00
10:11
20-0
30,0
10:01
20:0
3:0
Number of spiecales
X
Nomber of opientee
XII
Figure 3: LHRM learning curves for CRAFTWORLD (FRL) and WATER (WD). The leg- end in WATERWORLD separates tasks by level, and the subtask order (in brackets) follows that introduced in Table I The dotted vertical lines correspond to episodes in which an HRM is learned.
By restricting the callable RMs to those required by the HRM (e.g., using just PAPER and LEATHER RMs to learn BOOK's s HRM), there are fewer ways to label the edges of the induced root. Learning is 5-7x faster using 20% fewer calls to the learner (i.e., fewer examples) in CRAFTWORLD and 1.5x faster in WATERWORLD; hence, HRM learning becomes less scalable as the number of tasks and levels grows. This is an instance of the utility problem (Minton 1988). Refining the callable RMs set 'a priori' to speed up HRM learning is a direction for future work.
We evaluate the performance of exploration with options using the number of episodes needed to collect the P goal traces for a given task since the activation of its level. Intuitively, the agent will rarely move far from region of the state space using primitive actions only, thus taking more time to collect the traces; in contrast, options enable the agent to explore the state space more efficiently. In the FRL setting of CRAFTWORLA we observe that using primitive actions requires 128.1x more episodes than options in MILKBUCKET, the only level 2 task for which p traces are collected (although in just 2/5 runs). Likewise, primitive actions take 20.8x and 7.7x more episodes in OPL. and WD respectively. In OP and WOD options are not beneficial since episodes are relatively long (1,000 steps), there are no dead-ends and is easy to observe the different propositions.
Finally, we observe that using single goal trace to learn the first HRMs (p = Ps 1) incurs time- outs across all CRAFTWORLD settings, thus showing the value of using many short traces instead.
Learning Flat HRMs. Learning a flat HRM is often less scalable than learning a non-flat equivalent since (i) previously learned HRMs cannot be reused, and (ii) the flat HRM usually has more states and edges (as shown in Theorem 2 the growth can be exponential). We compare the performance of learning (from interaction) a non- flat HRM using LHRM with that of an equivalent flat HRM using LHRM, DeepSynth (Hasanbeig et al. 2021), LRM (Toro Icarte et al. 2019) and JIRP (Xu et al. 2020 Akin to LHRM, JIRP induces RMs with explicit accepting states, while DeepSynth and LRM do not. We use OP and WOD instances for CRAFTWORLD and WATERWORLD respectively.
The non-flat HRM for MILKBUCKET is learned in 1.5 (0.2) seconds, whereas the flat HRMs take longer to learn: 3.2 (0.6) w/L.HMM, 325.6 (29.7) w/DeepSynth, 347.5 (64.5) w/LRM and 17.1 (5.5) w/IRPP. LHRM and JIRP learn minimal RMs, hence producing the same RM consisting of 4 states and edges. DeepSynth and LRM do not learn minimal RM but one that is good at predicting the next possible label given the current one. In domains like ours where propositions can be observed anytime (i.e., without temporal dependencies between them), these methods tend 'overfit' the input traces and produce large outputs that barely reflect the task's 's structure, e.g. DeepSynth learns RMs with 13.4 (0.4) states and 93.2 (1.7) edges. In contrast, methods learning minimal machines exclusively from observable traces may suffer from overgeneralization (Angluin, 1980) in other do- mains g., with ceeporrallydependemn propositions). In more complex tasks such as BOOK, LHRM learns the flat HRM (see Figure [b) in 191.2 (36.4) seconds, whereas methods learning the flat HRM (see Figure Icb usually time out or, in the case of DeepSynth, learn bigger representations.
The performance of DeepSynth, LRM and JIRP is poor in WATERWORLD since they all learn RMs whose edges are labeled with proposition sets instead of formulas, unlike LHRM; thus, the RMs may require exponentially more edges, motivating the use of formulas for abstraction. For instance, the flat HRM for RG requires 64 edges instead of 2, and only LHRM and JIRP can learn it on time. All flat HRM learners time out in RG& BC, whereas the non-flat HRM is learned in 4.5 (0.3) seconds.
8

---

Under review as a conference paper at ICLR 2023
7 RELATED WORK
RMs and Composability. Our RMs differ from the original ones (Toro Icarte et al. 2018 2022)
in that (i) an RM can call other RMs, (ii) there are explicit accepting and rejecting states (Xu et al.
2020 Furelos- Blanco et al. 202T), and (iii) transitions are labeled with propositional logic formulas instead of proposition sets (Furelos- Blanco al.] (02T). Recent works derive RMs (and similar
FSMs) from formal language specifications (Camacho et al., 2019 Araki et al.) 2021) and expert demonstrations (Camacho et al.) 202T), or learn them from experience using discrete optimiza-
tion Toro Iearte al.) 2019), SAT solving (Xu et al. 2020), active learning (Gaon & Brafman
2020 Xu et al. 2021). state-merging (Xu et al. 2019 Gaon & Brafmann (020), program synthe-
sis (Hasanbeig et al. 2021 inductive logie programming (Furelos-Bil Blanco al.
2021). Prior
ways of composing RMs include (i) merging the state and reward transition functions (De Giacomo
et al. 2020), and (ii) encoding multi-agent task using an RM, decomposing it into one RM per agent and executing them in parallel (Neary et al. (021). Task composability has also been modeled using subtask sequences called sketches (Andreas et al. 2017), context-free grammars defining subset of English (Chevalier- Boisvert et al.) 2019), formal languages (Jothimurugan et al., 2019
León et al. 2020 Wang et al.) 2020) and logic-based algebras (Nangue Tasse et al. 2020).
Hierarchical RL. Our method for exploiting HRMs resembles a hierarchy of DQNs (Kulkarni et al. 2016). Akin to option discovery methods, LHRM induces a set of options from experience. LHRM requires set of propositions and tasks, which bound the number of discoverable options; similarly, some of these methods impose an explicit bound (Bacon et al. 2017 Machado et 2017). LHRM
requires each task to be solved at least once before learning an HRM (and, hence, options), just like other methods (MeGovern & Barto 2001, Stolle & Precup 2002). The problem of discovering
options for exploration has been considered before (Bellemare et al.
2016 Machado et al. 2017
Jinnai et al. 2019. Dabney et al. 202I). While our options are not explicitly discovered for explo- ration, we leverage them find goal traces in new tasks. Levy al.
(2019) learn policies from
multiple hierarchical levels in parallel by training each level as if the lower levels were optimal; likewise, we train call option policies from experiences where invoked options achieve their goal.
HRMs are close to hierarchical abstract machines (HAMs; Parr & Russell 1997) since both are hierarchies of FSMs; however, there are two core differences. First, HAMs do not have reward transition functions. Second, (H)RMs decouple the traversal from the policies, i.c. independently of the agent's choices, the (H)RM is followed: thus, an agent exploiting an (H)RM must be able to interrupt its choices (see Section D. While HAMs do not support interruption, Programmable HAMs (Andre& & Russell (000)) extend HAMs to support it along with other program- features. Despite the resemblance, there are few works on learning HAMs (Leonetti et al., (0022) and there are many on learning RMs, hence showing (H)RMs are more amenable (yet expressive) to learning.
Curriculum Learning, Pierrot et al. (2019) learn hierarchies of neural programs given the level of each program, akin to our RMs height; likewise, Andreas et al. a (2017) prioritize tasks consisting of fewer high-level steps. The 'online" method by Matüienn et al. (2020) also keeps estimate of each task's ' average return, but it is not applied in an HRL scenario. Wang et al. (2020) learn increasingly complex temporal logic formulas leveraging previously learned formulas using set of templates.
likevise,AAndeas
CONCLUSIONS
We have here proposed (1) HRMs, formalism that composes RMs in a hierarchy by enabling them to call each other, (2) an HRL method that exploits the structure of an HRM, and (3) curriculum- based method for learning a collection of HRMs from traces. fla-flat HRMs have significant advantages over their flat equivalents. Theoretically, we have proved that the flat equivalent of given HRM can have exponentially more states and edges. Empirically, we have shown that (i) our HRL method converges faster given non-flat HRM instead of a flat equivalent one, and (ii) in line with the theory, learning an HRM is feasible in cases where its flat equivalent is not.
LHRM assumes that the proposition set is known, dead-end indicators are shared across tasks, there is a fixed set of tasks and the height for each HRM is provided. Relaxing these assumptions by form- ing the propositions from raw data, conditioning policies to dead-ends, and letting the agent propose its own composable tasks are promising directions for future work. Other interesting extensions include non-episodic settings and methods for learning globally optimal policies over HRMs.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY
To make our work more understandable and reprodueible, we provide pseudo-code, proofs and examples throughout the paper. We here outline the content covered in the appendices that help with reproducibility;
Appendix
All the intermediate steps for the hierarchy traversal example in Section
Appendix
Proofs for Theorems I
Appendix
The implementation details (including pseudo-code) for the policy learning algorithm
outlined in Section 4 We include running examples of the algorithm to aid understanding.
Appendix D
The implementation details for the curriculum learning mechanism introduced in Sec-
tion
Appendix
E How the root of HRM is learned using the ILASP inductive logic programming system, including proofs of correctness.
Appendix Details on experiments described in Section such as computational resources, implementation of the domains, training and evaluation details (e.g.. hyperparameters) and extended results (e.g., tables on which the results in the main paper are based).
Appendix G Handcrafted HRMs for the tasks used in the experiments.
We plan to release the code if the paper is accepted.
REFERENCES
David Andre and Stuart Russell. Programmable Reinforcement Learning Agents. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS) Conference, pp. 1019- 1025, 2000.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular Multitask Reinforcement Learning with Policy Sketches. In Proceedings of the International Conference Machine Learning (ICML), pp. 166-175, 2017.
Dana Angluin Inductive Inference of Formal Languages from Positive Data. Inf. Control., 45(2): 117-135, 1980.
Brandon Araki, Xiao Li, Kiran Vodrahalli, Jonathan A. DeCastro, Micah J. Fry, and Daniela Rus. The Logical Options Framework. In Proceedings of the International Conference Machine Learning (ICML), pp. 307-317, 2021.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The Option-Critt Architecture. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 1726-1734, 2017.
Andrew G. Barto and Sridhar Mahadevan. Recent Advances in Hierarchical Reinforcement Learn- ing. Discrete Event Dynamic Systems, 13(4):341377, 2003.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying Count-Based Exploration and Intrinsic Motivation. In Proceedings of the Ad- vances Neural Information Processing Systems (NeurIPS) Conference, pp. 1471-1479, 2016.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum Learning. In Proceedings of the International Conference Machine Learning (ICML), pp. 41-48, 2009.
Alberto Camacho, Rodrigo Toro Icarte. Toryn Q. Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. LTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 6065-6073, 2019.
Alberto Camacho, Jacob Varley, Andy Zeng, Deepali Jain, Atil Iscen, and Dmitry Kalashnikov. Re- ward Machines for Vision- Based Robotic Manipulation. Proceedings of the IEEE International Conference Robotics and Automation (ICRA), pp. 14284-14299 2021.
10

---

Under review as a conference paper at ICLR 2023
Maxime Shevvllir-BBiivert, Lucas Willems, and Suman Pal. Minimalistic Gridworld Environment for OpenAl Gym.
com/ wwtp///aiimec/c/eemmmmmmm hespa//gygmmmiiiiiim minigrid 2018.
Maxime Chevalier-Boisse
Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. BabyAI: A Platform Study the Sample Efficiency of Grounded Language Learning. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Will Dabney, Georg Ostrovski, and André Barreto. Temporally--Etended e-Greedy Exploration. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Giuseppe De Giacomo, Marco Favorito, Luca locchi, Fabio Patrizi, and Alessandro Ronca. Tempo- ral Logic Monitoring Rewards via Transducers. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 860-870, 2020.
Thomas G. Dietterich, Hierarchical Reinforcement Learning with the MAXQ Value Function De- composition. Artif. Intell. Res., 13:227-300 303, 2000.
Thomas G. Dietterich, Pedro M. Domingos, Lise Getoor, Stephen Muggleton, and Prasad Tadepalli. Structured machine learning: the next ten years. Mach. Learn., 73(1):3-25 23, 2008.
Thomas Fiter and Georg Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Ann. Math. Artif. Intell., 15(3-4):289-322 1995.
Daniel Manelos-Blanco Mark Law, Anders Jonsson, Krysia Broda, and Alessandra Russo. Induction and Exploitation of Subgoal Automata for Reinforcement Learning. J. Artif. Intell. Res., 70:1031- 1116, 2021.
Maor Gaon and Ronen I. Brafman. Reinforcement Learning with Non-Markovian Rewards. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), pp. 3980-3987, 2020.
Michael Gelfond and Yulia Kahl. Knowledge Representation, Reasoning, and the Design of Intelli- gent Agents: The Answer-Set Programming Approach. Cambridge University Press, 2014.
Michael Gelfond and Vladimir Lifschitz. The Stable Model Semantics for Logic Programming. In Proceedings of the International Conference and Symposium on Logic Programming, pp. 1070- 1080, 1988.
Mohammadhosein Hasanbeig, Natasha Yogananda Jeppu, Alessandro Abate, Tom Melham, and Daniel Kroening. DeepSynth: Automata Synthesis for Automatic Task Segmentation in Deep Re- inforcement Learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 7647-7656, 2021.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural Networks for Machine Learning Lecture 6a: Overview of Mini-Batch Gradient Descent.
https:/ www. cs. www.storoto.oooom edu/ http://eeeeeeeeee//////eeee/////
s_iiees______ss
lec6. pdd 2012.
Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek. Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 13956-13968, 2019.
Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized Level Replay. In Proceedings of the International Conference on Machine Learning (ICML), pp. 4940-4950, 2021.
Yuu Jinnai, Jee Won Park, David Abel, and George Dimitri Konidaris. Discovering Options for Ex- ploration by Minimizing Cover Time. In Proceedings of International Conference on Machine Learning (ICML), pp. 3130-3139, 2019.
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A Composable Specification Language for Reinforcement Learning Tasks. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS) Conference, pp. 13021-13030, 2019.

---

Under review as a conference paper at ICLR 2023
Andrej Karpathy, REINFORCEj:: WaterWorld demo.
http://s..taaaff....eeeeoeeeeeee html 2015.
Tejas D. Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical Deep
Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation. In Pro- ceedings of the Advances in Neural Information Processing Systems (NeurIPS) Conference, pp- 3675-3683, 2016.
Mark Law. Inductive Learning of Annwwrr Set Programs. PhD thesis, Imperial College London, UK, 2018.
Mark Law, Alessandra Russo, and Krysia Broda. The ILASP System for Learning Answer Set Programs, 2015. https::///w/ttt doc. ic ac uk/ mixx/mmle m1 1909/ ILASP
Mark Law, Alessandra Russo, and Krysia Broda. Iterative Learning of Answer Set Programs from Context Dependent Examples. Theory Pract. Log. Program., 16(5-6)8834-88) 848, 2016.
Mark Law, Alessandra Russo, and Krysia Broda. The Meta-program Injection Feature ILASP.
Technical report, Imperial College London, June 2018. URL https::/ /wwp://wwwww... doc. ic.ac.cc..
uuk/mm19999) CaA00///LAAPPnneeeneee
Borja G. León, Murray Shanahan, and Francesco Belardinelli. Systematic Generalisation through
Task Temporal Logic and Deep Reinforcement Learning. CoRR, abs/2006.08767 2020.
Matteo Leonetti, Luca Iocchi, and Fabio Patrizi. Automatic Generation and Learning of Finite-State Controllers. In Proceedings of the International Conference on Artificial Intelligence: Methodol- ogy. Systems, Applications (AIMSA), pp. 135-144, 2012.
Andrew Levy, George Dimitri Konidaris, Robert Platt Jr., and Kate Saenko. Learning Multi-Level Hicrarchies with Hindsight. In Proceedings of the International Conference on Learning Repre- sentations (ICLR), 2019.
Marlos C. Machado, Mare G. Bellemare, and Michael H. Bowling. A Laplacian Framework for Option Discovery in Reinforcement Learning. In Proceedings of the International Conference on Machine Learning (ICMI.), pp. 2295-2304 2017.
Tambet Matiisen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-Student Curriculum Learning. IEEE Trans. Neural Networks Learn. Syst. 319)::3333333 2020.
Amy McGovern and Andrew G. Barto. Automatic Discovery of Subgoals in Reinforcement Learn- ing using Diverse Density. In Proceedings of the International Conference on Machine Learning (ICML). pp. 361-368, 2001.
Steven Minton. Quantitative Results Concerning the Utility of Explanation-Based Learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 564-569, 1988.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas 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, 518(7540):529-555 533,, 2015.
Geraud Nangue Tasse, Steven D. James, and Benjamin Rosman. A Boolean Task Algebra for Rein- forcement Learning. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS) Conference, pp. 9497-9507, 2020.
Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topcu. Reward Machines for Cooperative Multi-Agent Reinforcement Learning. Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 934-942. 2021.
Ronald Parr and Stuart J. Russell. Reinforcement Learning with Hierarchies of Machines. In Pro- ceedings of the Advances in Neural Information Processing Systems (NeurIPS) Conference, pp- 1043-1049, 1997.
12

---

Under review as a conference paper at ICLR 2023
Thomas Pierrot, Guillaume Ligner, Scott E. Reed, Olivier Sigaud, Nicolas Perrin, Alexandre Laterre, David Kas, Karim Beguir, and Nando de Freitas. Learning Compositional Neural Programs with Recursive Tree Search and Plamning. In Proceedings of the Advances in Neural Information Processing Systems (NewrIPS) Conference, pp. 14646-14656, 2019.
Szymon Sidor. Reinforcement Learning with Natural Language Signals. Master's thesis, Mas- sachusetts Institute of Technology, 2016.
Michael Sipser. Introduction to the Theorr of Computation. PWS Publishing Company, 1997. ISBN 978-0-534-94728-6
Martin Stolle and Doina Precup. Learning Options in Reinforcement Learning. In Proceedings of the International Symposium on Abstraction, Reformalation and Approximation (SARA), pp. 212 223, 2002.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Richard S. Sutton, Doina Precup, and Satinder P. Singh. Intra- Natron Learning about Temporally Abstract Actions. In Proceedings of the International Conference on Machine Learning (ICML), pp. 556-564, 1998.
Richard S. Sutton, Doina Precup, and Satinder P. Singh. Between MDPs and Semi-MDPS: A Frame- work for Temporal Abstraction in Reinforcement Learning. Artif. Intell., 112(1-2):111-211, 1999.
Rodrigo
Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A. Mcllraith. Us- ing Reward Machines for High-Level Task Specification and Decomposition in Reinforcement Learning. In Proceedings of the International Conference on Machine Learning (ICML), pp- 2112-2121, 2018.
Rodrigo Toro Icarte, Ethan Waldie, Toryn Q. Klassen, Richard Anthony Valenzano, Margarita P. Castro, and Sheila A. Mcllraith. Learning Reward Machines for Partially Observable Rein- forcement Learning. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS) Conference, pp. 15497-15508, 2019.
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward Ma- chines: Exploiting Reward Function Structure in Reinforcement Learning. J. Artif. Intell. Res., 73:173-208, 2022.
Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforcement Learning with Double Q-Learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 2094- 2100, 2016.
Guan Wang, Carl Trimbach, Jun Ki Lee, Mark K. Ho, and Michael L. Littman. Teaching a Robot Tasks of Arbitrary Complexity via Human Feedback. In Proceedings of the ACM/IEE Interna- lional Conference on Human-Robee Interaction (HRI), pp. 649-657, 2020.
Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. Joint Inference of Reward Machines and Policies for Reinforcement Learning. CoRR, abs/ 0bss/1909.55 1909.05912, 2019.
Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. Joint Inference of Reward Machines and Policies for Reinforcement Learning. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp- 590-598, 2020.
Zhe Xu, Bo Wu, Aditya Ojha, Daniel Neider, and Ufuk Topcu. Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples. In Proceedings of the International MCD-MAKE), pp. 135-135, 2021.
Conference for Machine Learning and Knowledge Extraction
13

---

Under review as a conference paper at ICLR 2023
A HIERARCHY TRAVERSAL EXAMPLE
The HRM in Figure lb
accepts trace À ((+) (8) (9), (000 (8), (m)). whose traversal is
(A) (Vo, U1, 02 V3, Va, U5 16), where:
bp (Mo, u0- T, T),
5u (vo: (+)
( ag: T, T>, (++)
( ul. -dd, [u u Mo, M1, -b, T))) (+))
-O=((MT; ut, - # [u u Mp. M1, -i6, T), (ug, u MT. 4, -x)1), (+))
(H((M u). T, [(g. up Mo. M, -6, T));
ui, T, T, un. Mo, M1, - T)),.
22 (1(11, {}}]
5 u]: T, [(u]: up Mo. M₁ -te, T)}, (f))
(H [ul un Mo, M1, -86 T), (ut, u Mr, MT, T)), (R))
-5H((M, [u]] ug. Mo. M1, - TY),
6н((Mo, ud: 1)
(Mo, un- I),
83 5и (v2, (
((Mo ud: T>0 (
(Mo, up. [),,,
5u (v3, {0)}
(H un: T, (). (b))
((M2, ug. T, [(bb u Mo, M2,, T, T)),; (t7)
(N((MT,uf 8 Kuu unj Mo M2, T, T), (ug, u. M2, MT, 8 T)), (b)
(H{(M2, u², T, [(ub, upr Mo. M2, T, L)
(M2, u/, T, [, ug. Mo, M2, T, T))>,
Vs (14 {+
(HM2 un T, [,,, up Mo, M2, T, T)),, (A))
6x((MT u4. fr, [(ug un: Mo. M2, T, T), (ug, ug M2, MT, A, T)),, (m)
64((M2, u² T, [ug ug, Mo. M2, T, T))),1)
6 ug: T, 0),11)
(Mo, ug. T, II).
6s 5 {+}}
(H(M ug. T>, (+) (n([ u4, m. Lun " Mo. Mr, m, TY), (+))
((Mo u 1)) 1)
(Mo, ug T
Example shows the traversal but omits the intermediate applications of hierarchical transition function 0z1-
B EQUIVALENCE TO FLAT HIERARCHIES OF REWARD MACHINES
In this section, we prove the theorems introduced in Section regarding the equivalence of an arbitrary HRM to flat HRM.
14

---

Under review as a conference paper at ICLR 2023
B.1 PROOF OF THEOREM
I
We formally show that any HRM can be transformed into an equivalent one consisting of a single non-leaf RM. The latter HRM type is called flat since there is a single hierarchy level.
Definition 6. Given an HRM H- (M, P), a constituent RM M, E .M is flat if its height h; 1.
Definition 7. An HRM H (M,M,, P) is flar if the root RM M, is flat.
We now define what it means for two HRMs to be equivalent. This definition is based that used in automaton theory Siipser 1997).
Definition 8. Given a set of propositions P and a labeling function I, two HRMs = (M, M,, P) and H' = (M', My, P) are equivalent if for any label trace À one of the following conditions holds: (i) both HRMs accept X, (ii) both HRMs reject A, or (iii) neither of the HRMs accepts or rejects A.
We now have all the required definitions prove Theorem I which is restated below. Theorem 1. Given an HRM H. there exists equivalent flat HRM H.
To prove the theorem, we introduce an algorithm for flattening any HRM. Without loss of generality, we work on the case of an HRM with two hierarchy levels; that is, an HRM consisting of root RM that calls flat RMs. Note that an HRM with an arbitrary number of levels can be flattened by considering the RMs two levels at a time. We start flattening RMs in the second level (i.e., with height 2). which use RMs in the first level (by definition, these are already flat), and once the second level RMS are flat, we repeat the process with the levels above until the root is reached. This process is applicable since, by assumption, the hierarchies do not have cyclic dependencies
recursion.
For simplicity, we use the MDP reward assumption made in Section 2 i.e. the reward transition function of any RM Mj is ru, n') [u & U A v/ E ((A1) like in Section 4 However, the proof below could be adapted to arbitrary definitions of ru))
Preliminary Transformation Algorithm. Before proving Theorem I introduce an interme- diate step that transforms a flat HRM into an equivalent one that takes contexts with which it may be called into account. Remember that call to an RM is associated with context. In the case of two-level HRMs such as the ones we are considering in this flattening process, the context and the exit condition from the called flat RM must be satisfied. Crucially, the context must only be satisfied at the time of the call; that is, it only lasts for a single transition. Therefore, if we revisit the initial state of the called RM by taking an edge to it, the context should not be checked anymore.
To make the need for this transformation clearer, we use the HRM illustrated in Figure 4a The flattening algorithm described later embeds the called RM into the caller one; crucially, the context of the call is taken into account by putting it in conjunction with the outgoing edges from the initial state of the called RM F Figure 4b is a flat HRM obtained using the flattening algorithm; however, it does not behave like the HRM in Figure 4a Following the definition of the hierarchical transition function δμ, the context of a call only lasts for a single transition in the called RM in Figure 4a (i.e.. a A -c is only checked when M, is started), but the context is kept permanently in Figure 4b which is problematic if we go back to the initial state at some point. We later come back to this example after presenting the transformation algorithm.
To deal with the situation above, we need to transform an RM to ensure that contexts are only checked once from the initial state. We describe this transformation as follows. Given flat HRM H = (M, M,, P) with root M, = (Ur P, Pr, Tr, U U ) we construct a new HRM H' (M', M,, P) with root M'. = (L,, P. G rh. up. U,A U such that:
2r = U (2)), where aP plays the role of the initial state after the first transition is taken.
. The state transition function sp. is built by copying yr and applying the following changes:
1. Remove the edges to the actual initial state from any state v E UK: (, uf, MT)
L. Note that since the RM is flat, the only callable RM is the leaf MT.
Add edges to the dummy initial state i.f from all states E UG that had an edge to the actual initial state: s/,, (v. a. MT) pr ue, MT).
We refer the reader to the 'Flattening Algorithm' description introduced later for specifie details.
15

---

Under review as a conference paper at ICLR 2023
aB
uf
M2
aa
MT aaaa-
MT
MT
CA -b
"1
ui
M
cA
-b
Mo
M1
(a) Original HRM with root Ma.
(b) Flattened HRM without transforming M1.
uf
MT
MT
a m
MT
M
ai
ui
MT
cc -b
uP
MT |c -be
un
MT
MT
(c) Transformed M1 from (a).
(d) Flattened HRM after transforming M1.
Figure 4: Example to justify the need for the preliminary transformation algorithm.
Add edges from the dummy initial state a, to all those states v E UV that the actual initial state u.f points to: sf ( .M) = 4f (uf. v. MT).
The reward transition function rf (u, u²) 1[u & U Au' u is defined as stated the beginning of the section.
The HRM H' such that M' {Mr, Mr Note that this transformation is only required in HRMs where the RMs have initial states with incoming edges.
We now prove that this transformation correct; that is, the HRMs are equivalent. There are two cases depending
whether the initial state has incoming edges or not. First, if the initial state uh. does not have incoming edges, step does not remove any edges going to wh. and step does not add any edges going ah. making it unreachable. Even though edges from üf to other states may be added, it is irrelevant since it is unreachable. Therefore, we can safely say that this case, the transformed HRM is equivalent the original one. Second, if the initial state has incoming edges, we prove equivalence by examining the traversals H()) and H'(A) for the original HRM H (M, M,., P) and the transformed one H' (M', MV,, given generic label trace (Co...., Cn). By construction, both H (A) and (((A) will be identical until reaching state w with an outgoing transition u in the case of H and the dummy initial state a in the case of H'. More specifically, upon reaching wo and satisfying an outgoing formula to the aforementioned states, the traversals are:
H(A) ((M,, uf T, D)..... ... (M, W. T, T,O) H²(A) = ((M,, u. T, [)...., (M,, w. T>)
By construction, state w in both HRMs, and both the aforementioned transitions from this state are associated with the same formula, i.e. (p,(w, uh, MT) &f (w. uP, MT). Therefore, if one of them is satisfied, the other will be too, and the traversals will become:
H()) ((M,, 2 T, D. (Mr, w, T, 1), (M,, 44 T, T,D);
H'(A) = ((M,, 2. T. D....... (M,, w, T. [), (M,, a., T))..
We stay in af and U until transition to state w' is satisfied. By construction, w/ is in both HRMs and the same formula is satisfied, i.e., spr w', MT) = (ū" w/, .T). The hierarchy traversals then become:
...., (Mr, w, T. D) (M,, u T, D) H'()) ((M,, u. T, T, [)).... (M, w. T. 1), (M/ 00. T. ().... (M,. al T. [}, (M,, w/, T, ()).
(A) ((M,, u. T, D......
(Mr, ui T. T.0>, (M,, w', T, ())
16

---

Under review as a conference paper at ICLR 2023
From here both traversals will be the same until transitions to u.. and a.. respectively satisfied again (if any) in and H'. Clearly, the only change in (A) with respect to (A) (except for the different roots) is that the hierarchy states of the form (M,, f.. T, []} in the latter appear as (M,, u², T. T. in the former. We now check if the equivalence conditions from Definition hold:
If (A) ends with state uf (A) ends with state ap following the reasoning above. By construction, neither of these states is accepting or rejecting; therefore, neither of these HRMs accepts or rejects A.
If ({)) ends with state w, (A) will also end with this state following the reasoning above. Therefore, if w is an accepting state, both HRMs accept X; if w is a rejecting state, both HRMs reject X; and if w is not an accepting or rejecting state, neither of the HRMs accepts rejects X.
Since all equivalence conditions satisfied for any trace X, H and H' are equivalent.
Figure 4c exemplifies the output of the transformation algorithm given M1 in Figure 44 as input, whereas Figure is the output of the flattening algorithm discussed next, which properly handles the context unlike the HRM in Figure 4b
Flattening Algorithm. We describe the algorithm for flattening HRM. As previously stated, assume without loss of generality that the HRM to be flattened consists of two hierarchy levels (i.e., the root calls flat RMs). We also assume that the flat RMs have the form produced by the previously presented transformation algorithm.
Given HRM H (M, Mr P) with root M, (Ur P, Mr, U, ,,," we build a flat RM Mr = (4 P. pr. Fr, 7.. U,, U using the following steps:
Yr,
1. Copy the sets of states and initial state from Mr (i.e., U, = Ur, n = o0.00, U, U 2
2. Loop through the non-false entries of the transition function yrr and decide what to copy. That is, for each triplet (u, u', M2) where u, u,u' E Ur and Mj M such that p,, u', M2) # 1:
(a) If M, = MM (i.c., the called RM is the Ieaf), we copy the transition: (r,u, ul, MT) = 4r (u, u', MT).
(b) If M, * Mr, we embed the transition function of M,- = (4 P, 49, Ty. u.. U, .RR)
into M, Remember that M, is flat. To do so, we run the following steps:
i. Update the set of states by adding all non-initial and non-accepting states from My. Similarly, the set of rejecting states is also updated by adding all rejecting states of the called RM. The initial and accepting states from Mj are unimportant: their roles are played by and u' respectively. In contrast, the rejecting states are important since, by assumption, they are global. Note that the added states u are renamed to Un,w'.i .j in order to take into account the edge being embedded: if the same state u was reused for another edge, then we would not be able to distinguish them.
ú, = ür U (Vuwes I v (4 \ (fug) (
ū. 12 U (urnee U E EE
ii Embed the transition function Φ of M, into py.. Since M, is flat, we can make copies of the transitions straightaway: the only important thing is to check whether these transitions involve initial or accepting states which, as stated before, are going be replaced by u and u' accordingly. Given triplet (v, w, MT) such that w E Uj and for which (v, w, M-) = Φ and & # 1 we update ;, as follows B
We do not to cover the case where v is an accepting state since, by assumption, there are no outgoing transitions from it In the case of rejecting states, we keep all of them as explained in the previous case and, therefore, there are no substitutions to be made. We also do not cover the case where w uz since the input flat machines never have edges to their initial states, but to the dummy initial state.
17

---

Under review as a conference paper at ICLR 2023
A. I = of and w & U then (r, Wa, MT) DNF( 9r(u, n', M,))- The initial state of M, has been substituted by u, we use the clone of w asso- ciated with the call (Wa,e')) and append the context of the call to Mj to the formula é.
B. I = ug and w E Una then (r v', ,-) = DNF A (u, u', M,))). Like the previous case but performing two substitutions: u replaces v and u' replaces W. The context is appended since it is transition from the initial state of My.
C. If v + us and w E UfA then (r u.'''' MT) accepting state by u', and use the clone of v associated with the call (f,,wr)). j). This time the call's context is not added since v is not the initial state of My.
Φ. We substitute the
D. If none of the previous cases holds, there are no substitutions to be made nor contexts be taken into account. Hence, (rr j. Wu,,', just use the clones of u and w corresponding to the call (Va,tt, and (u,w's).
MM) = Φ. We
3. We apply the transformation algorithm we described before, and form new flat HRM H = (1M,, .M). My, P) with the flattened (and transformed) root M,.
The reward transition function rf (u, u') 1|u & U,A Au' E U,,1 is defined as stated at the beginning of the section. Note that might not necessarily be state of the non-flat root, but derived from an RM with lower height.
We now have everything to prove the previous theorem. Without loss of generality and for simplicity, we assume that the transformation algorithm has not been applied over the flattened root (we have already shown that the transformation produces an equivalent flat machine).
Theorem 1. Given an HRM H, there exists an equivalent flat HRM H.
Proof. Let assume that an HRM H (M, M,, P), where M, is flat HRM that results from applying the flattening algorithm on an HRM H = (M, P), Mr.
where M, = (Ur, P, :Pr, u U 2 For these HRMs to be equivalent, any label trace X (Co.... ..) must satisfy one of the conditions in Definition g To prove the equivalence, we examine the hierarchy traversals (A) and (A) given a generic label trace A.
Let u E U be a state in the root Mr of H and let (,, u', MT) be satisfied transition from that state. By construction, u also in the root M, of the flat hierarchy H, and M, has an identical transition (,,(U, u', MT), which must also be satisfied. If the hierarchy states are (M,, u, T. D) and (M,, u, T. [}} for H and и respectively. then the next hierarchy states upon application of &h will be (M,, ut, T, [}) and (Mr, u', T, [). Therefore, both HRMs behave equivalently when calls to the leaf RM are made.
We now examine what occurs when non-leaf RM is called in H. Let (,, u', M2) be satisfied transition in M,, and let Vy(u,, w, M+) be satisfied transition from Mj's initial state. By con- struction, M, contains transition whose associated formula is the conjunction of the previous two, ie. fr (u, u', M2) A ( w. Mr). Now, the hierarchy traversals will be different depending on w:
. If w & U (i.e., w is not an accepting state of Mj), by construction, M, contains the transition (u, Wu,n' MT) (r,u,, u', M,) A spy (uf. (. w, MT). If the current hierarchy states are (the equivalent) (M, u, T, [}> and (M,, u, T, [} for H and H. then the next hi- erarchy states upon application of бн are (Mj. w. T, Ku, u', My, spy (u, v', My), T)]) and (M,, Wa j. T, D). These hierarchy states are equivalent since Wu.n's is a clone of w that saves all the call information (i.c., call machine M, for transitioning from u to u').
If w E U (i.e., w is an accepting state of Mj), by construction, M, contains the transition (,, u', MT) = &r (u, u', M2) A (,(u). w. MM). If the current hierarchy states are (the equivalent) (M,, u, T, D) and (M,, u, T. T.D) for H and H. then the next hierarchy states upon application of ōh are (M, u. T.0) and (M,, u', T, [).. These hierarchy states are clearly equivalent since the machine states are exactly the same.
We now check the case in which we are inside a called RM. Let (u, M2) be the transition that caused H to start running M,, and let (v, w. M+) be satisfied transition within MG such that
18

---

Under review as a conference paper at ICLR 2023
# uy. By construction, M, contains transition associated with the same formula (y w, MT).
The hierarchy traversals vary depending on wt
If U (i.e., w is not accepting state of M2), by construction, M, contains the transition (Vaaa jo Wa ii MT) L,(U, w, M-). For the transition to be taken in H, the hierarchy state must be (Mj, u, T, [(u, w', M,, Mj. MPr.sPr(e (u, u', M2), T)]). whereas in H it will be (Mr, "a T, [). These hierarchy states are clearly equivalent: Vu.u'j is clone of o that saves all information related the call being made (the called machine, and the starting and resulting states in the transition). Upon application of jh, the hier- archy states will remain equivalent: (M,, w, T, [u,, u/, M,, Mí. ipr (u, u', M2), T}}> and (My, Wa T, [}} (again Ww,u', saves all the call information, just like the stack).
If E Un (i.e., w is an accepting state of Mj), by construction, M, contains the tran- sition (V, j. u', MT) = (V, w, MT). This case corresponds to that where control is returned to the calling RM. Like in the previous case, for the transition be taken in H. the hierarchy state must be (M, T. Ku, M,, M,, (r (u, u', My), T)),, whereas in H it will be ( (Mr. Uu, 1). The resulting hierarchy states then become (Mr, u', T, D>> and (M, u', T, D) respectively, which are clearly equivalent (the state is exactly the same and both come from equivalent hierarchy states).
We have shown both HRMs have equivalent traversals for any given trace, implying that both will accept, reject, not accept nor reject trace. Therefore, the HRMs are equivalent.
Figure 5a shows the result of applying the flattening algorithm on the BoOk HRM shown in Fig- ure lb Note that the resulting HRM can be compressed: there are two states having an edge with the same label to specific state. Indeed, the presented algorithm might not produce the smallest possible flat equivalent. Figure 5b shows the resulting compressed HRM, which is like Figure Ic but naming the states following the algorithm for clarity. Estimating how much flat HRM (or any HRM) can be compressed and designing an algorithm to perform such compression are left as future work.
whan
M
FA
+
Aa
RA
u6
NO
(a) Without compression.
(b) With compression.
The notation u "j,,, denotes the i-th state of RM j in the call between states x and y in the parent RM. Note that x y appear only if that state comes from called RM. The blue states and edges in (a) can be compressed as shown in (b).
Figure 5: Results of flattening the HRM in Figure lb
B.2 PROOF OF THEOREM 2
We prove Theorem 2 by first characterizing an HRM H using a set of abstract parameters. Then, we describe how the number of states and edges in an HRM and its corresponding flat equivalent computed, and use these quantities to give an example for which the theorem holds. The parameters the following:
19

---

Under review as a conference paper at ICLR 2023
The height of the root hy-
The number of RMs with height NO.
The number of states in RMs with height i, U
The number of edges from each state in RMs with height i, E
We assume that (i) RMs with height only call RMs with height 1; (ii) RMs have a single accepting state and no rejecting states; (iii) all RMs except for the root are called: and (iv) the HRM well-formed (i.c., it behaves deterministically and there are no cyclic dependencies). Note that ((h.) 1 since there height h, we need it to call at least one RM with height h 1. Considering that all called RMs are have the same height simplifies the analysis since we can characterize the RMs at each height independently. Assumption (ii) is safe to make since a single accepting state is enough, and helps simplify the counting since only some RMs could have rejecting states. Assumption (iii ensures that the flat HRM will comprise all RMs in the original HRM. This is also a fair assumption: if given RM is not called by any RM in the hierarchy, we could remove it beforehand.
single root. Assumption (i) can be made since for the root to have
The number of states H in the HRM H is obtained by summing the number of states of each RM:
hr
H
NOTA
The number of states H in the flat HRM is given by the number of states in the flattened root RM
/ = -(h),
where ( is the number of states in the flattened representation of an RM with height which is recursively defined as:
if 1, 100 + (06-1) - (U -1 E
L
0
if 1.
That the number of states in a flattened RM with height i has all states that the non-flat HRM had. In addition, for each of the (+)) non-accepting states in the non-flat RM, there are E(0) edges, each of which calls RM with height
whose number of states is (i--1), These edges replaced by the called RM except for the initial and accepting states, whose role is now played by the states involved in the substituted edge (hence the 2). This construction process corresponds to the one used to prove Theorem !
The total of number of edges in an HRM is given by:
h
NO (1(00-1))
(+) is the total number of edges in an RM with height (the -1 is because the accepting state is discarded), so NO (17() - E() determines how many edges there are across RMs with height
where (T()
The total number of edges in the flat HRM is given by the total number of edges in the flattened root RM. E(he), where Eti) is the total number of edges in the flattened representation of an RM with height i, which is recursively defined as follows:
ifi 1, (17 1) EG-1) ifi> 1.
(0 - 1)
That is, each of the (U7(i - 1) E) edges an RM with height is replaced by (i--1) edges given by an RM with height i (if any).
The key intuition is that an HRM with root height h, > is beneficial representation-vee wise the number of calls across RMs with height is higher than the number of RMs with height 1; in
20

---

Under review as a conference paper at ICLR 2023
other words, RMs with lower heights are being reused. Numerically, the total number of edges/calls in an RM with height i is (Z7() - 1)F(() and, therefore, the total number of calls across RMs with height i is (T - E) N If this quantity is higher than N(1-1), then RMs with lower heights are reused, and therefore having RMs with different heights is beneficial.
Theorem 2. Let H = (M, Mr,P) P) be an HRM and let h be the height of its root M,. The number of states and edges in equivalent flat HRM H can be exponential in hy-
Proof. By example. Let H = (M, M, P) be an HRM whose root M, has height h, and is param- eterized by N²) 1, (1+) = 3, E = 1 for = I,..., hy. Figure 6 shows an instance of this hierarchy. Let us write the number of states in the flat RMs of each level:
( (11)) 3,
( T + (0() -2) (1t2) - E = 3 (3 - 1)
5,
( Uta) (7(2) 2) (vt3) - 1) B(0) 3 (5 (3 1)1 9,
- 11 0 = -1= 2' +1.
Hence, the number of states in the flat HRM is | = (k+)) = 2dr + 1, showing that the number of states in the flat HRM grows exponentially with the height of the root. In contrast, the number of states in the HRM grows linearly with the height of the root, |/| = Ex=, (OU) 3h,-
>h 1-3 =
u
M T
ut
M
T+
af
MT a
un
MT
b
11
Mi,1 1 <ish. hr
Mi
Figure 6: Example of an HRM whose root has height hr used in the proof of Theorem
2
In the case of the total number of edges, we again write some iterations to derive a general expres- sion:
E = (V -I)E = (3 -3-11)1-- =,
E(2) = (U(2) -1)E() 103-0(33000 13-1) 1 4,
E(3) (U 1)) A2) -3-
E = 2E = 2"
Therefore, the total number of edges in the flat HRM is E(h)) = 2hr In contrast, the total number of edges in the HRM grows linearly: Ei= NO (T - ()) Σh= 1(3 1)1 = 2h,.
Finally, we emphasize that the resulting flat HRM cannot be compressed, unlike the HRM in Fig- 5 each state has at most one incoming edge, so there are not multiple paths that can be merged. We have thus shown that there are HRMs whose equivalent flat HRM has a number of states and edges that grows exponentially with the height of the root.
Using the aforementioned intuition, we observe that the hierarchical structure is actually expected to be useful: the number of calls across RMs with height is (U - 1) = (3 - 1-] = 2, which is greater than the number of RMs with height - 1 (only 1).
There are cases where having a multi-level hierarchy (i.e., with h, > 1) is not beneficial. For instance, given an HRM whose root has height h, and parameterized by (1 1, ( 2 and
E(0 1. the number of states in the equivalent flat HRM is constant (2), whereas in the HRM itself it grows linearly with h,, The same occurs with the number of edges. By checking the previously
introduced intuition, we observe that (U - 1) ( = (2 - 1). 11 = 1 b ((1-1) = 1. which verifies that having non-reused RMs with multiple heights is not useful.
21

---

Under review as a conference paper at ICLR 2023
C POLICY LEARNING IMPLEMENTATION DETAILS
In this appendix, we describe some implementation details that were omitted in Section 4 for sim- plicity, First, we start by describing some methods used in policy learning. Second, we explain the option selection algorithm step-by-step and provide examples to ease its understanding.
C.I POLICIES
Deep Q-networks (DQNs; Mnih et al., 2015). We use Double DQNs (van Hasselt et al., 2016) for both formula and call options. The DQNs associated with formula options simply take an MDP state and output a Q-value for each action. In contrast, the DQNs associated with call options also take an RM state and context, which are encoded as follows:
The RM state is encoded using a one-hot vector. The size of the vector is given by the number of states in the RM.
The context, which is either T DNF formula with single disjunettconjunction, is encoded using a vector whose size is the number of propositions [P]. Each vector position corresponds (i) +1 if p appears positively, (ii) -1 if p appears negatively, or (iii) 0 if does not appear. Note that if the context T, the vector solely consists of zeros.
proposition p E P whose value depends on how p appears in the context:
These DQNs output value for each possible call in the RM; however, some of these values must be masked if the corresponding calls are not available from the RM state-context used as input. For instance, the DQN for Mo in Figure Tb outputs value for -w)), (M2, T), (M1, T), and (MT,*), +) the RM state was ug and the context was T, only the values for the first two calls are relevant. Just like unavailable calls, also mask unsatisfiable calls (i.e., calls whose context cannot be satisfied in conjunction with the accumulated context used as input).
To speed up learning, subset of the Q-functions associated with formula options is updated after each step. Updating all the Q-functions after each step is costly and we observed that similar per- formance could be obtained with this strategy. To determine the subset, we keep an update counter co for each Q-function (s. and a global counter e (i.c., the total number of times Q-functions have been updated). The probability of updating qs is:
86
Ps Ege So
where sq cc- Co 1.
A subset of Q-functions is chosen using this probability distribution without replacement.
Exploration. During training, the formula and call option policies e-greedy. In the case of formula options, akin Q-functions, each option w performs exploration with an exploration factor Ca*d, which linearly decreases with the number of steps performed using the policy induced by lone. Likewise, Kulkarni et al.] (2016) keep an exploration factor for each subgoal, but vary it depending on the option's success rather than the number of performed steps. In the case of call options, each RM state-context pair is associated with its own exploration factor, which linearly decreases as options started from that pair terminate.
The Formula Tree. As explained in Section 4 each formula option's policy is induced by a Q- function associated with a formula. In domains where certain proposition sets cannot occur, it is unnecessary to consider formulas that cover some of these sets. For instance, in a domain where two propositions and 6 cannot be simultaneously observed (i.e., it is impossible to observe {a, b)), formulas such as A -b or b A -a could instead be represented by the more abstract formulas or b; therefore, A -b and a could be both associated with a Q-function Go. whereas A -a and could be both associated with a Q-function qb. By reducing the number of Q-functions, the learning naturally becomes more efficient.
We represent relationships between formulas using a formula tree which, as the name suggests, arranges a set of formulas in tree structure. Formally, given a set of propositions P. a formula tree is tuple (F, F,, L), where F is set of nodes, each associated with a formula; F, E J is the root of the tree and it is associated with the formula T; and C (2P)" " is a set of labels. All the nodes in the tree except for the root associated with conjunctions. Let (X) 22P denote the set of
22

---

Under review as a conference paper at ICLR 2023
T
a
a -
a a^* c
a
0. A c
A - A =
aA -
A - A mc
a A b A -c -d
a -b A - A -d
(a) Tree for L {{a), {b), (c), (d)).
(b) Tree for L ({a), (0), {c). (d), (a,c))-
Figure 7: Examples of formula trees for different sets of literals. Note that the node a A -b A me
(a) could also be child of A -c (the parent depends the insertion order).
literals of a formula X, e.g. if = aA -b, Y if (f) T, or (2.i) (X) S vYY) and (2.ii) for all labels L E IL, either L F X and L F Y. or L + X and L + Y. Case (2) indicates that Y is special case of X (it adds literals but it is satisfied by exactly the same labels). The tree is organized such that the formula at a given node subsumes all its descendants. The set of Q-functions is determined by the children of the root.
(b, A formula X subsumes a formula
During the agent-environment interaction, the formula tree is updated if (i) new formula appears in the learned HRMs, or (ii) new label is observed. Algorithm [ contains the pscudo-code for updating the tree in these two cases. When a new formula is added (line 1), we create a node for the formula (line 2) and add it to the tree. The insertion place is determined by exploring the tree top- down from the root F, (lines 3-19). First, we check whether a child of the current node subsumes the new node (line 7). If such node exists, then we go down this path (lines 8-9); otherwise, the new node is going to be a child of the current node (lines 16-17). In the latter case, in addition, all those children nodes from the current node that subsumed by the new node need to become children of the new node (lines 1 11-15). The other core case in which the tree may need an update occurs when a new label is observed (lines 20-25) since we need to make sure that parenting relationships comply with the set of labels L. First, we find nodes inconsistent with the new label: parenting relationship is broken (line 39) when the formula of the parent non-root node is satisfied by the label but the formula of the child node is not (or vice versa). Once the inconsistent nodes are found, we remove their current parenting relationship (lines 45-46) and reinsert them in the tree (line 47). Figure 7 shows two simple examples of formula trees, where the Q-functions are qa in (a), and do and GaAme in (b).
C.2 OPTION SELECTION ALGORITHM
Algorithm 2 shows how options are selected, updated and interrupted during an episode. Lines 1-3 correspond to the algorithm's initialization. The initial state is that of the environment, while the initial hierarchy state is formed by the root RM M,. its initial state uf, an empty context (i.e., 4 = T), and an empty call stack. The option stack Qu contains the options we are currently running, where options the front are the shallowest ones (e.g., the first option in the list taken in the root RM). The steps taken during an episode are shown in lines 4-14, which are grouped as follows:
1. The agent fills the option stack QH by selecting options in the HRM from the current hi- erarchy state until a formula option is chosen (lines 15-25). The context is propagated and augmented through the HRM (i.e.. the context of the calls is conjuncted with the propagat- ing context and converted into DNF form). Note that the context is initially T (true), and not that of the hierarchy state. possible that no new options are selected if the formula option chosen in a previous step has not terminated yet.
2. The agent chooses an action according to the last option in the option stack (line 6), which will always be formula option whose policy maps states into actions. The action is ap-
23

---

Under review as a conference paper at ICLR 2023
Algorithm Formula tree operations
Input: A formula tree (F, Fy., L), where F is set of nodes, F, F is the root node (associated
with the formula T), and IL is set of labels. procedure ADDFORMULA(F)
2:
3: procedure ADDNODE(new.nodd)
4: current.node t- F,
5: added node 1
6: while added node = do child_nodk + FINDSUISUUINNCCHHD/uurnnn..nnc new new_node)
7:
8:
if child_node * nil then current_node child_node
>. Keep exploring down this path
9:
10:
else
Insert the node
subsumed.childeee
new cowdeode)
12:
new node.children <- new node.children U subsumed children for child E subsumed children do current_node.childee +- current_node.childeen {child}
14:
15:
child.parent <- new_node
16:
current_ www.:nnodd.cciliie. <- Surrent_node.chilleee. U [new_node} (nniiidreennnuwnnnooe
new www.onooaaaaee parent current.node
18:
added node <- F+ FU (new node)
20:
procedure ONLABEL(C)
L L
22: inconsistent nodes + 0
for child E F,.children do PINDAICOOSSSTTTTTTOOSSCCCCCCCC. C. inconsistent_nodes)
24:
25:
26: procedure FINDSURRSIMINGCHHI.Diii
new_ new_node)
27:
for child E current childechildeen do
28:
if formuu. subsumes www.nnode.formula then
29:
return child
30:
return nil
31: procedure CETSUUSSUUMDDCHHIDDEEVCCCCCCCLL
new_node)
32:
subsumed_cchilrren + 0
33:
for child E current node. childrennrenn do
34:
new mode.forruul subsumes fhilu.formula then subsumed. whtpeeeedddcddddeeeeeeee
35:
U (new_node)
36:
return sublumed_chilldren
37: procedure FINDLIcONSSSTENNNNDDSSSmUmm
node, C, inconsistent nodes)
38:
for child E current node do
39:
if L = current_node formula L = formul then
40:
inconsistent_nnoee + inconsistent.nodes {child] else
41:
42:
procedure FunDIIcoMeSSTENNNOoExCccCCCCLLL, inconsistent.neeeee RENNSRETIKKONNSSSTTNNOOOOSSOOOO for node E inconsistent do wode.parent.children node.paaent..cildrenn \ {node}
43:
nodes)
45:
46:
node.parent + nil ADDNoDE(node)
47:
24

---

Under review as a conference paper at ICLR 2023
plied, and the agent gets the next state (line 7). The next hierarchy state is obtained by ap- plying the hierarchical transition function би using label ((5441) (line 8). The Q-functions associated with formula options' policies are updated after this step (line 9).
3. The option stack Qy is updated by removing those options that have terminated (lines 10, 26-45). The terminated options are saved in different list Qg to update the Q-functions of the RMs where they were initiated later on (line 11). The termination of the options is performed as described in Section 4 All options terminate if terminal state is reached (lines 27-28). Otherwise, we check options Q2 from deeper to shallower levels. The first checked option is always formula option, which terminates if the hierarchy state has changed (line 40). In contrast, a call option terminates
does not appear the stack (lines 33, 46-51) When option is found to terminate, it is added to fgg and removed from S2 (lines 35-36, 41 41-) If a non- tentterminating option is found (lines 37, 43), we stop checking for termination (no higher level options can have terminated in this case).
4. If least one option has terminated (line 12), the option stack is updated such that it contains all options appearing in the call stack (lines 13, 52-70). Options are derived for the full stack if 22H empty (lines 53, 54), or for the part of the stack not appearing f2 (lines 56-59). The new derived options (lines 61-70) from the call stack are assumed to start in the same state as the last terminated option (i.e., the shallowest terminated option, line 63) and to have been run for the same number of steps too. Crucially, the contexts should be propagated accordingly, starting from the context of the last terminated option (line 69).
As result of the definition of the hierarchical transition function őμ, the contexts in the stack may be DNF formulas with more than one disjunct. In contrast, the contexts asso- ciated with options are either T or DNFs with a single disjunct (remember that an option is formed for each disjunct). For instance, this occurs if the context is V b and (a, b) is observed: since both disjuncts are satisfied, the context shown in the call stack will be the full disjunction V b. In the simplest case, the derived option (which is associated with a DNF with a single disjunct or T) can include one of these disjuncts could memorize all the derived
said before
chosen uniformly at random (line 67). Alternatively, options and perform identical updates for both later on once terminated.
C.3 EXAMPLES
We briefly describe some examples of how policy learning is performed in the HRM of Figure lb We first enumerate the options in the hierarchy. The formula options are -1.0-- 42 42,0, w 1,
T. T w1,1 W1,1T: 2.1.TT and T. The first option should lead the agent observe the label (7) to satisfy # A -W. The Q-functions associated with this set of options are (+a w. Iw: P+. qe and qa. Note that T and T are both associated with ge. Conversely, the call options are W.1.- W W0.0 2.T
T.A
2,
M 2.T sequentially achieve theirs. The associated Q-functions are go. QI and 92. Note that T and T both associated with 92-
T where the first one achieves its local goal if formula options -1.0, and W,,,, T. and I.T
T
We now describe a few steps of the aforementioned option selection algorithm in two scenarios. First, we consider the scenario where all chosen options are run to completion (i.e., until their local goals are achieved):
1. The initial hierarchy state is (Mo, ug. T, [}> and the option stack QH is empty. We select options to fill Qg. The first option is chosen from ug in Mo using a policy induced by go- 1.-W At this state, the available options are Wo,0T and T Let us assume that the former is chosen. Then an option from the initial state of M1 under context -'d' is chosen, which can T only be 11.0 w Since this option is a formula option (the call is made to MT), we do not select any more options and the option stack is ΩH = ( 11,00 w1,0,w
2,
'We denote by Φ1 C 62, where 1 02 E DNFp, the fact that all the disjuncts of Φi appear in d2- This containment relationship also holds if both formulas T. For instance, (a A -c) S (a -c) d..
25

---

Under review as a conference paper at ICLR 2023
Algorithm/ 2 Episode execution using an HRM (continues in p. 27)
Input: An HRM H = (M, M,, P) and an environment ENV = (S, A. p,r, P.I.T). Initial MDP tuple
80 ENV.INIT()
2: (M, u, 1, + (Mr, u,, T,0>
Initial hierarchy state Initial option stack
3: QH + -
4: for each step t ...... do
5: SH < FILLOPTIONSTACC((H, (Mi, u, 2,
D Expand the option stack b Choose according to the last option in Ω2
6: 4- SELECTACTION(s, QH)
7:
B1+1 <- EEW.APPLYACTION(I)
8:
(M,, u', óh (M, u, 2, T), (s(+1))
Apply transition function
9: UIDAIIEFORUULLQEUUCCIOOSS 8c, a, 81+1)
10:
2g St TERMINATHHOPTIONNS
(M; u, Φ, T), (M,, u. Φ ())
11:
SFANTECCALLFFCCCCTNNN((........ ((++))
if |[ -0 then SH + (LINOOTTONSTACC((0, ((g))
13:
14:
(M,, u, T, (M₃ v' "
15:
procedure FILLOOTIIOSSTCC((, (M, u. ()
16:
FH < SH & T
17:
b The context is initially true The state-automaton pair which an option is selected while the last option in S2r is not formula option do SELECTÖPTION(S M2,
M, -Miu- f
19:
20:
j.
Select option (e.g., with e-greedy) > If the option is call option Next option is chosen on the called RM's initial state
+)
21:
if + then
22:
Mj + M2;U- < ub
23:
Φ < DNF( A d)
Update the context b Update the option stack (concatenate new option)
24:
f2 + QH @ jun
return 22/
26:
procedure TERMINATEOPTIONSSC.., s, (M,, u, P, (M, u',''''''' F',
27:
if' ST T Then
return Qzg 0 2g < 1122 + 2H
All options terminate D Initialize structures
29:
30:
while 11 do
While the option stack not empty
31:
k. + last option D2F
32:
if x * then
> If the option a call option
33:
in in__tack, + OPTIONINSTACK F. k,
I')
34:
in stack then
35:
Ug <- U2g wk.a. I/ R'r e wk,
u.
Update the list of terminated options D Remove the last option from the option stack
36:
37:
else
break
b Stop unrolling
39:
else
40:
if (M, u, ④, (M,. &',"") then
If the hierarchy state has changed...
41:
Qg 4- 2g 3 k
Update the list of terminated options Remove the last option from the option stack
2/ D2 3 wkee
else
44:
break
> Stop unrolling
45:
return 2z. S'H procedure OPTIONINSTACCK(... J.0
46:
47:
for 1 0... [ do
48:
(u,, Mr, M, 0' x²) + Ti if ifuf= vAi = à A. = aA C ø' A C C then The call option is in the call stack > Return whether appears in the stack and the index
49:
return T,1
51:
return -1-1
26

---

Under review as a conference paper at ICLR 2023
52:
procedure ALIGNOPTIOSTTACKO4
53:
if [Qar] = 0 then
54:
return ALCCNOOTTOOSTTACK/HPPPPRCC&..
55:
else
56:
Wk,0, <- last option in ΩH
57:
in stack, stack index OPTIONINSSAAC K,o,0.
58:
if stack then
return ALIGNOPTOONSTACCHELPPP((CC Qg, stacsttck_ndee,, index)
60:
return ΩH
61:
procedure ALCGNOPTONSTTACKHHLPPRRCC Stackksssssssssn... stackinndx,,
62:
63:
w. f last option in 22p
> Shallowest terminated option
64:
T +
Context initialized from last option
65:
for 1 = black_index... - 1
66:
(u,, ; Mi, Mj +) +i
67:
@sel + Select disjunct from e (e.g., randomly)
68:
22 + S2z @ whe
> Append new option to the option stack
69:
O DNF(#' A))
70:
return 12H
T 2. The agent selects options according to the formula option in S2 410.-w- whose policy is induced by A*사 w Let us assume that the policy tells the agent to turn right. Since the label at this location is empty, the hierarchy state remains the same; therefore, options terminate, and the option stack does not change.
3. Let assume that the agent moves forward twice, thus observing )+). The hierarchy state then becomes (M1, un. T, [ug] ud Mo, M1, - T}}> (see Appendix A for a step-by-step application of the hierarchical transition function). We check which options in f2 have terminated starting from the last chosen one. The formula option w -1,0,-w terminates be-
cause the hierarchy state has changed. In contrast, the call option wo,0, does not terminate since there is an item in the call stack, (uf ugy Mo, M1, -b, T) that can mapped into (meaning that the option is running).
T 4. An experience (s, (1.0 s') is formed for the terminated option, where s and s' the
observed tuples on initiation and termination respectively. This tuple is added to the replay buffer associated with the RM where the option appears. D1. since it achieved its goal (i.e.,
a label that satisfied + A was observed).
5. We align ΩH with the new stack. this case, Qy remains unchanged since its only option can be mapped into item of the new stack.
6. We start new step. Since the option stack does not contain a formula option, we select new options from the current hierarchy state according to a policy induced by 91. In this case, there a single eligible option: w1.1
In the second scenario, we observe what occurs when the HRM traversal differs from the options chosen by the agent:
1. The initial step is like the one in the previous scenario, but we assume w W is selected instead. Then, since this is a call option, an option from the initial state of M2 under T.x context T is chosen, which can only be W2 The option stack thus becomes QH = (W w2
T.W 2. Let us assume that by taking actions according to 2200T we end up observing { Like in the previous scenario, the hierarchy state becomes (M1, u/, T, [ u/ Mo. Mr T)
We check which options in Qg have terminated. The formula option 2200T terminates 2.T since the hierarchy state has changed, and the call option wp,0T also terminates since it
T.
27

---

Under review as a conference paper at ICLR 2023
cannot be mapped into an item of the call stack. Note that these options should intuitively finish since the HRM is being traversed through a path different from that chosen by the agent.
3. The replay buffers are not updated for these options since they have not achieved their local goals.
4. We align U2 with the new stack. The only item of the stack (ug: up. Mo. MM, w T) can -..-w be mapped into option W0,0,T We assume that this option starts the same tuple s and that it has run for the same number of steps as the last terminated option -0
2.T
D CURRICULUM LEARNING IMPLEMENTATION
We here describe the details of the curriculum learning method described in Section 5 When an episode is completed for May. Raj is updated using the episode's undiscounted return r as Rij f R.j computed
RR, + (1 B)r, where 3 E [0, 1] from the return and used to determine the probability of selecting tasks and instances. Note that this scoring function, also used in the curriculum method by Annreas al.) (2017), assumes that the undiscounted return ranges between 0 and (see Section 2). The probability of choosing task i is max, Gz/ E. max; Ckti that is, the task for which an instance is performing very poorly has higher probability. Having selected task i, the probability of choosing instance is Ctj/ Σx Cike ie. instances where performance worse have higher probability of being chosen.
hyperparameter.
score Gj
E LEARNING AN HRM FROM TRACES WITH ILASP
We formalize the task of learning an HRM using ILASP Law et al. 2015), inductive logic pro- gramming system that learns answer set programs (ASP) from examples. We address the reader to Gelfond & Kahl (0014) for introduction to ASP, and to Law (018 for ILASP. Our formalization is close to that by FFurelos-Blance et al. (2021) for flat finite-state machines. Without loss of gener- ality, as stated in Section 5 assume that each RM has exactly one accepting and one rejecting state. We first describe how HRMs are represented in ASP, and then explain the encoding of the HRM learning task in ILASP.
E. REPRESENTATION OF AN HRM IN ANSWER SET PROGRAMMING
In this section, we explain how HRMS are represented using Answer Set Programming (ASP). First, we describe how traces are represented. Then, present how HRMs themselves represented and also introduce the general rules that describe the behavior of these hicrarchies. Finally, we prove the correctness of the representation. We use A(X) to denote the ASP representation of X (e.g.. trace).
Definition 9 (ASP representation of label trace). Given a label trace À = denotes the set of ASP facts that describe it:
M(A)
[label (p. 1). snnsin U.JU
A(A) (step t). 0 5
[last(n) (n).).
The label(p, t) fact indicates that proposition p P is observed in step t, step(t) states that f is step of the trace, and last(n) indicates that the trace ends step n.
Example 2. The set of ASP facts for the label trace À ((0) 0. (+) is A(A) {label O).,
label (,, 2)., step(O), step(1)., step(2).. l2st(2).).
Definition 10 (ASP representation of an HRM). Given an HRM H = (M, P), A(H) =
UM.EMAMTT (M,)), where:
A(M.) Au (M, A,,)),
(M,) {state(u, Mi). | U4).
28

---

Under review as a conference paper at ICLR 2023
call(u, u', x +e. M,, M2)-
G(u, 1. x M,, T) non label(p1, T), sTep(T).
M, E M,u,u' Elu.
pi(u, u', M2) * L,, 1y-1 (pi(u, Ma)), E [L, kipll, M,
puu, + M, . T): not label(p,, step(t u + M, (p. step.T
Au (Mi)
Φe E M,,, de = A... A...A.
G(u, u' + M., label(pm. T), step(T).
Pn+1 A A... A Pm
Note that each non-leaf RM Mj in the hierarchy associated with its own set of rules A(M)), which described follows:
Facts state(u, Mc) indicate that w is a state of RM M..
Facts call(u, u', e, Mi, M,) indicate that edge e between states u and in RM M2 labeled with call to RM M,.
Normal rules whose head is of the form şlu, w', M₁. T) indicate that the transition from state u' with edge e RM M, does not hold step The body of these rules consists of single label(p, T) literal and step(T) atom indicating that T is step. Commonly, variables are represented using upper case letters in ASP, which is the case of steps here.
There some important things to take into account regarding the encoding:
There no leaf RM MT. We later introduce the ASP rules to emulate it.
The edge identifiers e between a given pair of states (u, u') range from I to the total number of conjunctions/disjjncti between them. Note that in Ap assume that the leaf RM has an index, just like the other RMs in the HRM. The index could be n since the rest are numbered from 0
1.
Example 3. The following rules represent the HRM in Figure lb
state(ug Mg). stata(up) Ma). state(ug, Mg). call(ug un Ma. Mı). cala(up. (. " Ma, M2). call uo: Mo. M.).
state(ug, Ma)- state(ug) (ug) Mo). call(n)) ugr I, Mo. M2). call(ua a vg 1, My. Mi).
((1g Mor Mo. label stop(T..
(p(1) ud M).T) not lahel T), (T)
(stata(ay M2). atate(af, M2). atate(af) M1)-
casi(u, of M1. MT). ca ug
Mr, MT).
((uf, u.. M,, :-onot (a, T), ST)
p(u), af Mr. :-nt label r). stop(T).
stata(u)) 0. M2). state(u), Ma). stata(ud Ma).
call a). MM. MT). call(
( uz
Ma. Mr).
((a2, us. 1, M,, not label(w, T), sTep(T).
p(u u2. Ma, T) nont label r). step(T).
General Rules. The following sets of rules, whose union denoted by how HRM functions (e.g., how transitions are taken or the acceptance/rejection criteria). For simplicity, all initial, accepting and rejecting states are denoted by wD, u and n respectively.
R. represent
The rule below is the inversion of the negation of the state transition function e Note that the predicate for yp includes the called RM M2 as an argument.
Rs (x Y, M2, not @(X, Y, E,M, Y, M2), step(T).).
The rule set R1 introduces the pre_sat (X, M. T) predicate, which encodes the exit condition pre- sented in Section (3] and indicates whether call from state of RM can be started at time T. The first rule corresponds to the base case and indicates that if the leaf Mr is called then the condition satisfied if the associated formula is satisfied. The second rule applies to calls non-leaf RMs, where we need to satisfy the context of the call (like in the base case), and also check whether a call from the initial state of the potentially called RM can be started.
R1 = preessat X, M, T) (x(X -,,,,,,,, MT, pre sat M, T) :- : .2, T), pre sat(u M2, T), M2
The rule set R2 introduces the reachable(X: M. TO, T2) predicate, which indicates that state x of RM is reached between steps TO and T2. The latter step can also be seen the step
29

---

Under review as a conference paper at ICLR 2023
currently at. The first fact indicates that the initial state of the root RM is reached from step to step O. The second rule indicates that the initial state of a non-root RM is reached from step to step (i.e., it reached anytime). The third rule represents the loop transition in the initial state of the root M,: we stay there no call can be started at (i.e., we are not moving in the HRM). The fourth rule analogous the third but for the accepting state of the root instead of the initial state. Remember this is the only accepting state in the HRM that does not return control to the calling RMM The fifth rule is also similar the previous ones: it applies to states reached after TO that are non-accepting, which excludes looping in initial states of non-root RMs at the time of starting them (i.e., loops are permitted in the initial state of non-root RM if we can reach it afterwards by going back it). The last rule indicates that Y is reached at step T2 in RM M started at TO if there is an outgoing transition from the current state to Y at time that holds between T and T2, and state X has been reached between TO and T. We will later see how 5 is defined.
reachable(u* Mr, O, 0).
reachable (u), M, T, T) stateeuatteea MM), M-,,M step(T).
reachable(X, M, TO, T+1): :- reachable(X, M, TO, T), not pre_sat (X, M, T),
Step(T),X-uff M- R₂ reachable(X,M, M, TO, T+1): reachable(X, M, M, T), not pre_sat (X, T),,
step(T), MMM MM=Mp.
reachable(X,M, TO, T+1) reachable(X, M, IO,
T), not pre_sat T),
step(T), X!=uA,
rea TO, T2): r...rraaaaa..,,..T TO, T), 6xx, T,),
The rule set R3 introduces two predicates. The predicate satisfied(M, TO, TE) indicates that RM M is satisfied if its accepting state u is reached between steps TO and TE. Likewise, the predicate fai TO, TE) indicates that RM fails its rejecting state n reached between steps TO and TE. These two descriptions correspond to the first and third rules. The second rule applies to the leaf RM MT. which always returns control immediately; thus, is always satisfied between any two consecutive steps.
satisfied TO, TE): :- reachableeeaaraeeeee .M, TO, TE). R3 Satisfied[MT.. T, T+1] :- (T). failed(M, TO, TE) reachable
TO, TE).
The following set, R4, encodes multi-step transitions within an RM. The predicate 5(X, Y, M, T, T2) expresses that the transition from state to state Y in RM satisfied between steps T and T2. The first rule indicates that this occurs if the context labeling a call to an RM 122 is satisfied and that RM also satisfied (i.e., its accepting state is reached) between these two steps. In contrast, the second rule is used for the case in which the rejecting state of the called RM is reached between those steps. In the latter case, we transition to the local rejecting state u of M (i.e., the state we would have transitioned to does not matter). This follows from the assumption that rejecting states global rejectors (see Section 3p. The idea of this rule is that rejection is propagated bottom-up in the HRM.
6(X, Y. M, T, T2) Y, M, T), satisfiedMM2 T, T2). 66X,uu M, T, T2) :- -, M2, T),
R4
failed T2).
The last set, Rs. encodes the accepting/rejecting criteria. Remember that the last (T) predicate indicates that T is the last step of trace. Therefore, the trace is accepted if the root RM is satisfied from the initial step O to step T + 1 (the step after the last step of the trace, once the final label has been processed). In contrast, the trace is rejected if rejecting state in the hierarchy reached between these two same steps.
[accept:- :ccopt:-last(T) satisfied (M, 0, reject: las---astttt failed 0+1).
R₂
Unlike the formalism introduced in Section 3 this encoding does not use stacks, which would be costly to do. Here we know the trace to be processed and, therefore, the RMs be evaluated bottom-up: that is, we start evaluating the lowest level RMs first on different subtraces, and the result of this evaluation used in higher level RMs.
30

---

Under review as a conference paper at ICLR 2023
We now prove the correctness of the ASP encoding. To do so, we first introduce what means for an HRM to be valid with respect to a trace, as well as a definition and a theorem due to Gelfond & Lifschitz 1988) that will help us derive the proof.
Definition 11. Given label trace Xt, where X if H accepts X and * = G (i.e.. X is goal trace), or H rejects x and * = D (i.e., X is a dead-end trace), H. does not accept nor reject X and I (i.c., X is an incomplete trace).
(G, HRM H is valid with respect to
Definition 12. An ASP program P is stratified when there is partition
P Po UPP.....UUU
(P: and P3 disjoint for all i f))
such that, (1) for every predicate p. the definition of p (all clauses with p in the head) is contained in one of the partitions P. and, (2) for each S S n. a predicate occurs positively in a clause of P. then its definition is contained within UJ Pj. and if a predicate occurs negatively in clause of P. then its definition is contained within Ujei Pj.
Theorem 3. If an ASP program P is stratified, then it has a unique answer set.
Proposition (Correctness of the ASP encoding). Given a finite label trace X", where * E (G, D, T}, and an HRM H MM that is valid with respect X,, the program P A(H) UR U A(X) has unique answer set AS and (1) accept E AS if and only if = G, and (2) reject E AS and only if* D.
Proof. First, we prove that the program P A(H) U A where R = UP= R,, has unique answer set. By Theorem B if P is stratified then it has a unique answer set. We show there is way of partitioning P following the constraints in Definition [2] A possible partition is P PoUPL P:U Ps. where Po A(A),, ), P1 (H). P2 = Ro UR, P3- UR UR5- The unique answer set AS = AS, U AS, U AS2 U AS3. where AS, corresponds to partition P,, is shown in Figure g For simplicity, [1]t] denotes the f-th label in trace X*, X :] denotes the subtrace starting from the t-th label onwards, and MX()) denotes the hicrarchy traversal using RM M, as the root.
We now prove that accept E AS and only x G (i.e., the trace achieves the goal). If G then, since the hierarchy is valid with respect to X (see Definition I1. the hierarchy traversal HX*) finishes the accepting state 4 of the root; that is, H())) n + +I T[= (Mr, , This holds and only if accept E AS.
The proof showing that reject E AS if and only if * (i.e., the trace reaches a dead-end) is similar to the previous one. If + D then, since the hierarchy is valid with respect to X the hierarchy traversal (X*) finishes in a rejecting state u that is, H (X*) in + 1] = (M&, 2t where Mj E M. This holds if and only if reject AS.
E.2 REPRESENTATION OF THE HRM LEARNING TASK ILASP
We here formalize the learning of an HRM and its mapping general ILASP learning task. We start by defining the HRM learning task introduced in Section 5
Definition 13. An HRM learning task is a tuple Th (r, U, P, M,Mc, u², u ( u A, k)), where is the index of the root RM in the HRM; U 2 {uO, w = is set of states of the root RM always containing an initial state u an accepting state uA, and a rejecting state RR P is a set of propositions; M 2 {MT} } is set of RMs; Me C .M is set of callable RMs; A AGUAP A' is a set of label traces; and K is the maximum number of conjunctionssddijjneet in each formula. An HRM H- = (M U (M,), M,, PP) is solution of Tи if and only if it is valid with respect to all the traces in A.
We make some assumptions about the sets of RMs M: (i) all RMs reachable from RMs in Mc must be in M, (ii) all RMs in M are deterministic, and (iii) all RMs in M are defined over the same set of propositions P (or a subset of it).
For completeness, The first definition corresponds to the form of the examples taken by ILASP, while the second corresponds to the ILASP tasks themselves.
provide the definition of ILASP task introduced by Law et al. (016))
31

---

Under review as a conference paper at ICLR 2023
AS. [label (p, 4). L n.p Le) (step()) 105 <n) U (last(n).),
(state(u, M.). M, E M \ (MThu
call(u,u, Mr M2).
Mr E M [MT], E u,,u,u E Eu,,plu, M.) * 1. k
x= E (oi(u, u', Ma)le (1. MILl
AS
p(u, d 1).
st Mr M (MTh.M, EMMuu, ElI
X pi u' M,) + 1, Sy- lor(a, a', Mol,
E [1, (u, u, M,)I,, [ Ifr p.lu, u' Mj)lel
u' te, (,,
0 5150 Mr EM, (. E M.M.v Ele pi(u, u', M,) # -, ='
-. loru,, Ma)l:
A82-
e [1, kalu,, M))l) Fil,,, Mj)le]
(pre_sat (,, M, 10 St M, M M EM
A EI.,T))
reachable Mr. M,)
reachable uu. ,,,,,,) ().
0 CM M, o EUIJU
reachable(v, (2)
=[x][] (Mr, U
reachable(u, Mc, 12,2).
E M (Mr: MT), u Ui,
-(
(M, (.)) < f1 51 <t
-
(satisfied f1, (2) (otisfied(MM,tt..
:1)/tt2 = (Mr ud ).
1, EM (Mr, MT
M((X"tt=)))t - -1]= (M, ud, ,:,),)))
-4 10112-21-1 111 (Mi un ..:))
(MT,
O (
ASs
Mailed(M,,41.1)
<4< :)](22 41]
failed
0 0<4<k 1, E M {Mr, Mr
&
-4]
8(u, w,, M,, +1
M (MT), u, E Euhi)
6(u, v', (2).
5 (MT), u, E eui,
(M..)) u', M,,,, ("tii] T= Ej
3 (M,
6(u, R Mi,
< Sn+1, 3M, E (MT) (.t. 1.t.:=ppp0 (i v' M2,,, X" (ti) } Es ju
M,
Mf(AT(t1 [)/2
12] 1=MM, ,,)) Me EM
accept H [n 1] =M,, (M.,u" [M]]
reject H +1] 11-1]]=M,,,00 R Mr E E (MT))
Figure& 8: Answer sets for each of the partitions in the program P= A(H) U J A(X), where H is an HRM, R is the set of general rules and X is a label trace.
32

---

Under review as a conference paper at ICLR 2023
Definition 14. A context-dependent partial interpretation (CDPI) is pair (letna en c where (eine, e is pair of sets of atoms, called a partial interpretation. and eate is an ASP program called context. A program P accepts CDPI (fe e etta) if and only if there is an answer set A, P U getz such that eine ç AS and e n ASS= =
Definition 15. An ILASP lask is tuple T (B, SM, (E+, (E+,E-)) where B the ASP background knowledge, which describes a set of known concepts before learning; SM is the set of ASP rules allowed in the hypotheses; and g and E- are sets of CDPIs called. respectively, the positive and negative examples. A hypothesis H. C SM is an inductive solution of T if and only if (i) Ve E Et, BU H. accepts e, and (ii) Ve E E
does not accept e.
Given an HRM learning task T2, we map it into an ILASP learning task A(Th) = (B, SM (E+ 0)) and use the ILASP system (Law al. 2015) to find an inductive solution Ag((H) C SM that covers the examples. Note that we do not use negative examples (E = 9). We define the components of A ((Th) below.
Background Knowledge. The background knowledge B Bu U BM U. is set of rules that describe the behavior of the HRM. The set By consists of state (M, facts for each state u E U of the root RM with index ASP representations of all RMs. Finally, R is the set of general rules introduced in Appendix [E.1 that defines how HRMs process label traces. Importantly, the index of the root r in these rules must correspond to the one used in Tи.
aim to induce, whereas By = UM A(M) contains the
Hypothesis Space. The hypothesis space Sy contains all ed and e rules that characterize a tran- sition from non-terminal state u 2 \ {wr, " different state u' E U {u} using edge i [1, x|. Formally, it is defined as
call (u, u', MM.
u wel's fur Au R u' EE {u) i [1, M Mc.cP
SM-
d. M, M, label T), sT). (u, v' i, M, T): non label T). step(T).
Example Sets.
Given a set of traces A = ACUA UA' the set of positive examples is defined as * D. (C)
g+ =
where
G ((accept), (reject)).
D = ((reject), (accept)), and
e = (f), rijecct
the partial interpretations for goal, dead-end and incomplete traces. The accept and reject atoms express whether a trace is accepted or rejected by the HRM; hence, goal traces must only be accepted, dead-end traces must only be rejected, and incomplete traces cannot be accepted or rejected. Note that the context of each example is the set of ASP facts (AA) that represents the corresponding trace (see Definition 9)
Correctness of the Learning Task. learning task.
The following theorem captures the correctness of the HRM
Theorem 4. Given an HRM learning task Th (r, U.P.P. P. M,Me, u. u RRR,R,,, A,,, HRM H = (M U (M,), (M,),M, M, P\) ) solution of Th if and only if (M,) is an inductive solution of A(TH) (B, (E (0)).
Proof. Assume H is a solution of TH
H is valid with respect to all traces in A (i.e., H accepts all traces in A rejects all traces in D and does not accept nor reject any trace in A.).
By Proposition I for each trace X E A" where (G, A(H) U R A(X*) has unique answer set AS and (1) accept E AS if and only * G, and (2) reject E AS if and only if x D.
33

---

Under review as a conference paper at ICLR 2023
For each example E E+, RUUAURA (HH) accepts e.
For each example e E Ex, B U A (M,) accepts e (the two programs are identical). (p(M, is inductive solution of A(TH).
Constraints. We introduce several constraints encoding structural properties of the HRMs we want to learn. Some of these constraints expressed in terms of facts pos(u, u', e, m, and neg(u, u', m. p). which indicate that proposition p E P appears positively (resp, negatively) in edge e from state u state u' in RM Mm These facts are derived from e rules in A (H) and injected in the ILASP tasks using meta- veta--rogram injection (Law et al., 2018).
The following set of constraints ensures that the learned root RM is deterministic using the satura- tion technique (Eiter& & Gottlob) 1995). The idea is to check determinism top-down by selecting two edges from a given state in the root, each associated with a set of literals. Initially, the set of literals is formed by those in the formula labeling the edges. If selected edge calls non-leaf RM, we select an edge from the initial state of the called RM, augment the set of literals with the associated formula, and repeat the process until a call to the leaf RM is reached. We then check if the literal sets are mutually exclusive. If there is a pair of edges from the root that are not mutually exclusive, the solution is discarded. The set of rules is shown below. The first rule states that keep two saturation IDs, one for each of the edges we select next and for which mutual exclusivity is checked. The second rule chooses state X in the root, whereas the third rule selects two edges from this state and assigns saturation ID to each of them. The fourth rule indicates that if one of the edges we have selected so far calls a non-leaf R.M, we select one of the edges from the initial state of the called RM and create a new edge with the same saturation ID. The fifth and sixth rules take the propositions for each set of edges (one per saturation ID). The next three rules indicate that if the edges are mutually exclusive (i.e., proposition appears positively in one set and negatively in the other) or they are the same, then the answer set saturated. The saturation itself is encoded in the following three rules: an answer set is saturated by adding every possible ed_ and root pot_ppiint atoms to the answer set. Due to the minimality of answer sets in disjunctive answer set programming, this "maximal" interpretation can only be answer set if there is smaller answer set. This will be the case if and only if every choice of edges satisfies the condition (i.e. every choice of ed mtx and root point atoms results in saturation). The constraint encoded in the final rule then discards answer sets in which saturation did not occur, meaning that the remaining solutions must satisfy the condition.
sat id( root (oot.pointt(,M M) call(x, M-M
ed (X, Y, E, M. M2), SatID) call Y, M, M2) wwt.:rroot..ooooff... M), sat sat_id(SatID) ed0 Y2, E2, M2,
call(u0, Y2, E2, M2, M3) ed_mtx((- M2), SatID) MT.
pos edd neg pPo e ). ID), neg(
) ID), (os
saturate : Bacttdeepoosppppppppppp prop(p.1),,ngggg pr.))))
saturate :-
saturate :- ed..
mddmmx((X....... M2). (x)t.pointxx..
root root.point(X, M): call XX,,,X,-,,,,,, satuurate M=M,, ed_mtx Y, E, M, M2), SatID): :- call(x, Y, E,M, M-).M=M,, sat Sant..d(SaaII)) saturate. ed_mtx( Y, M, M2), SatID): culll(u0, Y, K. M2), sat_id(SatID), saturate. :-not saturate.
Other required constraints to learn sensible HRMs are shown below. The first rule prevents an edge from being labeled with calls to two different RMs. The second rule prevents edges from being labeled with the same literal both positively and negatively.
call (x, Y, M, M2), call(x, Y, E, M3), M2!-M3. ]
(X (X, Y, E, M, nXg Y, P)
The following constraints are used to speed up the learning of an HRM. First, we extend the symme-- try breaking method by Furelos- Blanco et al. (2021), originally proposed for flat RMs, to our hier- archical setting. The main advantage of this method is that it accelerates learning without restricting the family of learnable HRMs. Other constraints analogous to those in previous work (Furelos- Blanco al. 2021) that speed up the learning process further are enumerated below. For simplicity,
34

---

Under review as a conference paper at ICLR 2023
some of these constraints use the auxiliary rule below to define the ed E, M) predicate, which is equivalent to the call(X, Y, E, M2) predicate but omitting the called RM:
ed(x, Y, E, M): call E,
The constraints are the following:
Rule out inductive solutions where an edge calling the leaf MT is labeled by formula formed only by negated propositions. The rule below enforces proposition to occur posi- tively whenever a proposition appears negatively in an edge calling MT.
neg(X, Y, E, M, -), not poa(X, Y, Y, -), call(X, M,MY).
Rule out any inductive solution where an edge from X to Y with index E is not labeled by positive or negative literal. This rule only applies to calls to the leaf MT, thus avoiding unconditional transitions.
not (X Y,E,M, not neg(x, Y,E, call(X, Y,E,M,
Rule out inductive solutions containing states different from the accepting and rejecting states without outgoing edges. In general, these states are not interesting.
-x has www.oooog..eeeeeeeeeoee ed :- (X, M), not has_aaassoaaaa bas_onng edges (), X!=u ,.,,,,!-ll X!-uR.j
Rule out inductive solutions containing cycles: that is, solutions where two states can be reached from each other. The pXah(X, Y, M) predicate indicates there is directed path (i.e., a sequence of directed edges) from X to Y in RM M. The first rule states that there is path from X to if there an edge from to Y. The second rule indicates that there a path from X to Y if there is an edge from X to an intermediate state Z from which there is path to Y. Finally, the third rule discards the solutions where and can be reached from each other through directed edges.
path(X, Y,M) ed Y, M).
path(X, Y, M) ed Z, M), path(2, (2, M,M). --ppaah x, Y, M), pat
F EXPERIMENTAL DETAILS
In this section, we describe the details of the experiments introduced Section We discuss how the domains implemented, the hyperparameters used run the algorithms, and provide all specific results through tables and plots. All experiments ran on 3.40GHz Intel TM i7-6700 processors.
F.I DOMAINS
The CRAFTWORLD domain is based on MiniGrid (Chevalier-Boisvert al. 2018), thus inheriting many of its features. At each step, the agent observes W x H x 3 tensor, where W and Hl are the width and height of the grid. The three channels contain the object IDs, the color IDs, and object state IDs (including the orientation of the agent) respectively. Each of the objects we define (except for the lava which already existed in MiniGrid) has own object and color IDs. Before providing the agent with the state, the content of all matrices is scaled between -1 and 1. Note that even though the agent gets a full view of the grid, it is still unaware of the completion degree of a task. Other works have previously used the full view of the grid (Igl et al. 2019 Jiang al. 2021).
The grids are randomly generated. In all settings (OP, OPL, FR, FRL), the agent and the objects are randomly assigned unoccupied position. In the case of FR and FRL, no object occupies position between rooms nor its adjoining positions. There is a single object per object type (i.e., proposition) in OP and OPL, whereas there can be lava location in OPL, which is randomly assigned (like the rest of the propositions), whereas FRL there four fixed lava locations placed in the intersections between doors shown in Figure 9
two per type in FR and FRL. Finally, there is a single
35

---

Under review as a conference paper at ICLR 2023
Figure 9: An instance of the CRAFTWORLD grid in the FRL setting.
OQ
Figure 10: An instance of the WATERWORLD in the WOD setting TTroo Icarte et al. 2018)
The WATERWORLD domain (cf. Figure 10p has continuous state space. The states vectors containing the absolute position and velocity of the agent, and the relative positions and velocities of the other balls. The agent does not know the color of each ball. In all settings (WOD and WD), WATERWORLD instance is created by assigning random position and direction to each ball. Like in CRAFTWORLD, the agent does not know the degree of completion of task.
F.2 HYPERPARAMETERS
Table 2 lists some of the hyperparameters used in the experiments. The rest of the hyperparameters and other details (e.g., architectures, evaluation of other methods) discussed in the following paragraphs.
Architectures. The DQNs for CRAFTWORLD consist of 3-layer convolutional neural network (CNN) with 16. 32 and 32 filters respectively. All kernels are 2 x 2 and use stride of 1. In the FR and FRL settings, there is a max pooling layer with kernel size layer. This part of the architecture is based on that by Igl et al. (201)) and Jiang et al. (2021). who also work on MiniGrid using the full view of the grid. In DQNs associated with formulas, the CNN's output is fed to 3-layer multilayer perceptron (MLP) where the hidden layer has 256 rectifier units and the output layer has single output for each action. In the case DQNs for RMs, the output of the CNN is extended with the encoding of the RM state and the context (as discussed in Appendix C) before being fed to a 3-layer MLP where the hidden layer has 256 rectifier units and the output layer has single output for each call in the RM.
2 after the first convolutional
The architecture for WATER W ORLD is a simple modification the one introduced by Toro Iearte et al. (2018). The formula DQNs consist of 5-layer MLP, where each of the 3 hidden layers has 512 rectifier units. The DQN for the RMs share the same architecture and, like in CRAFTWORLD, the state from the environment is extended with the state and context encodings.
36

---

Under review as a conference paper at ICLR 2023
Table List of hyperparameters and their values.
Parameter
CRAFTWORLD
WATERWORLD
General
Episodes
300.000
300,000
Maximum episode length
1.000
1,000
Num, instances
DQNs
Learning rate
5
-4
1 10-5
Learning rate (SMDP) a
5
m4
Optimizer
RMSprop Hiinon et al.
2012
RMSprop Hiinton et al.
2012
Discount y
0.3
0.9
Discount (SMDP)
0.99
0.99
Updated formula Q-fumctions per step
4
4
Replay memory size
500,000
500,000
Replay start size
100,000
100,000
Target network update frequency
1,500
1,500
Replay memory size (SMDP)
10,000
10,000
Replay start size (SMDP)
1,000
1 1,000
Target network update frequency (SMDP)
500
500
Minibatch size
32
Exploration
Initial exploration
1.0
1.0
Final exploration
0.1
0.1
Annealing steps
2,000,000
5,000,000
Annealing steps (SMDP)
10,000
10,000
HRM learning
Curriculum weight Ø
0.99
Curriculum threshold
0.85
0.75
ILASP time budget
hours
2 hours
Num. collected goal traces (height 1)
25
25
Num, collected goal traces (height 2-2)
150
150
Num. goal traces to learn first HRM
10
10
Compression. Akin to some methods for learning RMs (Furelos- (Furelos-Blanco et al. 2021 Toro Iearte ct al. 2019), we compress label traces by merging consecutive equal labels into single one. For [w}) becomes (f), (0) f}. (+), [w}).
instance, (O) (D), (2). (). (+),
The average undiscounted returns (see Section 5 and Appendix D updated for each task instance pair every 100 training episodes using the undiscounted return obtained by the
Curriculum.
greedy policies in single evaluation episode.
Flat HRM Learning Methods. We briefly describe the methods used to learn flat HRMs. Each run consists of 150,000 episodes, and the set of instances is exactly the same across methods. The difference with respect to learning non-flat HRMs is that there is single task for which the HRM learned. Our method, LHRM, is therefore not able reuse previously learned HRMs for other tasks; however, it still uses the same hyperparameters. In the case of DeepSynth (Hasanbeig et al., 2021. LRM LRM (Toro Icarte al., 2019) and JIRP (Xu al. 2220), we exclusively evaluate their RM learning components using traces collected through random walks. For a fair comparison against LHRRM (both the non-flat and flat learning cases), we (i) compress the traces using the aforemen- tioned methodology, and (ii) use the OP and WOD settings of CRAFTW ORLD and WATER W OORLD respectively, where observing goal traces is very easy for simple tasks such as MILKBUCKET. In these approaches, different instance is selected each episode following cyclic order (i.e., 1. I.....-1,, 1, The set of propositions in these approaches includes proposition covering the case where other propositions are observed (if needed). In the case of LRM. of the pa- rameters is the maximum number of RM states, which we set to that the minimal RM. Finally, we modify DeepSynth to avoid periodically calling the learner (i.e., only call it when counterexample
37

---

Under review as a conference paper at ICLR 2023
trace is observed): this is not done in other approaches and usually causes timeouts unnecessarily (the same RM is repeatedly learned)
ILASP. We use ILASP2 (Law et al. 2015) to learn the HRMs For efffcciency, the default calls to the underlying ASP solver are modified to be made with the flag that non-minimal solutions might be obtained (i.e., solutions involving more rules than needed), so the learned root might contain some unnecessary edges. In practice, the solutions produced by ILASP rarely contain such edges and, if they do. these edges eventually disappear by observing an appropriate counterexample. We hypothesize that using this flag helps since no optimization is made every time ILASP called. The design of the ILASP tasks is discussed in Appendix[E.2 We highlight that this notion of minimality is not related to that of minimal RM (i.e., an RM with the fewest number of states) described in Section
mope- meaning
F.3 EXTENDED RESULTS
We organize the tables and figures following the structure in Section 6
Policy Learning. Figure TT shows the plots omitted in the main paper (the remaining CRAFT- WORLD setting, FRL, is shown in Figure 2). The number of plotted episodes varies across domains and tasks for clarity. Figure T shows the learning curves for a task called TENPAPERS, which con- sists of performing PAPER total of 10 times |]] The plot shows that exploiting the non-flat HRM leads to much faster convergence than the equivalent flat one. The difference arises from the fact that the non-flat HRM can reuse the policies for the called PAPER RM, whereas the flat one cannot.
Learning Non-Flat HRMss We present tables containing the results for the HRM learning compo- nent of LHRM. The content of the columns is the following left-to-right: (1) task name; (2) number of runs in which at least one goal trace was observed; (3) number of runs in which at least one HRM was learned; (4) time spent to learn the HRMs; (5) number of calls to ILASP made learn the HRMs; (6) number of states of the final HRM; (7) number of edges of the final HRM; (8) number
of episodes between the learning of the first HRM and the activation of the task's level: (9) number of example traces of given type (G goal. D = dead-end, I = incomplete); and (10) length of the example traces of a given type. In addition, the bottom of the tables contains the number of com- pleted runs (i.e., the number of runs that have not timed out), the total time spent on learning the HRMs, and the total number calls made to ILASP. In the case of CRAFTWORLD. Table 3 shows the results for the default case (all lower level RMs are callable and options are used for exploration), ssows the results when the set of callable RMs contains only those actually needed, and Ta- ble shows the results using primitive actions for exploration instead of options. Analogous results are shown for WATERWORLD in Tables 6 and g The discussion of these results can be found in Section 6
Learning Flat HRMs. Table 9 shows the results of learning a non-flat HRM using LHRM, and the results of learning flat HRM using several approaches (LHRM, DeepSynth, LRM and JIRP). An extended discussion of these results can be found in Section 0
G EXAMPLES OF HIERARCHIES OF REWARD MACHINES
Figures 14 and 15 show the minimal root RMs for the CRAFTWORLD and WATERWORLD tasks, respectively. In the case of CRAFTWORLD, since two or more propositions can never occur si- multaneously, the mutual exclusivity between formulas could be enforced differently. These RMs correspond to the settings without dead-ends; thus, they do not include rejecting states.
"The code of these methods is publicly available: DeepSynth ttttps:://gttubbbccomm wtt.://///g.ociii.oo deepsynth MIT license), LRM com/ wtt.///orazaaaaaaa http///aaaaaaaccaaaaaaaaaaaa ieteettiiireeerree www.erewwwrddaaaeee wwwhewawadddaaaaesseeeeeaeeeeeee no license). The first two links can he found in the papers, whereas the last one was provided by one of the authors through personal communication.
no license), and
JIRP petttp:://githie
"ILASP free to use for research and education (see wwtpthttp////. //www. laap. com/terms).
Disclaimer: At the time of writing this revised version ( (November 10), this experiment consisting of 5 runs has not finished. However, confident the observations have made still will hold when it is completed.
38

---

Under review as a conference paper at ICLR 2023
BOaRQumr
CAKE
0.8
Averaeg EX5127
Awrage méllimm
0.6
3.6
0.6
Average
0.4-
3.4
0.4
Nor. Fla
Non UT
Noc, 200r
Flat
0.0
0.0
2.0
4.0
6.0
8.0
36.0 x
3.0
300
2.9
4.0
5.0
5.0
10.0
0.0
2.0
2.0
10.01
8.0
10.0
Namnber of episodes
Number of epánodes
X
Numbor of epteodes
X10
(a) CRAFTWORLD OP
MiceBuckaer
BOOKQUmn
CANE
1.0
0.8
Awaapp 14/107
0.8
3.6
0.6
Avsage
Anragg
0.4
2,4
0.4
0.2-
Nor. Pla:
3.2
Noo Ulat
0.2
Noc Plac
Flat
Flud
Flat
0.0
2.0
4.0
800
10:0
3.02
2.3
4.1
5.1
10.0
1000
2.0
4.1
8.11
10.0
Number of episodes
Number of eposodes
Numbor of epicodes
X110
(b) CRAFTWORLD OPL
BoOkQUiLE
CAKE
1.0
1.0
1.0
0.8
3.8
0.8
Aneage 1att
Aweage 1-4um
0.6
Ancage
0.4
2,4
0.2-
3.2
Noo
0.2
Flat
Flat
Flat
0.01
000
Nomber of episodes
x100
Number of episodes
Number of episodes
(c) CRAFTWORLD FR
nem&&emay
1.00
0.8-
3.8
0.8
Aveage 1iiths
Aveage edmum
0.6-
366
0.6
0.4
0.2-
Nac-Fla
3.2
0.2
Fldt
0.31
2.0
1.0
300
10.0
000
110
60
8.0
Number episodes
Number episodes
Number episodes
(d) WATERWORLD - WOD
0.5-
3.8-
0.88
Average wiun
0.5-
ZU6
RUG
Average
0.4-
Nac-Fao
Noo-Bla
Nocs Plee
0.0
5.0
16.0
15.0
200
3.0
5.0
10.0
20.0
0.0
0.0
5,0
10.0
15.0
Nomuber of epieodes
110
Number
Numble espbeode
(e) WATERWORLD WD
Figure 11: Learning curves comparing the performance of handcrafted non-flat and flat HRMs.
39

---

Under review as a conference paper at ICLR 2023
Table 3: Results of LHRM in CRAFTWORLD for the default case.
(a) OP
Tisk
PG
LL
Time (s.)
Calls
States
Edges
Ep. First HRM
Examples
Example Length
(x:10)
BATTER
11.1 (1:7)
(1.9)
5.0 (0.0)
5.2 (0.2)
1.8 (0.1)
12.2 (0.7)
11.6(1.4
(2.1)
(3.2)
BUCKET
5
0.9 (0.0)
3.6 (0.2)
3.0 (0.0)
2.0 (0.0)
1.7 (0.1)
10.0 (0.0)
1.6(0.2)
(1.1)
(9.7)))7)
COMPASS
5
(73.3)
(1.6)
5.0 (0.0)
5.2 (0.2)
1,8 (0.2)
11.8 (0.6)
12.8
26.7
(2.8)
LEATHER
(0.0)
3.0 10.2
2,000.0)
1.8
16.7
(7.9
PAPER
(0.1)
(.60).)
10.0 (0.0)
QUILL
(3.5)
(9.8
5.0 (0.0)
(.22)
(..1
(0.4)
12.6(1.1)
(2.5
(1.2
SUGAR
S
0.8 (0.1)
(.2)
3.0 (0.0)
(.0)
(.2(0.2)
(0.0)
1.2
17.7
(3.5
BOOK
5
(36.4)
22.8 (2.6)
5.0
588
6.0.
(0.7
17.4
(1.5
21.51)))
$49.4 (149.5)
27.2
(1.7
(0.2)
(04)
6..)
10.0
2.610.4)
11.
BOOKQUILL
17.9 (1.4)
19.6
4.0 (0.0)
4.0
3.8
(0.0
16.6
(1.3
20.8 (1.4)
MILKB.SUGAR
7,3
(1.2
4,0 (0.0)
(.0
(.8)
(0.2)
9.2.1.2
(0.9
(1.7
CAKE
74.5 (25.7)
26.4 (3.7)
4,0
(0.2)
2.1 (0.1)
(0.2)
(3.2
38A (0.9
22.7
Complesed
Toxal Time (s))
8009.8 (122.3)
Total Calls
189.4
(b) OPL
Tisk
FG FL
Time (4,)
Cals
Steee
Edges
Ep. Finst HRM
ExEamples
Exampl: Lenath
[XIUP)
13
BATTER
(1.4
7011.2)
(1.1)
1.8
(.2
K0.0..5
2.2
238
(1.9
(1.7
21.0
10.4(1.4)
11.0.0.6)
10.2.1.0
20.9(199
(4.3
LEATHOR
1.9.0.2)
7.000.5)
4.0 (40)
6.9.0.5))
10.00000
2.4 (12))
2.6 00.40
16.9
89(3.))
PAPER
2.0.0.21
3.6
4.0.00)
7.2(1.1)
10.00.0)
30:00:3
26.00-)
10.1 (0.5
189
S6.088)
QUIEL
11.343.2)
22.0
60.00)
9.2 (.25
128(1.5)
(0.60..)
64 64:00.)
(1.0.09)
(5.3)).)
(3.
(2.1(1.)
SUGAR
1.7
(0440
1.:00.)
(..0
6.3
10.0
2.4 (0.2)
20
9.6
(33
(66
BOOK
427.8 51
(2.6
6.:000)
6,6 (0.2)
5..0.2)
(2.0
36 (27)
(3.4
21.61.55
(344
23.71.3)
MAP
641.9:310..7
(3.6
68 (0))
64 (0.2)
5..02.)
11.2:0.4)
38 (0.0)
23.6
11.0
(4.6
26.1 (U4)
MILKBOCKET
2.1.0.2)
(0.4
49 (00)
3.0 10.0)
7.6
10.0.0.0)
14.0.4)
2.0 2.000.0
11.1 10.5)
26.3 (6-5
(5.
BOOKQUILL
(2.3
(6.61.3)
40.00))
4.0 (005
6.2)0.7)
(0.0000))
04:00))
(52.414)
622.5.))
218(1))
KR
1.7.0.7)
(1:3.0.9)
(0.00)
(00))
(..00.7)
(0.00.0)
03300-7)
90:00
160 (0.)
16:1
(6.3(13)
473.9(216.6)
(6.0
50.000)
(0.3)
2.000.0)
(0.0
(.6(0.4)
(5
59.5 (1:7)
(8
(0.)
Compleced (s)
1622.6 (338.7)
(c) FR
Task
#G
Time
Calls
States
Edges
Ep. First HRM
Examples
Example Length
(x10P)
BATTER
5
(1.7
(1.3
5.0.0.0)
5.4 (0.2)
(12(1.2)
11.6 (1.440)4)
(1.0
(0.3
(2.0
BUCKET
S
1.2 (0.1)
(0.2)
3.0(0.0)
2.0 (0.0)
6.7 (0:9)
10.0 (0.0)
(0.2)
16.6(2.5)
28.5(4.))
COMPASS
14.1
(1.7
5..00.0)
(0.2)
(..)
11.6 (0.6)
14.6
26.5 (0.8)
26.5
LEATHER
3.6(0.2)
(0.7)
PAPER
1.2 (0.0)
(.0(0.0)
30:00.)
2.0 (0.0)
(.9.
10.0 (0.0)
2.0
12.40.1)
(0.9
QUILL
8.9 (0.9)
(6.0
5.0(0.0)
(.2
9.4
10.6 (0.2)
(1.4
25.4
22.5
SUGAR
(.,)
30.00.0
2..0
10,0 (.3)
(.2))
(1.3
21.0(10.1)
(0.)
(0.2)
MAP
628.3 (85.4)
(3.7)
50.00)
(0.)
(.1)
1000 (0.0)
(3.7)
26.4(1.0)
21.(0..)
MUCKRUCKET
1.9 (0.2)
(...).
3..000)
(00)
(0.7
10.0 (0.0)
(..)).))
(0.7)
(2.
BOOKQUILL
12.9 (2.2)
(1.6
4.000.0)
4.0
(.91).1)
10.0 (0.0)
(2.6(1.)
29.0
(3.3
MILKB SUGAR
7,2
(2.0
4.000.0)
(.00
(.9.
9.0
(0.9)
(1.1
121.1 (41.1)
(4.8
(.0
(0.0)
(0.0)
(4.8
(2.2
(62
Completed Runs
Total Time (5.)
1031. (150.3) (11.3)
Total
(d) FRL
Time
Fixt HRM
Examples
Exaupl: Length
[XX0P)
D
RATTER
(1:341.4)
(2.5)
6.0 (1)
9.7 (0.2)
668.4 9)
10.4 (0.2)
76.009)
11:4(1)) 9)
11.9100)
(1.1 (1:3)
(9
RUCKET
2.5
7.010.33
4.0 (01))
4.0 (0.0)
128.5 (60
(0.2)0.)
2.5 (1.)
2.000.5 5)
7.5 (0.5)
99 7:
6.42.1)
COMPASS
(3.0(1.9)
24.5
5.0 (01)
9.4 (0.2)
35018
10.4 (0.2)
12.(112) 7.8(1.))
12.
9.4
(.5)
LEATTHO
2..00
7.840.T1
4.0000)
3.9 (0.0)
88 88.0111.00
10000.00
32 (0.4)
26
73
93(117)
(7
2.200.11
7.010.3)
(18.8)
10.0.0.0
20.00:1
(.9)0.)
47.72.1
QUILL
(1,6(11)
23.5
(0.6(0.)
112(122
11.90.))
(2.7)
2.700.21
(39.5)
10.00.00
366
23(0.5)
82.00.)
(0(1
(158.2)
5.5022)
35..2.3)
224
MULKBUCKET
2.8.0.1)
(0.3
6.900.3)
10.0.0.0)
20:000
26:0221
(3.1
7.(22.2)
BOOKQUILLL
(9.9)29)
(1
4.3(0.1)
(0.000.0)
0x
(58(1.2)
26411.1)
22
135
MILKB. SUGAR
6.690.9)
(1.6
4.0 4.0.0.0)
4.0 (0.0)
4..00.)
10.0
(..5
(.70
(1.3
(2.72.0
CAKE
344.0(87.77 (87.7)
(4.9)
5.0 (.)))
4 (0.2)
28(0.1)
10.0
2.8 (0.7)
40.4
44.5 (2.3)
21.2
(1.0
Completed Rum
Toeal Time (s.
14.68 (175.3)
Toral Calle
(6.5)
40

---

Under review as a conference paper at ICLR 2023
Table 4: Results of LHRM in CRAFTWORLD with restricted set of callable RMs.
(a) OP
Task
Time
Calls
States
Edges
Pirst HRM
Examples
Example Length
[x10P)
BATTER
(1.6
17.8(19)
(.D0
5.2 (0.2)
(0.1)
(2.7(
(1.6((.4)
(2.1(2.1)
(3.2
BUCKET
0.9 (0.0)
3.6(0.2)
3.0
2.0 (0.0)
1.7 (0.1)
(0.0
(.6.0.2)
(9.1)
(9.3
COMPASS
184(166
50:0000
(0.)
0.9 (0.8)
38:002)
30:00:0
2.0 (0.0)
10.0000)
(.2)
(1.7
(7.9.44))
PAPER
0.9 (0.9)
3.4022)
3.
2.0 (0.0)
1.5 (0.1) (0.0
(.4.).2
(2.0)
(2.00
QUILL
0.8 (3.5)
(9
5.0(0.0)
(0.2)
(..1
(3.2
(2.((1))
(2.5
24.4
SUGAR
30:0.00
(.7.
(.2.).2)
BOOK
19.6:09)
5.000.00
6.000.2)
(1.2(())
21.(1.8)
21.0(1.)
MAP
64.1 (10.6)
22.0.2..)
5.0(0.0)
(.2)
60.2
(0.3
(2.2
22.5(1.))
23.0
MOLKBOCKRT
1.2 (0.1)
(04)
3.(00)))
2.0 (0.0)
6.8
10.0
24(04.4)
12.1 (0.7
(5.3(16)
BOOKQUILL
4.5
(1.2(14)
4..00.0)
(.0)
(..)
10.0
(.2.1.4)
26.1
22.4
MILKB. SUGAR
4.000.0)
6.4(1.2)
(0.5)
CAKE
9.1 (0.9)
(7.9
(.0
(.2)
(..1
(0.0
(1.0
(1.9
(8.9
Completed Runs
Total Time (x.)
176.6(13.1)
Tonal Calls
(3.66
(b) OPL
(4)
Statss
Edges
Ep. Finst
Examples
Example Length
[x:10)
(3.0
20.4(1.1) 1)
BUCKET
(0.3)
0.20
4.0
10.5
10.2 (0.2)
2.2(0.2)
(0.5)
13.411.9)
6.80.77
COMPASS
15.2
22.0(.7))
6.010.0
10.4
(1.0
5861.0
10.2:1.00
17:2(1.)
11.911
(4.3
LEATHER
1.9.0.0)
7.000.5
4.000.0
4.000.0)
6.900.5)
(0.0(00))
2.400.2
26600.4)
(0.9)
3.9.33)
PAPER
2.0
7.6.0.5)
4.000.0)
40:00:)
(17
(0.0000)
3.000.5
26:0044
(0.))
(89
5.6
QUILI
(1.5
22.0(1.2)
6.000.0)
9.2 (.23
(1.8
(0.6
64.07
110:09%)
153(113
13.5
(2.104)
SUGAR
1.5
6.4.0..)
4.000.0)
4.200.0)
6.570.7)
(0.)
20.22.2
2.000.3)
9..(0.))
15.3
16.6.922
BOOK
(9.0
22.8
6.010.0)
6.2 (0.2)
3.5
(0.4
5.2
12.2(19)
20.4(1.3)
21.2
2080.3
MAP
76.5 16.0)
24.20.3)
6.010.00
6.4 (0.2)
5.7
(1.6
(.0
14.6:1.00
26.0
21A12.1)
25.7
MILKBUEKET
1.7 (.2.0.2)
6.0.0.6)
4.000.0)
30.00.1
7.540.7)
(0.2
(..0))))
2:400.)
(1.700.)
25.4
14200
BOOR HLL
5.3.0.9
(0.(1.4)
40
40:00.1
1.7
100-00)
1.005)
6.8.0.9
21.7.1.0)
(1:2
21.10.
MILKB SUGAR
4.0.00.9)
(..7
4,0 (0.0)
4,0 (0,0)
3.8 (0.1)
1000 (00)
(.67
5221125
(8.7007)
8,3
(5.60.7)
CAke
16.2 (0.4)
20.5 (0.2)
3.0 (0.0)
3.0 (0.0)
2.1 (0.1)
10.0 (0.0)
3.2 (0.2)
14.6.10. (..)
38.1 (0.))
22.5 22.3
(33)
23.7
Completed Runs
Tocal Time 5.)
2186 (21.1)
Tocal Calls
1886 (5.4)
(c) FR
Task
L
Time (s.)
Calls
States
Edgas
Ep. First HRM
Examples
Example Length
(x10P)
G
G
BATTER BOCKET
12.6
(1.6 3)
5.0
(0.2)
(1.2)
(0.6
(1.0
30.3 (2.3)
(2.0)
1.2 (0.1)
3.0
(0.2)
COMPASS
14.1 (1.5)
20.2(1.7)
5.0
5.2 (0.2)
9.8 (0.7)
(1.6(0.))
(4.6(1.2)
(6.5
(2.1
LEATHER
(0.1)
3.6(0.))
3.0
2.0 (0.0)
4.5
10.0
(0.))
(1.3
(6.7
PAPER
(.1)
4.0.00))
2.0 3.000.0)
4.9
10.0
20.00.0)
(2.4
10.9
QUILL
25.4 (0.3)
SUGAR
(0.2)
3.8(02)
3.0
2.0 (0.0)
5:2 (0.3)
(0.0
(0.2)
(1.7
21.0(1011
BOOK
(13.0)
20.0(19)
(.0)).0)
5.4 (0.2)
(.11
10.0
(6.9
21.9
(1.(4))
MAP
(13.4)
22.2(2.5)
(.D.0..)
(0.2
5.9 (0.1)
(0.2
(2.6
26.5
(82(112)
BOOKQUIL
6.3 (0.9)
1322(17)
40(00)
4.0 (0.0)
3.8 (0.1)
10.0
(1.7
32.6
(1.9
MILKB. SUGAR
4.8 (0.6)
(18
4..00.)
4.0 (000
3.8 (0.1)
(0.0
(1.3)
19%
(6
CAKE
12.5 (1.8)
(2.5
(..00.0)
3.0 (0.0)
2.3 (0.1)
(0.0
17.8 (2.5)
44.2
13.1 (1.2)
Completed
Total Time (s.
194.9 (17.6)
Total Calls
(7.0)
(d) FRI.
Took
KG #1.
Time (6))
Calls
Sttrs
Felgen
Fp. First HRM
4 Foumples
Promple lingth
[x:102)
G
BATTER BUCKET
11:2(1.4)
(2.5)
6.0v0.t)
(0:2)
(0.2)
(.600.9
(1.4(1.)
(0.9
(1.3)
(0.)
2.4(0.1)
7.000.3)
4.0(0..0
4.0(0.0)
129.5:59.41
2.800.))
2..00.3)
7.8
9.9(1.7)
(-11211
COMPASS
(3.1
24.6 2-22
6.0
(0.2)
550.8
(0.2)
7
(1.2)
12.5
9:4(1.0)
(0.5)
33.8:1.5
(3.1
26:00.2
8.4.0.)
4.000.0
4.000.00
10.00
36.(0.4)
5.0.D
BOOK
61.21322
27.1222)
6./0..0
6.2)0.2)
(0.2)
56.00)
176:117)
25.(1.00
(2.0020)
(1.00.0))
MaP
(21.5
34.0
6.v0..
(0.2)
(0:3)
68(07)
250:2.4)
26.20.71
(69(1.6)
(4.)00))
MILKBOCKET
2.7
6.6 (0.)
4.000.00
3.010.00
(1.3)
10.0-0.0)
21(02.)
24:004)
(2.3
9.4
93
BOOKQUULL
(.3))
12.6 (0.))
4.0
4.0 (0.0)
4.4 (0.2)
10.0
(.6)
80:00.3
(2.3
(9
(1.(
MILKB SUGAR
12.2 5.440.6)
4.000.00
4,0 (0.0)
4.0 (0.3).3
10.2 (0.2)
(.0(0.)
$0:004)
(1.7
29(1.)
(1.3
CARE
16.341.2
21.2/1.0)
5.000.0
4.0 (00)
288 (0.0)
10,0 (0.00
2..02.2
15
(1.9
(5.0
(..)
Complnaa Rans
Texal Time (s)
270.1 (34.6)
Toull Calls
216.0 (5.1)
41

---

Under review as a conference paper at ICLR 2023
TENPAPERS
1.0
0.8-
Averago return
0.6
0.2-
Non-Flat Fla:
0.0
0.0
3.2
0.5
0.8
1.0
Number of episodes
x10
Figure 12: Learning curves comparing the performance of handcrafted non-flat and flat HRMs in the TENPAPERS task (FRL setting).
Table 5: Results of LHRM in CRAFTWORLD without exploration using options.
(a) OP
(s.)
Edges
Ep.
Examples
Example Length
(x10*)
G
BATTER BUCKET
5
5
11.2
(7.8(1.)
(.D.)
5.2 (0.2)
1.:00.1)
12.2 (0.7)
11.6
26.5 (2.1)
(3.2
5
5
0.9 (0.0)
(6.2
(..00.
2.0 (0.0)
1.700.11
(0.0)
1.6.00.)
19.4(1.))
(5.7))
COMPASS
18.6(166
(.0.)..))
(.2.0.2)
(0.6)
(1.8
28.7
20.3
0.9
3.8(0.2)
(0.0)
1..00.1)
(6.7
PAPER
5
0.9 (0.1)
3.4(0.2)
3.0
2.0 (0.0)
1..00.1)
(0.0
1.4
(2.0
40.6 (27.0)
QUILL
5
18.3 (3.6)
(9.8(1.2
5.0
(.2)
2.1
13.2
12.6
29.6
21.4
SUGAR
5
0.9
3.2(
30.00.0)
200 (0.0
1.700.2
(0.0
1.2.002)
(7.7
(3.5
BOOK
$29.0 (164
21.2(1.4)
5.0.0.0)
(0.2)
6.8(0.2)
10.2
17.0
33.0
13.7
23.6
MILKBUCKET
1.6 (0.2)
(040
3.000.0)
(0.0
6.1.0.3)
10.0
2.4
16.01.0)
(4203))
QOOKQUELL
(20.))
(3.6
(.000.0)
4.0 (0.))
6..00.2)
10.0
21.6
(2.7
21.2
MIL KB. SUGAR
8.1 (0.8)
(1.0(
(0.00.))
4.0 (0.0)
49.0.11
10.2 (0.2)
8.6
31.1 (0.7)
13.1 (08)
CAKE
198.3 (47.5)
(3.0
(.000.0)
3.8 (0.2)
5.5.0.2)
(0.0
(5.0
65.0
22.0
Completed Runs
Toxal Time (s.
2752.8 (503.2)
Total Calls
203 (11.8)
(b) OPL
Tisk
GG
AL
Time (6.)
Calls
Suies
Edges
Ep. Fast HRR
A Examples
Esampl Length
[x:1))
G
BATTER
(1.0
7.0(1.2)
(1.6)
BUCKET
(0:3)
2.2(0.2)
(0.5)
6.(1.7)
22,0:17)
4.000.00
10.010.0)
59
4.000.00
10.010.0)
(0.)
5.6
1188113)
220:11::
6.000.0
(1.5
10.5:0.2)
(.))
(3.3
13,5
12.14.4)
SIIGAR
16:00.1
64:004:
4.-0..
40:00.0
6.5 (0.7)
(0.)
24(00.)
20:00:
9..00.5)
(5.5(3.)
(66
ROOK
(24.6
2700:19
6.000.00
6.4 (..)
(30.7(218)
(0.)
3.2(04)
182(14:
22.5
24.766.5
23.
MAP
(33.9
33.0.2.8)
6.000.00
6.4 (..0
2048(27.5)
(0.2
28:03)
256:2.5)
25.4
21.83.1)
252(1.1)
MILKBOCKET
3.5
8.2.066)
4.000.00
3.000.00
(7.6
10.2 (0.2)
2.(044)
3.4.0.)
(0.3
16.(
14.(
BOOKQU QUTLE
190/2.2)
154:1
40/0.0
40:0000
(83.6
10.0 (00)
10:00.)
114:1
38.21.86
(4.1
218(1.0)
Mit KR SUGAR
1144221)
144:1.7
48/0.0
40.0000
(8.9
10.4 (0.))
1.0:0.4)
100:1 9
(1/7
k.744.)
176(12)
Cake
237.4/0.8)
(00)
5.000.0
40.000)
264. (0.0)
10.0 (0.0)
2.000.0)
38000000
46.7 (0.0)
36.0.0.0)
22.9
Complesed Runs
Tooal Time (5)
(L11
Tocal Calls
1998 (6.5)
(c) PRI
#1.
Calls
Falges
Fini HRM
Fasmples
[x11FF
BATTER BUCKET
(1.4
(3.4
6.000:00
00.2
468.4
(0.4
7.6(0.9)
11,4
119900.0
(0.1
9.910.4)
2.2 10.11
20:00.3)
4.0.0.00
(..00
129.5 (69
10.2
2.8(0.2)
2.0.0.3)
73.00.5)
9.9(1.7)
(.41
COMPASS
(1.9
266-
6.0
9.4 0.420.2)
590.8
(0.4
7.8(1.0)
(1.4
12.5(1.6
9.4(1.)
(.4
LEATHER
2.8 (0.4)
73:00.7)
4.000.00
4.0
(180
10.00.00
3.2
(.6.0.4)
733004)
9.3(1.))
37 37.00.)
PAPER
5
2.1 00.31
7.200.3)
40.00.00
4.00000)
$2.7 (18.5
10.00.00
3.0.000)
2.0
6.910.7)
102(1.5
4.
QUILL
5
11.6
(1.5
6.0.0.00
9.6(0.2)
458-966110)
10.6
$.0(0.))
11.2
11.910.61
(2.1
0.1.0.55
SUGAR
5
00.3)
8.4 (1.3)
40.00.00
4.00000)
103.5 (39.5
10.0
3.6(0.4)
2.800.5)
8.2.0.7)
(1.5
5.((L.)
Book
0.0 (0.30
BU (1.0)
0.0 (0.00
(.0
(.0)0.))
0.0
0.0
(.0)
0.000.5)
(US
1.000.00
MAF
0.0 (0.3)
[02 (0.0)
0.0 (0.00
(.0
(.0
0.0
0.0(000)
(.0
0.000.0)
(U0-0.0)
1.000.00
MILKBUCKER
4.7 (0.5)
(1.0
4.0 (0.00.0
(.0
(142.)
10.0
2.0(0.0)
7.0
$2.00.4
(0.21.7)
(.3
QUILQ
0
0.0 (0.0)
0.0 (0.0)
0.:00.00
0.0
0.0
0.0
0.0(0.0)
0.000.00
0.:00.0
0.000.0)
0.000.00
AhL.B.SUGAL
0
0.0 (0.30
D0 (1.0)
0.0 (0.00
(.0
0.0-0.)
0.0
0.0 (QU)
(.00
(.:00.5)
0,0 (UC
0.0 (0.0)
CAKE
0.0 (0.30
00 (1.0)
0.0 (0.0)
0.0
(.000.))
0.0
0.0 (QU))
0.0 (00)
(..00.))
000 (0,0)
0,0 (0.0)
Complated Rans
Total Tine
(7.1
Total Calls
1064 (2.99)
42

---

Under review as a conference paper at ICLR 2023
Table 6: Results of LHRM in WATERWORLD for the default case.
(a) WOD
Task
#G L
Time (5.)
Calls
States
Edges
Ep. First HRM
# Examples
Example Longth
(x10")
G
RG
0.9 (0.0)
4.0 (0.0)
3.0 (0.0)
2.0 (0.0)
0.9 (0.1)
10.0 (0.0)
2.000.0)
(1.0)
(.8(1.1)
(0.1)
3.8 (0.2)
3.0 (0.0)
2.0 2.0.(..0)
0.8 (0.1)
10.0 (0.0)
1.8 (0.2)
10.8 (0.8)
(1.9
(.0)
2.0
6.6(1.9)
RGRAC
(0.3)
13.4 (0.4)
(..0)
(.00
11.8 (.3)).3)
8.6)
(2.2
(4.8
BC&MY
5.8(100)
(..0) (2.1)
4.0
8.1)
12.8 (1.3)
9.8(1.5)
13.2
(1.6
RGRMY
(3.2
RGB
1.2 (0.1)
4.8 (0.5)
(..0)
2.0.0.00
8.6 8.6.
10.0 (0.0)
(..5)
(0.2)
(.0((.4)
(0.2)
(.77
(.00
2.0.0.0)
(.5)
10.0 (0.0)
(.77
8.0
(0.2
ROBRCCM
(1.7)
21.6
(0.0)
4.0.00.)
2.300.00)
(0.4)
17.6(1.3)
17.3
22.6(
Completed Runs
Total Calls
85.4 (3.1)
(b)
Trck
#
#1.
Time (h.)
Calls
Stare
Fdlya
Fp. Fins HRM
# Exsmples
Esample Lengh
[x10%)
G
D
D
RD
5
1.900.2;
18:1131
400 (10-0..0)
4.0:00.0
3.010.3)
(00))
3.0
(0:9)
7.0
(1.3
(12.
BC
5
1.800.3)
7.2(1.0)
(0.00
4.0:00.0
2.700.3)
(0.2
2.4(0.2)
2.600.7
8.4(0.5)
6.(1)
6.3(1.7)
MY
5
1.400.13
58 S8.00-)
(0.00:0)
4.0:00.0)
29.00.3)
10.000.)
2.4002)
14400.2]
6.9.004)
(8
46(16))
5
11.7
24.9
48 (0.2)
4.800.2)
1200-0.4
13.00..
62.(1.))
113
11.7.08)
69(1.5)
11.8:0))
SCRMY
5
9.5
208 (2.4)
48 (0.2)
4.8:0.2)
(0.4
(1.2
5.2(0.7)
11411.
(0.5-09)
$8
(3.2
XGRMY
5
5.400.5)
14.0(1.))
4.2 (0.2)
4.200.2)
(1.8
(0.5(0.2)
3.2(0.7)
7211111
9.8(0.3)
6.2
(1..)..7
XGB
5
10.30
8.2 (0.7)
4..00.0)
3.0:00.0
(19.00.5)
(0.2
3.0
3.000.5)
1.9
[40(188
(0..(2.))
CMY
3.6 (0.4)
11.4112)
4.0 (0.0)
3.0.0.00
10.8 (0.3)
10.0 (0U)
(.2.).
(..6
1.9.0.2)
(..6)))
10.5 (1.))
XGR&CMY
(4.0
31.4 (2.5)
4.4 (0.2)
4.4(0.2)
4.9 (0.3)
11.2 (0.4)
(.4.).))
2133
16.6.038)
1.49
(7.2
Completed Rune
Total Time
(6.0
Total Calls
130.6(660)
Table 7: Results of LHRM in WATERWORLD with a restricted set of callable RMs.
(a) WOD
(s.)
Edges
Pp.
Examples
Example Length
(x10P)
G
(0.0)
(0.0)
(0.0)
(0:0)
(1.2
BC
5
5
0.9 (0.1)
3.8 (0.2)
3.0
(0.0)
0.8
10.0 (0.0)
(.8))
10.8 (0.8)
(1.9
36
3.0
(.0)
10.0 (.7
(.6(
6.6(19)
RG&BC
(0.4)
(0.9)
4.0(0..)
(..00..)
8.6(0.3)
12.4 (0.2)
(..)
(4.7
16.0
BORMY
5
3.1)
12.4 (0.2)
4.0
4.0
8.3
11.8 (0.7)
(.6)
11.2
13.2(1.))
RG&MY
RGB
(..1)
4.8 (0.7)
(.0
(..0
8.7
102 (0:2)
(..)
(0.5
16.2
CMY
5 1.6 (0.2)
6.2 (0.7)
3.0
2.0
8.6
10.0 (0:0)
(..0
8..3
(0.2
(0.4)
Completed Runs
5
(0.9)
Total Calls
78.8 (2.7)
(b)
Tiak
G
#1.
Time (s)
Chils
Stace
Edges
Ep. Fint HRM
# Examples
Exampl Lenglt
(X10P)
G
D
RG:
5
(.9)
7.8(1.1)
4.0(0.))
4.0:00)
3..(0.3)
(0.0.00.)
3.0.00.5)
2.8.009
70.
10.1
42.(0.5)
BC
5
(.8(0.3)
7.2(1.05
4.000.0)
4.0(00)
2...0.3)
(0.3)
2.4(0.3)
2.6.0.7)
8.4
69(1.5)
6.3((1.)
MY
5
1.4(0.1)
3.8
3.0(0.0)
4.0(0.0)
2.9.0.3)
10.0.0.0)
2.4(0.2)
1.4.0..)
6.910.6
58(1.5)
4.((.6)
XGRBC
5
6.9(0.7)
(7,6(15)
4..00.)
4.5(0.2)
12.0.004)
10.800.)
4.6(0.5)
9.2(1.0
10.4 10.5
9.41.85
12.6(0.5
BCAMY
5
9,3(1.8)
21.4
4.5
4.8(22)
11.7 (0.5)
12.2(1.0)
58(113
10.4
11.4
69(1.3)
(2.1
XCRMY
5
7,8(1.))
(1.)
(.5
4.8(0.2
11.8 (0.5)
11.0
(.
(0.0
9.8 (0.2)
86:0.8)
13.0.0.)
XGB
5
(.10
7.6(0.2)
(.0)
(.0)
11.9 (0.5)
10.0.0.0)
2..00.2
3.0.0.0
16.00.5
(18(1.))
(0.7(1.)
CMY
5
(.3(0.2)
8.2 (0.8
(..
(.0)
10.7 (0.2)
10.000.0)
(1244.4)
4.000.5)
7.8
99(1.6)
(.()))
SOBACMY
9.6(1.5)
20.6 (2.6)
(L0)
(10)
5.0.0..5
10.2 (0.2
6.4 (0.9)
11.0(1))
15.0
12.3008)
142(1.))
Completed Runs
Total Time
Total Calls
(1..0
43

---

Under review as a conference paper at ICLR 2023
Table Results LHRM in WATERWORLD without exploration using options.
(a) WOD
Tisk
#
Time (s.)
Calls
States
Edges
Ep. First HRM
Examples
Example Lougthi
(x10²)
G
(0.0)
(0.00
(0.0)
2.0 (0.0)
0.9 (0.1)
10.0 (0.0)
2.00).0)
(1.0
5
BC
5
(.91) (0.1)
3.8 (0.2)
3.0 (0.0)
(.0((..0)
0.8 (0.1)
10.0 (0.0)
1.8 (0.2)
10.8 (0.8)
(1.9
(.90
3.6
(..0)
(.000..)
10.0 (0.0)
(0,))
6.6(1.)
RGRBC
(2.40.4)
12:2 (0.9)
(..0).
4.0.00.0
9.5
10.6 (0.2)
8.6(1.1)
13.2
15.3
BC&MY
(.3)
11.8 (0.7)
(.00
(.0(0.0)
9.8)
11.6 (0.2)
(..6)
15.3
16.7
4.000.0)
(.1)
RGB
1.2 (0.2)
(.7)
(0.0
2.0.0.0)
(.0.
10.0 (0.0)
(.77)
9.4)0.4)
8.7
CMY
(0.1)
(..)
(0.00
2.0.0..))
8,8 (0.2)
10.0 (0.0)
(0.5
8.8 (0.2)
(0.5
RGB&UMY
(1.1
4.0(00.)
21.6
Completed Runs
5
Total Time
34.4
Total Calls
77.4 (2.0)
(b) WD
Taok
FG FL
Time (s.)
Calls
Statts
Edges
Ep. Fint HRM
Exampple
Example Length
[x10')
X6
(.9.0.3)
188 18:(1.1)
4.0 (0:00
4.0:00.0)
3.0:0.3)
(0.0)
(..3)
(0:9)
7.0
10.3 (1.6)
(.2.0.3)
BC
(.8.0.22
7.2(1.0)
(0.0)
4.0:00.0)
2.7 (0.3)
(0.2
(.4((.2)
2.6
8.4(0.3)
6.91)
6.3(1.7)
MY
5
1.400.13
5.8 (0:4)
4.0-00. (0.00
4.0-00.0
299 (0.3)
10.0
2.4 2.4(212)
14:0.21
6.9.004)
1..11.5)
4.6(1.8)
(..4
15.2.2.2)
4.6 (0:2)
4.6-10.2
97.4.4.3 (4.2)
10.8
(22))
92
10.5 (0.5)
10.311
13.7(1.5)
BCANNY
(0.5)
15.6 (0.7)
4.6 (0.20
4.6/00.2
91.3 (3.5)
(0.5
(16)
7.400.71
9.7(0.2)
7.11.21
11.5(1.)
RC.&M
5
8.611.8
(2.7(2.7)
4.4 (0.2)
4.4:0.2)
90.3 (5.3)
(1.2.08)
5.6.0.)
941133)
(0.4.0.7
77.00.7)
(3.3.09)
RGB
5
2.3
(0.2)
4.0 (0.00
3.0.00.)
(1.5)
10.2 (0.2)
(.6)
(0.4
7.6.0.3)
[1.1
$.8(1.))
CMY
5
4.4 00.63
13.2(1.5
38 (0.2)
(.0000.0
(2.9)
10.2 (1.2)
(16)
71.00
6.95
12
7.6-003
RERACMY
5
(5.0)
(3.4
4.4 (0.2)
4.4(0.2)
125.7 (9.9)
(0.5)
5.8(1))
2120022)
(7.6
(..6)))
178(1.))
Completed Runs
5
Total Time
66.7 (6.6)
Total Calls
16.30
Tasks
Updated task's HRM
Callable
Batter
task
HRMs
Task HRM
ILASP
Cake
Lt
4+114411
Lt
Instances
Task Instance
Agent
Traces
a6+1
Lt
8t: 24+1
Yes
Trace Co. Lt
Counterexample?
Figure 13: Overview of LHRM.
H ILLUSTRATION OF LHRM
Figure 13 illustrates the main components of our algorithm for learning HRMs, LHRM, described Given a set of tasks with known levels and a set instances, we select (task, instance) pair at the beginning of episode. The HRM corresponding to the selected task is taken from the bank HRMs. At each step, the agent performs an action a:41 in the (task, instance) environment, and observes tuple 8, and label L. The label is used to (i) know the next hierarchy state W++1 in the HRM and the reward Tt+1. and (ii) update the label trace (Co,..., L.). If the trace is counterexample (i.e., the tuple 8, and the new hierarchy state U4+11 inconsistent with each other) we add it to our set of counterexample traces for the current task and learn new HRM using the ILASP system. The learned HRM is then updated in the bank of HRMs so that future tasks can reuse it. Note that the description omits some aspects for simplicity, such as how are the (task, instance) pairs selected, the exploration using options from lower level HRMs, or the accumulation of traces before learning the first HRM for given task.
in Section 5
Foor example if (*T + =(T, TT and the state in Me+1 is not the accepting state of the root RM.
44

---

Under feview as a conference paper at ICLR 2023 3
Table 9: Results of learning non flat and flat HRMs using different methods. The columns are the following: the number of completed runs without timing out, the amount of time needed to learn the HRMs or RMs, and the number of states and edges of the R.M.
32.3 3. 82.4 (9.1)
Edggos
3.0
States
JIKP
4.0
17.1
Time
31.2 (2.0)
Edles
States
4.0 2261. (0610(55500 (552.2)
LKM
C Time
347
93.2 (1.7
119.0 (19.4)
928
Edgges
DeepSynil
States
16.6 (3.1)
12.8 (0.5)
(2.2
298 9 (31-771
308 6 (52.6)
Time
Eilges
2.0 (0.0)
LHKK (Plr))
States
3.0 (0.0)
(0.6) 4.0
(0.0
Time
0
Bilgess
2.0.0.0)
5.8 20
4.000.00
3.0 (0.0) 2.0.0.0)
(..00.00
4.0000.0
LHKM (Non- Hil))
States
(0.0)
4.0 (0.00
1.000.00
4.000.00
(91.2.06444 (364)
17.9
0.9 (0.0)
455 (033)
Time (s.)
Book BUOKQUILL
ROOk
Tank
MG
45

---

Under review as a conference paper at ICLR 2023
22
MA
MT
MT
M
A
M
4
22
u2
M
4
MT
M
u
u
MT
M
MT
A
MT
ug
(a) Mo - BUCKET
(b) M1 SUGAR
(C) M2 BATTER
(d) M3 PAPER
x4
MT
MT
MT
MT
u
M-
My
T
MT
MT
MT
MT
un
MT
A
MT
Mr
MT
US
UG
(c) M4- COMPASS
(f) Ms LEATHER
M QUILI.
(h) My MIL.BBCKKT
M
M,
#
M3
T
M,
#
M,
T
My
8
M
M
T
M2
M2
T
Ms
M
T
M,
I
M-
05
M40
(i) M3- MAP
(i) Mg BOOK
(k) Mio MUGAR.SUGAR
Mg
T Mg
Ma
Ms
uri
uP2
M2
T
u12
Mio
T+
ui22
MT
1
()) M11 BOOKQUILL
(m) M12 CAKE
Figure 14: Root reward machines for each of the CRAFTWORLE tasks.
46

---

Under review as a conference paper at ICLR 2023
My
MT 5
M
NO
c
Mr y
Mi T
Mo
M1
(a) Mo RG
(b) M1 BC
(c) M2 MY
(d) M3 RG&BC
Mo T
M
Mj
mm
M2
Mo
m
M2
m
1
M
M
Mo
T
MT 9
M2 T
(e) M1 BC&MY
Ms RG&MY
(g) Ms RGB
(h) CMY
ue
Mg
M
u
US
M
T
M
ug
Ms RGB&CMY
Figure 15: Root reward machines for each of the WATERWORLD tasks.
47


Reviews:
[{"review_id": "ZYrAhe0nmU", "reviewer": "Reviewer_8bbu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper extends the Reward Machines (RM) formalism to hierarchical RMs (HRMs) by allowing RMs to call other RMs as sub-programs. The paper demonstrates that this allows for more efficient learning of RMs on long-horizon tasks in a number of toy grid-world environments.", "summary_of_the_review": "Overall, I found the submission quite hard to read. I was not previously familiar with RMs and I found the heavy use of formalism and special terms throughout the submission hampered the reading flow. It also makes it hard for me to properly judge the novelty of the work: my perception is that the submission adds novelty over the previous RM work, but it also seems to make multiple assumptions that can reduce its impact outside the currently rather niche RM topic. The experimental evaluation does not help judge this either, since it is limited to toy environments and does not compare to non-RM works.\n\nI am leaning towards not accepting the submission, but am willing to change my mind if the authors can clearly state their assumptions and how they relate to other option learning papers (ie is there good use cases for their approach that others cannot do, can you compare to any non-RM approach?). Additionally, I am curious to know what other reviewers opinions are, especially for reviewers with a better overview of the RM literature.\n\n=============\nPost-Rebuttal: I updated my score to a weak accept based on the discussion with the other reviewers -- see my reply below.", "strength_and_weaknesses": "# Strengths\n\n- incorporating hierarchy into RMs seems like an important step towards making them more applicable to long-horizon tasks\n\n- the submission rigorously defines all aspects of the problem setup\n\n- the toy experiments demonstrate that the introduced hierarchical RMs learn faster than regular (flat) RMs if a RM hierarchy is pre-defined, they also demonstrate learning of long-horizon tasks with HRMs (not possible with RMs)\n\n\n# Weaknesses\n\n(A) **hard to follow writing**: The writing of the paper is very hard to follow. I attribute this in large part to the very heavy usage of formalism and introduction of terms, which make smooth reading challenging. It seems that the paper could benefit a lot from replacing / augmenting some of the formal definitions with their plain-english equivalents. On other occasions crucial terms are not properly defined. Eg in the background section 2, the terms “propositions” and “labels” are not properly introduced, no intuition / example is given for what they could refer to. This makes it very hard to understand the paper for readers (like myself) that aren’t already familiar with the RM literature.\n\n(B) **assumptions not clearly mentioned**: compared to other papers that use (deep) RL to learn options & policies the submission seemingly makes a number of assumptions (given subtask hierarchies or at least a priori knowledge about depth of the hierarchy, symbolic observations, access to training tasks for *non-hierarchical* RMs, …). However, these assumptions are only step-by-step introduced throughout the text and can be easily missed. It would be good to add a “problem formulation” section or similar that explicitly lists the required assumptions for learning hierarchies of HRMs and how they compare to prior works, so that readers can better understand in what use cases they can consider HRMs.\n\n(C) **no comparisons to other option learning approaches**: the only comparison in the experimental section is to flat RMs — this is a meaningful comparison since the proposed approach is a hierarchical extension of flat RMs. However, since the paper proposes an approach for learning hierarchical options, it should compare to prior works on option learning with deep RL too, if applicable. E.g. the work of Sungryull Sohn could be applicable, since it also addresses hierarchical RL with discrete observational symbols (eg Sohn et al., NeurIPS 2018).\n\n(D) **only tested in toy environments**: the submission tests the proposed approach only in simple 2D grid-world like environments with low-dimensional observation and action spaces. This makes it hard to judge how well the method would scale to more realistic settings, eg. learning robot control in 3D environments.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "A4bMocrd0lZ", "reviewer": "Reviewer_M97T", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "**Update after rebuttal** I think the other reviewers have raised some valid criticism, and have definitely helped to make the manuscript more accessible and improve readability. Having read the authors' response I think that all main issues have been addressed in a satisfactory manner (certainly true for the issues raised by me), and therefore remain in favor of accepting the paper.\n\n\nThis paper extends the Reward Machine framework by allowing for hierarchical compositions of reward machines. The basic idea for the construction is that transitions in one reward machine are captured by whole separate reward machines - a higher-level reward machine can call a lower-level reward machine, which allows for compositionality and re-use of reward machines. The paper also shows how to use hierarchical RL to learn policies from hierarchical reward machines, and how to synthesize hierarchical reward machines from data. Evaluations on simple environments prove that the concept works, and show some favorable results compared to flat reward machines. ", "summary_of_the_review": "The paper constructs and analyzes an interesting and sensible hierarchical extension to the Reward Machines framework, which addresses important shortcomings and puts follow-up work on a solid theoretical footing. It also introduces two important and nontrivial algorithms for learning from HRMs and learning HRMs themselves from data. Overall I think this is a well executed and interesting extension to the Reward Machines framework, which has seen good adoption lately; the paper will be relevant to researchers in hierarchical RL and modeling of complex reward functions / specifications (which itself is a growing area of interest). The main idea of the extension is sensible and straightforward; the execution in the paper is very good and the precise theoretical construction presented is sound and interesting - this is a nontrivial contribution. My main criticism is that the paper is very dense and packs a lot of material into the page limit - while the first sections are very well written and can be well understood (with a background in basic Reward Machines), Section 4, 5, and 6 could be improved in terms of clarity and detail (but adding detail is hard given the already crammed paper). I think this is a high-quality, well-written and well executed paper that is ready for publication, and has good potential to stir follow-up theoretical work and almost certainly more investigations into learning with HRMs and synthesizing HRMs from data, and therefore currently suggest acceptance at the conference. \n", "strength_and_weaknesses": "**Main contributions, Impact**\n\n1) Hierarchical extension of the Reward Machines framework. Though not entirely unexpected, the construction presented is solid and well executed. I would give this a medium to high impact since it puts a lot of potential follow-up work on solid footing and addresses important shortcomings of basic reward machines.\n2) Illustrative algorithm / proof of concept for learning policies with hierarchical reward machines. This certainly strengthens the paper since it allows for empirical results. I do not feel confident judging the sophistication of the algorithm, and suspect that there might be improvements in the near future inspired by this work. Impact: medium.\n3) Proof of concept algorithm for learning hierarchical reward machines. Another great point to strengthen the paper since it addresses the criticism of having to manually construct reward machines. Quite a number of choices went into the algorithm, and it currently also comes with quite a number of restrictions / assumptions. While it would be nice to see some alternatives explored and compared to, I think this is beyond the scope of this paper (and certainly beyond the page limit), and similarly to 2) I would expect more follow-up work along these lines to appear in the near future. Impact: medium to potentially high (e.g. for learning complex reward functions from human data).\n\n**Strengths**\n\n* Interesting and natural open problem in the Reward Machines framework addressed in a theoretically sound and solid fashion\n* Very well written intro and theory (up to Sec. 4)\n* Adding important bits for empirical evaluation: (i) adapting/suggesting a hierarchical RL algorithm that can learn with HRMs, (ii) suggesting an algorithm to learn HRMs from data. \n\n**Weaknesses**\n\n* Paper is very dense, this comes at the expense of clarity and sufficient detail in sections 4, 5 and 6. Both 4 and 5 (including some empirical results form 6) could be turned into separate full publications. While I appreciate having 4, 5, and 6 in the paper, and would not recommend removing them, the strict page limitations of a conference make some trade-offs necessary. Additionally, the paper comes already with an excessive appendix (which contains interesting parts).\n* Sections 4 and 5 propose two algorithms - both algorithms could have been designed differently, and there are some (more or less) obvious alternatives and ablations that would be nice to see; but the current paper simply does not have space for them (and I do not recommend filling up the appendix even more).\n\n**Improvements**\n1. There is not too much that can be done about a dense paper with an already long appendix, other than aiming for a journal paper with less severe page restrictions. While I think this would improve the paper, I also think that the current version is clearly above the threshold for publication at the conference, and I also think that publishing these results should not be delayed any longer. So I don’t expect to see an improvement here; maybe as a suggestion, the related work section could potentially be moved to the appendix to give 4 and 5 a bit more space.\n\n2. I think it is worth giving Sections 4 and 5 another pass for clarity - it currently seems that all the information is in place, but not presented in the most easily understandable way. Some overview/summary/illustration of the actual scheme proposed and the algorithms implemented for the empirical evaluation would be helpful. Having said that, the two sections do currently pass my threshold for acceptance, but I think could be improved for an excellent paper.\n\n3. Discussion of limitations of (L)HRMs is very short (determinism, having to define labeling functions). It would be nice to expand on this a little bit more, particularly compared to RMs.\n\n**Minor comments**\n\nA) Theorem 1: It would be nice to be more precise what “equivalent” means in the main paper (e.g. equivalent: an automaton that accepts the same language (language = set of all possible label traces \\lambda that respect the MDP transition dynamics)).\n\nB) Learning HRMs - why select tasks and instances with lower returns first? Why not choose highest returns first and switch once the increase in returns starts to saturate (i.e. learn the easiest tasks first, then switch to the next hardest ones once there is no progress on the easy ones anymore).\n\nC) Learning HRMs - how exactly are learned options re-used? “An option is selected from a\npool of options appearing in lower height RMs”; how is this selection done, probabilistically or by exhaustive evaluation and some deterministic selection criterion?\n\nD) Not sure if the experiments are optimal to show the advantages of non-flat HRMs. I would imagine non-flat HRMs to perform even better in cases where a simple task (such as gathering paper) must be repeated multiple times (e.g. to create a composite object of ‘book’ and ‘map’, ‘paper’ needs to be gathered twice). The current tasks (at first glance) seem to be chosen to collect a series of objects once. I might have missed that the same advantage would play out in flat HRMs (which are different from plain RMs?), so please correct me if this is wrong.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7KlW5TX3TY", "reviewer": "Reviewer_2jNi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper extends the concept of reward machines to hierarchical reward machines (HRM), and presents a method for learning policies for HRMs and for learning HRMs from data (learning is interleaved with policy optimization).  ", "summary_of_the_review": "The paper makes relevant contributions, which, however, are currently not sufficiently well presented. There are several aspects that need to be clarified, for example, regarding the treatment of discounting and the possibility of executing the same RM several times during a single trajectory.\n", "strength_and_weaknesses": "Strength:\n- Relevance: the paper tackles an important problem of learning and exploiting hierarchical task specifications.\n- Novelty: The presented formalism (HRM) and the methods for learning policy and HRMs are novel.\n\nWeaknesses:\n- Clarity: The paper is hard to follow (see \"Clarity\" below)\n- Significance: HRMs seem to suffer from too strong assumptions (see \"Quality\" below)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject