The Logical Options Framework
Authors: Brandon Araki
Xiao Li
Kiran Vodrahalli
Jonathan DeCastro
J Micah Fry
Daniela Rus
Venue:  (2021)
Keywords: reinforcement learning
hierarchical methods
formal methods
formal logic

Abstract: Learning composable policies for environments with complex rules and tasks is a challenging problem. We introduce a hierarchical reinforcement learning framework called the Logical Options Framework (LOF) that learns policies that are satisfying, optimal, and composable. LOF efficiently learns policies that satisfy tasks by representing the task as an automaton and integrating it into learning and planning. We provide and prove conditions under which LOF will learn satisfying, optimal policies. And lastly, we show how LOF's learned policies can be composed to satisfy unseen tasks with only 10-50 retraining steps. We evaluate LOF on four tasks in discrete and continuous domains.

Under review as a conference paper at ICLR 2021
LOGICAL OPTIONS FRAMEWORK
Anonymous authors
Paper under double-blind review
ABSTRACT
Learning composable policies for enviromments with complex rules and tasks is a challenging problem. We introduce hierarchical reinforcement learning frame- work called the Logical Options Framework (LOF) that learns policies that are satisfying, optimal, and composable. LOF efficiently learns policies that satisfy tasks by representing the task as an automaton and integrating it into learning and planning. We provide and prove conditions under which LOF will learn satisfy- ing, optimal policies. And lastly, we show how LOF's learned policies can be composed to satisfy unseen tasks with only 10-50 retraining steps. We evaluate LOF on four tasks in discrete and continuous domains.
INTRODUCTION
To operate in the real world, intelligent agents must be able to make long-term plans by reasoning over symbolic abstractions while also maintaining the ability to react to low-level stimuli in their environment (Zhang & Sridharan 2020). Many environments obey rules that can be represented as logical formulae; e-g., the rules car follows while driving, or a recipe a chef follows to cook dish. Traditional motion and path planning techniques struggle to formulate plans over these kinds of long-horizon tasks, but hierarchical approaches such as hicrarchical reinforcement learning (HRL) can solve lengthy tasks by planning over both the high-level rules and the low-level environment. However, solving these problems involves trade-off's among multiple desirable properties, which we identify as satisfaction, optimality, and composability (described below). Most of today's 's algorithms sacrifice at least one of these objectives. For example, Reward Machines from Iaart al. (2018) is satisfying and optimal, but not composable; the options framework (Sutton et al.) 1999) is com- posable and hierarchically optimal, but cannot satisfy specifications. We introduce a new approach called the Logical Options Framework, which builds upon the options framework and aims to com- bine symbolic reasoning and low-level control to achieve satisfaction, optimality, and composability with as few compromises as possible. Furthermore, show that our framework is compatible with a large variety of domains and planning algorithms, from discrete domains and value iteration to continuous domains and proximal policy optimization (PPO).
An agent operating in an environment governed by rules must be able to satisfy the specified rules. Satisfaction is a concept from formal logic, in which the input to a logical formula causes the formula to evaluate to True. Logical formulac can encapsulate rules and tasks like the ones described in Fig. [ such as "pick up the groceries" and "do not drive into a lake". In this paper, we state conditions under which our method is guaranteed to learn satisfying policies.
Satisfaction:
Optimality: Optimality requires that the agent maximize its expected cumulative reward for each episode. In general, satisfaction can be achieved by rewarding the agent for satisfying the rules of the environment. In hierarchical planning there are several types of optimality, including hier- archical optimality (optimal with respect to the hierarchy) and optimality (optimal with respect to everything). We prove in this paper that our method hierarchically optimal and, under certain conditions, optimal.
Composability; Our method also has the property of composability - once it has learned to satisfy a task, the learned model can be rearranged to satisfy large variety of related tasks. More specifically, the rules of an environment can be factored into liveness and safety properties, which we discuss in Sec. 3 The learned model
be adapted to satisfy any appropriate new liveness property. A shortcoming of many RL models is that they are not composable trained to solve one specific task, they incapable of handling even small variations in the task structure. However, the real world is

---

Under review as a conference paper at ICLR 2021
dynamic and unpredictable place, so the ability to automatically reason as-yet-unseen tasks and rules is a crucial element of intelligence.
"Go grocery shopping, pick the kid, and go home, unless your partner calls telling you that they will pick
up the kid, which case just go grocery shopping and then go don't drive the lake."
(a) These natural language instructions can transformed into an FSA, shown in (b).
S2
Safety Event
Subgoal propositions
proposition proposition
(b) The FSA representing the natural language instruc- tions. The propositions are divided into "subgoal", "safcty", and "event" propositions.
(c) The low-level MDP and corresponding policy that
satisfies the instructions.
Figure Many parents face this task after school ends who picks up the kid, and who gets groceries? The pictorial symbols represent propositions, which are true false depending the state the environment. The arrows (c) represent subpolicies, and the colors the arrows match the corresponding transition in the FSA. The boxed phone at the beginning of some of the arrows represents how these subpolicies can occur only after the agent receives a phone call.
The illustrations Fig. give an overview of our work. The environment a world with a grocery store, your (hypothetical) kid, your house, and some lakes, and in which you, the agent, are driving a car. The propositions are divided into "subgoals", representing events that can be achieved, such as going grocery shopping; "safety" propositions, representing events that must be avoided (driving into a lake); and "event" propositions, corresponding to events that you have no control over (receiv- ing phone call) (Fig. [b]. In this environment, you have to follow rules (Fig. lap. These rules be converted into a logical formula, and from there into a finite state automaton (FSA) (Fig. lb). The Logical Options Framework learns option for each subgoal (illustrated by the arrows in Fig. [T], and metapolicy for choosing amongst the options to reach the goal state the FSA. After learning, the options can be recombined to fulfill other tasks.
1.1 CONTRIBUTIONS
We introduce the Logical Options Framework (LOF), which makes four contributions to the hierar- chical reinforcement learning literature:
1. The definition a hierarchical semi-Markov Decision Process (SMDP) that is the product of logical FSA and low-level environment MDP.
2. A planning algorithm for learning options and metapolicies for the SMDP that allows for the options to be composed to solve new tasks with only 10-50 retraining steps.
3. Conditions and proofs for achieving satisfaction and optimality.
4. Experiments discrete domain and continuous domain four tasks demonstrating satisfaction, optimality, and composability.
BACKGROUND
We use linear temporal logic (LTL) to formally specify rules (Clarke et al.] 2001]. LTL. formulae are used only indirectly in LOF, as they converted into automata that the
Linear Temporal Logic:
2

---

Under review as a conference paper at ICLR 2021
algorithm uses directly. We chose to use LTL to represent rules because LTL corresponds closely to natural language and has proven to be a more natural way of expressing tasks and rules for engineers than designing FSAs by hand (Kansou 2019). Formulae & have the syntax grammar
- Φ1 V Ø2 O Φ Φ1 U c2
where p is proposition (a boolean- valued truth statement that can correspond objects or events in the world), - is negation, V is disjunction, O is "next", and U is "until". The derived rules are conjunction (A), implication ( ) equivalence (++), "eventually" (Dé = Truel U ()) and "always" (Dó - (Baier & Katoen 2008). Φ1 i2 d2 means that Φ1 is true until Φ2 is true, Dø means that there a time where Ø is true and Ug means that Φ is always true.
The Options Framework: The options framework is framework for defining and solving semi- Markov Decision Processes (SMDPs) with a type of macro-action or subpolicy called an option (Sutton et al.,, 1999). The inclusion of options in MDP problem turns it into an SMDP problem, because actions are dependent not just on the previous state but also on the identity of the currently active option, which could have been initiated many time steps before the current time.
An option o is a variable-length sequence of actions defined as = (I, n. 3, (8), To(s"(s)) IC is the initiation set of the option. S A + [0, 1] is the policy the option follows while the option is active. 8 S + [0, 1] is the termination condition.
(s) is the reward model of the option. (5'(s) is the transition model. A major challenge in option learning is that, in general, the number of time steps before the option terminates, k. is a random variable. With this in mind, (s(s) is defined as the expected cumulative reward of option o given that the option is initiated in state at time and ends after k time steps. Letting rt be the reward received by the agent at / time steps from the beginning of the option,
(s) = [E[r 732 +....
(s'ss)) (8) is the combined probability p(s', .)) that option o will terminate at state s' after & time steps:
Ts(sss) Σ k)
(2)
In the next section, we describe how Eqs. and can be simplified in the context of LOF.
LOGICAL OPTIONS FRAMEWORK
Here a brief overview of how we will present our formulation of LOF:
1. The LTL formula decomposed into liveness and safety properties. The liveness property defines the task specification and the safety property defines the costs for violating rules.
2. The propositions of the formula are divided into three types: subgoals, safety propositions, and event propositions. Subgoals are used define tasks, and each subgoal is associated with its own option, whose goal is to achieve that subgoal. Safety propositions are used to define rules. Event propositions serve as control flow variables that affect the task.
3. We define an SMDP that is the product of low-level MDP and high-level logical FSA.
4. We describe how the logical options can be defined and learned.
5. We present an algorithm for finding the hierarchically optimal policy on the SMDP.
6. We state conditions under which satisfaction of the LTL specification guaranteed, and we prove that the planning algorithm converges hierarchically optimal SMDP policy is the same as the optimal MDP policy.
optimal policy by showing that the
The Logic Formula: LTL formulae can be translated into Büchi automata using automatic trans- lation tools such as SPOT (Duret-Lutz et al. 2016). All Büchi automata can be decomposed into liveness and safety properties (Alpern & Schneider 1987). To simplify the formulation, we assume that the LTL. formula itself can be divided into liveness and safety formulae, dliveness Psafety-
3

---

Under review as a conference paper at ICLR 2021
For the case where the LTL formula cannot be factored into independent formulae, please Ap- pendix A The liveness property describes "things that must happen" to satisfy the LTL formula. is a task specification, and it is used in planning to determine which subgoals the agent must achieve. The safety property describes "things that can never happen" and is used to define costs for violating the rules. In LOF, the liveness property must be written using finite-trace subset of LTT. called syntactically co-safe LTL (Bhatia et al. 2010), in which the D ("always") operator is not allowed and O U. and & are only used in positive normal form. This way, the liveness property can be satisfied by finite-length sequences of propositions, and the property can be represented as an FSA.
Propositions are boolean- valuud truth statements corresponding to goals, objects, and events in the environment. We distinguish between three types of propositions: subgoals Pa, safety propositions Ps. and event propositions PE- Subgoal propositions are propositions that must be achieved in order to satisfy the liveness property. They are associated with goals such as "the agent at the grocery store". They only appear in Pliveness- Each subgoal may only be associated with one state. Note that in general, it may be impossible to avoid having subgoals appear in feay- Appendix A describes how to deal with this scenario. Safety propositions are propositions that the agent must avoid for example, driving into a lake. They only appear in frafety- Event propositions have a set value that affects the task specification - for example, whether or not phone call is received. They may occur in Oiineness, and, with some extensions that are described in Appendix [A] in @safety- Although in the fully observable setting, event propositions are somewhat trivial, in the partially observable setting, where the value of the event proposition is revealed to the agent at random point in time, they are very useful. Our optimality guarantees only apply in the fully observable setting; however, LOF's properties of satisfaction and composability still apply in the partially observable setting. The goal state of the liveness property must be reachable from every other state using only subgoals. This means that no matter what the values of the event propositions are, it is always possible for the agent to satisfy the liveness property. Proposition labeling functions relate states to the set of propositions that are true at that state: TP& : SS - 2PG, Tp. : :S + 2P'; for event propositions, a function identifies the set of true propositions, TPg: :2 + 10.
Propositions:
Hierarchical SMDP: LOF works by defining a hicrarchical semi-Markov Decision Process (SMDP), learning the options, and then planning over the options. The high-level part of the hi- erarchy is defined by an FSA specified using LTL. The low level is an environment MDP.
We assume that the high-level LTL specification can be decomposed into a liveness property Óliveness and a safety property feafety. The set of propositions P is the union of the sets of subgoals Pa. safety propositions Ps. and event propositions Pg. We assume that the liveness property can be translated into an FSA T = (F, PP Tr. Rr; fo. fg)- FF is the set of automaton states; P is the set of propositions; TF is the transition function relating the current state and proposition to the next state, TF= : F x P x J + [0, 1]. In practice, TF is deterministic despite our use of probabilistic notation. We assume that there is a single initial state fo and final state fg. and that the goal state fg is reachable from every state f E F using only subgoals. There is also reward function that assigns a reward to every state, Rp : F R. our experiments, we assume that the safety property takes the form Ap.eps D-p.. This simple safety property implies that every safety proposition is not allowed, and that the safety propositions have associated costs, Rss : 2Ps + R. @safety is not limited to this simple case; the general case is covered in Appendix
There is a low-level environment MDP È (S,A, Rg, TE. 7). S is the state space and A is the action space. They can be discrete or continuous. RØ S x A - IR is low-level reward function that characterizes, for example, distance or actuation costs. Rg a combination of the safety reward function Rs and Rg, e.g. Rg a) = RE(s, a) + Rs (Tp, (s)). The transition function of the environment is TE: : S x A x S + [0, 1].
From these parts we define a hierarchical SMDP 1IDDPM- (SXF P, TEXxxXxxxx RSMDP, The hierarchical state space contains two elements: low-level states S and FSA states F. The action space is A. The set of propositions is P. The set of options (one option associated with each subgoal in PG) is O. The transition function consists of the low-level environment transitions Tg and the FSA transitions Tr. Tr Tra x Try x Tre- We classify Tr, relating states to propositions, as a transition function because it helps to determine when FSA transitions occur. The transitions are applied in the order TE. Tp, TF. The reward function RSMDP (f, s) = RF (s,)),, so RF(f) is a weighting on the option rewards. Lastly, the SMDP has the same discount factor as E. Planning is done on the SMDP in two steps: first, the options O are learned over & using an
4

---

Under review as a conference paper at ICLR 2021
Algorithm Learning and Planning with Logical Options
1:
2:
Given:
Propositions P partitioned into subgoals Pa, safety props Ps. and event props Pr:
Logical FSA T = (F. Pg x Pg.TE RF, fg) derived from Piiveness
Low-level MDP & = (S,A, Rg. TE, 7). where Rg a) Rg(s, Rs (I (s))
combines the environment and safety rewards
Proposition labeling functions Tra - Poo Try - 2Ps , and
Tpp P 10,1}
3:
To learn:
4:
Set of options O, one for each subgoal proposition p E Pa
5: Metapolicy fff.s, along with Q(f, s, and (ff.s)
6:
Learn logical options:
7:
For every p Pc. learn an option for achieving p. Op (Iops Tap Sap Rop Top)
8:
Io = S
[1
p E TPa
9:
Bor
00
otherwise
10:
Top = optimal policy on with rollouts terminating when p E (P)
Top (s'1s) EEy* if TP (s'), where k is number of time steps to reach otherwise
11:
12:
RØ, (s) = E (s, + Rg 02) + ................................ ........ gp 8-1 (s
13:
Find metapolicy μ over the options:
14:
Initialize Q Q:Fxx S O and F R
For (1)) [1, mJ] F
16:
For 0 E O:
Qu(f.s,0 0, RF(f)Ro(s) EPEF En Lf
(P.) V (
19:
8)(5,)) max (u(
20:
s(ʃ, 8, arg max 8,),
oEO
21:
return Options O, metapolicy μ(f, 8, and Q- and value functions V(f,)
22:
end procedure
appropriate policy-leaming algorithm such as PPO or Reward Machines. Next, a metapolicy over the task specification found using the learned options and the reward function RSMDP.
Logical Options: The first step of Alg. I is to learn the logical options. We associate every subgoal p with an option Op (Iop: Fop Soy Rop ). These terms are defined starting at Alg. line Every Op has a policy Top whose goal is to reach the state Sp where is true. Options are learned
by training on the environment MDP & and terminating only when sp reached. As we discuss in Sec. 3.1 under certain conditions the optimal option policy is guaranteed to always terminate at the subgoal. This allows us to simplify the transition model of Eq. to the form Alg line IT In the experiments, we further simplify this expression by setting
Logical Value Iteration:
After finding the logical options, the next step is to find policy for FSA
T over the options, as described in Alg. line 13
A value function and Q-function are found for
the SMDP using the Bellman update equations:
Qu(S.8,0) + Rr())R((s) +
Σ Σ TTr J'FF PeeeRe
TPe
(3)
V)(S,) max (,( DEO
Eq. 3 differs from the generic equations for SMDP value iteration in that the transition function has two extra components, Eper (r Tr(s'), P.)) and Ep.e2 Tre (Pe). The equations
5

---

Under review as a conference paper at ICLR 2021
derived from Araki et al. (2019) and the fact that, on every step in the environment, three transitions are applied: the option transition To. the event proposition "transition" Tpp and the FSA transition Tr. Note that (s) and (s' (s) compress the consequences of choosing an option state from a multi-step trajectory into two real-valued numbers, allowing for more efficient planning.
3.1 CONDITIONS FOR SATISFACTION AND OPTIMALITY
Here we give an overview of the proof' and necessary conditions for satisfaction and optimality. The full proofs and definitions are in Appendix B using the more general formulation of Appendix A
First, we describe the condition necessary for an optimal option to always reach its subgoal. Let (s(sss be the optimal goal-conditioned policy for reaching a goal s'. If the optimal option policy equals the goal-conditioned policy for reaching the subgoal Sg, i.e. π T*(ss = (5)s)) then the op- tion will always reach the subgoal. This can also be stated in terms of value functions: let V (s|s") be the expected return of x (s)ss'' If V* (s|sg) > V (s|s") Vs, s' & 8g. then n" (*()) = Tgg (s)s)). This occurs for example if -oo < (E(s, a) and if the episode terminates only when the agent reaches #g. Then V is a bounded negative number, and V* for all other states is -o0. We show that if every option is guaranteed to achieve its subgoal, then there must exist at least one sequence of options that satisfies the specification.
We then give the condition for the hierarchically optimal metapolicy μ² (s) always achieve the FSA goal state fg- In our context, hierarchical optimality means that the metapolicy is optimal over the available options. Let yt (f. s sif') be the hierarchically optimal coul-conditioned metapolicy for reaching FSA state f'. If the hierarchically optimal metapolicy equals the goal-conditioned metapolicy for reaching the FSA goal state fg. i.e. μ² (f, = My (f, s fg), then Je" y= 8) will always reach fg. In terms of value functions: let V (f, slf') be the expected return for μ². If V (J, s) fs)s) > VV' ([)s), f' + fg. then μ² = Mg. This occurs if all FSA rewards Rf( 0, all environment rewards -00 < Rg(s, a) < O, and the episode only terminates when the agent reaches fg. Then V is a bounded negative number, and VK for all other states is -oo. Because LOF uses the Bellman update equations to learn the metapolicy, the LOF metapolicy will converge to the hierarchically optimal metapolicy.
Consider the SMDP where planning is allowed over low-level actions, and let call it the "hierar- chical MDP" (HMDP) with optimal policy THMDP. We can then state the final theorem:
Theorem 3.1. Given that the conditions for satisfaction and hierarchical optimality are met, the LOF hierarchically optimal metapolicy By with optimal option subpolicies Ti has the same expected returns as the optimal policy π THDDP and satisfies the task specification.
4 EXPERIMENTS & RESULTS
Experiments: We performed experiments to demonstrate satisfaction and composability. For the satisfaction experiments, we measure cumulative reward over training steps. Cumulative reward is proxy for satisfaction, as the environments can only achieve the maximum reward when they satisfy their tasks. For the composability experiments, we take the trained options and record how many metapolicy retraining steps it takes to learn an optimal metapolicy for new task.
Environments:
We measure the performance of LOF on two environments. The first environment is discrete gridworld (Fig. 2a) called the "delivery domain," as it can represent delivery truck delivering packages to three locations (a, b, c) and having a home base h. There are also obstacles (the black squares). The second environment is called the reacher domain, from OpenAl Gym (Fig. 2d). It is a two-link arm that has continuous state and action spaces. There are four subgoals represented by colored balls: red r, green g. blue b, and yellow y. Both environments also have an event proposition called can, which represents when the need to fulfill part of a task is cancelled.
We test satisfaction and composability on four tasks. The first task is "sequential" task. For the delivery domain, the LTL formula is (a A (b A O(c A (h))) A O-o - "deliver package a, then b, then c, and then return home h. And always avoid obstacles." The next task is the "IF" task (equivalent to the task shown in Fig. [b): (0(c A Qa) A C-can) V (&a A (can) A D-o "deliver package e, and then a, unless gets cancelled. And always avoid obstacles". We call the
Tasks:

---

Under review as a conference paper at ICLR 2021
Auarage normal lood soward
Avarage nammalteed reward
0.5
0L8-
0.4
8.44
200 250
training
1e5
metepolicy retraining steps
(a) Delivery domain.
(b) Satisfaction performance.
(c) Composability performance.
-20
Averago raward
Auurage roward
-00
-100
20
Number trarsig steps
Number of metapolicy retraining steps
(d) Reacher domain.
(e) Satisfaction performance.
(f) Composability performance.
LOF-VI
LOF-QL
Greedy
Flat Options
Reward Machines
Figure 2: Performance on the satisfaction and composability experiments, averaged over tasks. Note that LOF-VI composes new metapolicies in just 10-50 retraining steps. Results for the delivery domain are the first row, for the reacher domain the second row. All results, including RM satisfaction performance the reacher domain, are in Appendix C.6
LOF Total
O De
SO
-5
rD
Greedy Total Reward: -7
-2
Figure 3: In this environment, the agent must either pick up the kid go grocery shopping, and then go home. This is equivalent to the OR task. Starting at SO, the greedy algorithm picks the next step through the FSA with the lowest cost (in this case, picking up the kid), which leads to higher overall cost. The LOF algorithm finds the optimal path through the FSA.
"deliver package a or b, then and always avoid obstacles". The "composite" task has elements of all three of the previous tasks: (0 v ^ (cA (h)) A l-can) v (o((a V)) A 4)) A Φcan) A U-o. "Deliver package a or 6, and then unless c gets cancelled, and then return to home h. And always avoid obstacles". The tasks for the reacher environment are equivalent, except that there are no obstacles for the reacher to avoid.
third task the "OR" task, (( V)
The sequential task meant to show that planning efficient and effective even for long-ting time horizon tasks. The "IF" task shows that the agent's policy can respond to event propositions, such as being alerted that a delivery is cancelled. The "OR" task meant demonstrate the optimality of our algorithm versus a greedy algorithm, discussed in Fig. Lastly, the composite task shows that learning and planning are efficient and effective even for complex tasks.
We test four baselines against our algorithm. We call our algorithm LOF-VI, short for "Logical Options Framework with Value Iteration," because it uses value iteration for its high- level planning. Our first baseline, LOF-QL, uses Q-learning instead (details can be found in Ap- pendix C Unlike LOF-VI, COF-QL does not need explicit knowledge Tr. the transition function of the FSA. Greedy is naive implementation of task satisfaction; it uses its knowledge
Baselines:

---

Under review as a conference paper at ICLR 2021
of the FSA to select the next subgoal with the lowest cost to attain. This leaves it vulnerable to choosing suboptimal paths through the FSA, as shown in Fig. 3 Flat Options uses the regular options framework with no knowledge of the FSA. In other words, its SMDP formulation is not hierarchical the state space and transition function do not contain high-level states FF or transition function Tr. The last baseline is RM, short for Reward Machines (Icarte al. 2018). Whereas LOF learn options to accomplish subgoals, RM learns subpolicies for every FSA state. Appendix C.2 discusses the differences between RM and LOF in detail.
Implementation: For the delivery domain, options were learned using Q-learning with an e-greedy exploration policy. Options were learned simultaneously while switching the option used for explo- ration at every episode. RM was learned using the Q-learning for Reward Machines (QRM) algorithm described in ( et al. 2018). For the reacher domain, options were learned by using proximal policy optimization (PPO) (Schulman et al. (017)) to train goal-oriented policy and value functions, which were represented using a 128 x 128 fully connected neural network. Beep-QRM was used to train RM. The implementation details are discussed more fully in Appendix C
4.1 RESULTS
Results for the satisfaction experiments, averaged over all four tasks, are shown in Figs. and 2e] (Results on all tasks are in Appendix C.6). As expected, Flat Options shows no ability to satisfy tasks, as it has no knowledge of the FSAs. Greedy trains as quickly as LOF-VI and LOF-QL, but its returns plateau before the others because chooses suboptimal paths in the composite and OR tasks. The difference is small in the reacher domain but still present. LOF-QL achieves as high a return as LOF VI, but it is less composable (discussed below). RM learns much more slowly than the other methods. This is because for RM, reward is only given for reaching the goal state, whereas in the bas-based methods, options are rewarded for reaching their subgoals, so during training LOF-based methods have a richer reward function than RM. For the reacher domain, RM takes an order of magnitude more steps to train, so we left it out of the figure for clarity (see Appendix Fig. 14p. However, in the reacher domain, RM eventually achieves higher return than the L.OF-based methods. This is because for the reacher domain, we define the subgoals to be spherical regions rather than single states, violating one of the conditions for optimality. Therefore, for example, it is possible that the metapolicy does not take advantage of the dynamics of the arm to swing through the subgoals more efficiently. RM does not have this condition and learns a single policy that can take advantage of inter-subgoal dynamics to learn more optimal policy.
Satisfaction:
Composability: The composability experiments were done on the three composable baselines, LOF-VI, LOF-QU, and Greedy. Appendix C.2 discusses why RM is not composable. Flat Options is not composable because its formulation does not include the FSA T. Therefore is completely incapable of recognizing and adjusting to changes in the FSA. The composability results are shown in Figs. 2c and 26 Greedy requires no retraining steps to "learn" a metapolicy on a new FSA given its current FSA state, it simply chooses the next available FSA state that has the lowest cost to achieve. However, its metapolicy may be arbitrarily suboptimal. LOF-QL learns optimal (or in the continuous case, close-to op-timmll) policies, but it takes 550-250 retraining steps, versus 10- 50 for LOF-VI, Therefore LOF-V strikes a balance between Greedy and LOF-QL, requiring far fewer steps than LOF-QL to retrain, and achieving better performance than Greedy.
5 RELATED WORK
We distinguish our work from related work in HRL by its possession of three desirable properties composability, satisfaction, and optimality.
The previous work most similar to ours is learte et al. 2018 2019). which introduces a method to solve tasks defined by automata called Reward Machines. Their method learns a subpolicy for every state of the automaton; by transferring rewards between automaton states, they can achieve satisfaction and optimality. However, the learned policies have limited composability because they are specific to the automaton; by contrast, LOF learns a subpolicy for every subgoal, independent of the automaton, and therefore the subpolicies can be arranged to satisfy arbitrary tasks. Another similar work is Logical Value Iteration (LVI) (Araki et al., 2019) 20220) LVI defines hierarchical MDP and value iteration equations that can find satisfying and optimal
Not Composable:
8

---

Under review as a conference paper at ICLR 2021
policies;
however, the algorithm is limited to discrete domains and has limited composability. A number of HRL algorithms use reward shaping to guide the agent through the states of an automaton
(Li al. 2017: 2019; Camacho et al. 2019 Hasanbeig et al. 2018 Jothimurugan et al., 2019; Shah et al. 2020 Yuan et al. 2019). While these algorithms can guarantee satisfaction and, under certain conditions, optimality, they also have limited composability. Another approach is to
symbolic planner to find satisfying sequence of tasks and use an RL agent to learn and execute that sequence of tasks (Gordon al. 2019; Illanes et al. 2020 Lyu al. 2019). However, the meta-controllers of Gordon et al. (2019) and Lyu et al. (2019) are not composable as they are trained together with the low-level controllers. Although the work of Iflanes et al. (2020) is amenable transfer learning, it is not composable. Paxton et al.] (2017); Mason et al. (2017) use logical constraints to guide exploration, and while these approaches are also satistying and optimal, they are not composable as the agent is trained for a specific set of rules.
Not Satisfying: Most hierarchical frameworks cannot satisfy tasks. Instead, they focus on using state and action abstractions to make learning more efficient (Dietterich) 20000 Dayan & Hinton 1993 Parr & Russell 1998; Diuk et al. 2008 Oh et al. 2019). The options framework (Sutton et al. 1999) stands out because of its composability and its guarantee of hierarchical optimality, which is why we based our work off of it. There is also a class of HRL algorithms that builds on the idea of goal-oriented policies that can navigate to nearby subgoals (Eysenbach et al.) 2019] Ghosh et al. [0118] Faust et al.] (018)). By sampling sequences of subgoals and using a goal-oriented policy to navigate between them, these HRL algorithms can travel much longer distances than a goal-oriented policy can travel on its own. Although these algorithms are "comppsable" in that they can navigate to arbitrary goals without further training, they are not able to solve tasks, and therefore none of them are capable of satisfying task specifications. (Andreas et al. (2017) presents an algorithm for solving simple task "sketches" which is also composable; however, sketches are considerably less expressive than automata and linear temporal logic, which we use.
In HRI., there are at least three types of optimality - hierarchical, recursive, and overall. As defined in Dietterich (2000), the hierarchically optimal policy is the optimal policy given the constraints of the hicrarchy, and recursive optimality is when the policy is locally optimal given the policies of its children. For example. the options framework is hierarchically optimal, while MAXQ and abstract MDPs (Gopalan et al., 2017) are recursively optimal. The method described in Kuo et al. (2020) is fully composable, but not optimal as it uses recurrent neural network to generate a sequence of high-level actions and is therefore not guaranteed to find optimal policies.
Not Optimal:
6 DISCUSSION AND CONCLUSION
In this work claim that the Logical Options Framework has unique combination of three prop- erties: satisfaction, optimality, and composability. We state and prove the conditions for satisfaction and optimality in 3.1. The experimental results confirm our claims while also highlighting some weaknesses. LOF-VI achieves optimal or near-optimal policies and trains an order of magnitude faster than the existing work most similar it, RM. However, the optimality condition that each sub- goal be associated with exactly one state cannot be met for continuous domains, and therefore RM eventually outperforms LOF-VI. But even when optimality is not guaranteed, LOF-VI VVI always hierarchically optimal, which is why it outperforms Greedy in the composite and OR tasks. Next, the composability experiments show that LOF-VI can compose its learned options to accomplish new tasks in very few iterations- about 10-50. Although Greedy requires no retraining steps, it a tiny fraction of the tens of thousands of steps required to learn the original policy. Lastly, we have shown that LOF can learn policies efficiently, and that it can be used with a variety of domains and policy-lcarning algorithms. In fact, any policy-learning algorithm where it is possible to extract value (expected eumulative reward) for the policy's 's execution on the subgoals is fully compatible with LOF, including value iteration and PPO.
Thus, we have proven and demonstrated LOF's features of satisfaction, optimality, and compos- ability, while also reviewing the compromises involved in achieving this goal. We hope that this framework can be useful in practical settings that governed by complex and changeable rules.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
David Abel and John Winder. The expected-length model of options. In IJCAI, 2019.
Bowen Alpern and Fred B Schneider. Recognizing safety and liveness. Distributed compuring, (3):117-126, 1987.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International Conference on Machine Learning, pp. 166-175, 2017.
Brandon Araki, Kiran Vodrahalli, Thomas Leech, Cristian loan Vasile, Mark Donahue, and Daniela Rus. Learning plan with logical automata. In Proceedings Robotics: Science and Systems, FreiburgimBreisggau Germany, June 2019. doi: 10. 10.15607/RSS..019.XX
Brandon Araki, Kiran Vodrahalli, Thomas Leech, Cristian loan Vasile, Mark Donahue, and Daniela Rus. Deep bayesian nonparametric learning of rules and plans from demonstrations with learned automaton prior. In AAAI, pp. 10026,10034, 2020.
C. Baier and J. Katoen. Principles of model checking. MIT Press, 2008. ISBN 978-0-262-00649--9
Amit Bhatia, Lydia E. Kavraki, and Moshe Vardi. Sampling-based motion planning with temporal goals. In 2010 IEEE International Conference on Robotics and Automation, pp. 2689-2696. IEEE, 2010.
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A Mcllraith. Ld and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI, volume 19, pp. 6065-6073, 2019.
Edmund M. Clarke, Orna Grumberg, and Doron Peled. Model Checking. MIT Press, 2001. ISBN 21880-262-0320--4
Peter Dayan and Geoffrey Hinton. Feudal reinforcement learning. In Advances in neural infor- mation processing systems, pp. 271-278, 1993.
Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decompo- sition. Journal of artificial intelligence research, 13:227-303, 2000.
Carlos Diuk, Andre Cohen, and Michael L Littman. An object-oriented representation for efficient reinforeement learning. In Proceedings of the 25th international conference on Machine learning, pp. 240-247, 2008
Alexandre Duret-Lutz, Alexandre Lewkowicz, Amaury Fauchille, Thibaud Michaud, Etienne Re- nault, and Laurent Xu. Spot 2.0 framework for LTL and w-automata manipulation. In Proceedings of the 14th International Symposium on Automated Technology for Verification and Analysis (ATVA 16), volume 9938 of Lecture Notes in Computer Science, pp. 122-129. Springer, October 2016. doi: 11.110779988-331--44552
Ben Eysenbach, Russ Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems, pp. 15220-15233 2019.
Aleksandra Faust, Kenneth Oslund, Oscar Ramirez, Anthony Francis, Lydia Tapia, Marek Fiser, and James Davidson. Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-basee planning. 2018 IEEE International Conference on Robotics and Automation (ICRA). pp. 51 13 5120. IEEE, 2018
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal- conditioned policies. arXiv preprint 1r11v:1811.07819 2018
Nakul Gopalan, Michael L Littman, James MacGlashan, Shawn Squire, Stefanie Tellex, John Winder, Lawson LS Wong, et al. Planning with abstract markov decision processes. In Twenty- Seventh International Conference on Automated Planning and Scheduling. 2017.
Daniel Gordon, Dieter Fox, and Ali Farhadi. What should do now? marrying reinforcement
learning and symbolic planning. arXiv preprint arXiv: 1901009901 2019.
10

---

Under review as a conference paper at ICLR 2021
Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Logicclly-constrainee inforcement learning. arXiv preprint arXiv: 2018.
Rodrigo Toro Iearte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward ma- chines for high-level task specification and decomposition in reinforcement learning, In Interna- tional Conference on Machine Learning, pp. 2107-2116, 2018.
Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, and Sheila Mcllraith. Learning reward machines for partially observable reinforcement learning. In Advances in Neural Information Processing Systems, pp. 15523-15534, 2019.
León Illanes, Xi Yan, Rodrigo Toro Icarte, and Sheila Mcllraith. Symbolic plans as high-level instructions for reinforcement learning. In Proceedings of the International Conference on Auto- mated Planning and Scheduling, volume 30, pp. 540-550, 2020.
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. In Advances in Neural Information Processing Systems, pp. 13041- 13051, 2019.
Bilal Kansoand Ali Kansou. Converting asubset of ld formula to buchi automata. International Journal of Software Engineering & Applicaaiins (IJSEA), 10(2), 2019.
Yen-Ling Kuo, Boris Katz, and Andrei Barbu, Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of Itl formulas. arXiv preprint arXiv:2006.01 010, 2020.
Xiao Li, Cristian-loan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3834- 3839. IEEE, 2017.
Xiao Li, Zachary Serlin, Guang Yang, and Calin Belta. A formal methods approach to interpretable reinforcement learning for robotic planning. Science Robotics, 4(37), 2019.
Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson. Sdrl: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 33. pp. 2970-2977, 2019.
George Rupert Mason, Radu Constantin Calinescu, Daniel Kudenko, and Alec Banks. Assured reinforcement learning with formally verified abstract policies. In 9th International Conference on Agents and Artificial Intelligence (ICAART). York, 2017.
Yoonseon Oh, Roma Patel, Thao Nguyen, Baichuan Huang, Ellie Pavlick, and Stefanie Tellex. Planning with state abstractions for non-markovian task specifications. arXiv preprint 1905. /2096, 2019.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, pp. 1049-1049, 1998.
Chris Paxton, Vasumathi Raman, Gregory D Hager, and Marin Kobilarov. Combining neural networks and tree search for task and motion planning in challenging environments. 2017 IEFF/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 6059-6066. IEEE, 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
Ankit Shah, Shen Li, and Julie Shah. Planning with uncertain specifications (puns). IEEE Robotics and Automation Letters, 5(2):3414-3421, 2020.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
Lim Zun Yuan, Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Modular deep reinforcement learning with temporal logic specifications. arXiv preprint ww.Xiv:109..13:0 2019.
11

---

Under review as a conference paper at ICLR 2021
Shiqi Zhang and Mohan Sridharan. A survey of knowledge- based sequential decision making under uncertainty. Xrxiv preprint arXiv:2008 08548, 2020.
A FORMULATION OF LOGICAL OPTIONS FRAMEWORK WITH SAFETY AUTOMATON
In this section, we present a more general formulation of LOF than that presented in the paper. In the paper, we make two assumptions that simplify the formulation. The first assumption is that the LTL specification can be divided into two independent formulae, a liveness property and a safety property: o Oliveness A feaf. However, not all LTL formulac can be factored in this way. We show how LOF can be applied to LTL formulae that break this assumption. The second assump- tion is that the safety property takes simple form that can be represented as a penalty on safety propositions. We show how LOF can be used with arbitrary safety properties.
A.1 AUTOMATA AND PROPOSITIONS
All LTL formulae can be translated into Büchi automata using automatic translation tools such as SPOT (Duret-Lutz et al. (016). All Büchi automata can be decomposed into liveness and safety properties (Alpern & Schneider, 1987). so that automaton W = Wisennss X Wsafety- This is generalization of the assumption that all LTL formulae can be divided into liveness and safety properties Uliveness and @safety. The liveness property Wiivenes must be an FSA, although this assumption could also be loosened to allow it to be a deterministic Büchi automaton via some minor modifications (allowing multiple goal states to exist and continuing episodes indefinitely, even once goal state has been reached).
As in the main text, we assume that there are three types of propositions - subgoals Pc. safety propositions Ps. and event propositions Pg. The event propositions have set values and can occur in both Wiveness and Wsafety- Safety propositions only appear in Wsafety- Subgoal propositions only appear in Wiiveness- Each subgoal may only be associated with one state. Note that after writing a specification and decomposing it into Wiseness and feafety, it is possible that some subgoals may unexpectedly appear in feaye This can be dealt with by creating "safety twins" of each subgoal - safety propositions that are associated with the same low-level states as the subgoals and can therefore substitute for them in Weafety-
Subgoals are propositions that the agent must achieve in order to reach the goal state of W Wivensss Although event propositions can also define transitions in Wiieeness we assume that "achieving" them is not necessary in order to reach the goal state. In other words, we assume that from any state in Wineneas: there is a path to the goal state that involves only subgoals. This is because in our formulation, the event propositions are meant to serve as propositions that the agent has no control over, such as receiving a phone call. If satisfaction of the liveness property were to depend on such a proposition, then it would be impossible guarantee satisfaction. However, if the user is unconcerned with guaranteeing satisfaction, then specifying a liveness property in which satisfaction depends on event propositions is compatible with LOF.
Safety propositions may only occur in Wsafety and are associated with things that the agent "must avoid". This is because every state of Wsafety is an accepting state (Alpem & Schneider 1987). so all transitions between the states are non-violating. However, any undetined transition is not allowed and is a violation of the safety property. In our formulation, so that violations are allowed but come at a cost. In practice, it also may be the case that the agent in low-level state from which it is impossible reach the goal state without violating the safety property. In our formulation, satisfaction of the liveness property (but not the safety property) is still guaranteed in this case, as the finite cost associated with violating the rule is less than the infinite cost of not satisfying the liveness property, so the optimal policy for the agent will be to violate the rule in order to satisfy the task (see the proofs, Appendix B This scenario can be avoided in several ways. For example, do not specify an environment in which it is only possible for the agent to satisfy the task by violating a rule. Or, instead of prioritizing satisfaction of the task, it is possible to instead prioritize satisfaction of the safety property. In this case, satisfaction of the liveness property would not be guaranteed but satisfaction of the safety property would be guaranteed. This could be accomplished by terminating the rollout if safety violation occurs.
assign costs to violations.
12

---

Under review as a conference paper at ICLR 2021
We assume that event propositions are observed in other words, that know the values of the event propositions from the start of a rollout. This is because we are planning in a fully observable setting, so must make this assumption to guarantee convergence to optimal policy. However, the partially observable case is much more interesting, in which the values of the event propositions not known until the agent checks or the environment randomly reveals their values. This case is beyond the scope of this paper, however, LOF can still guarantee satisfaction and composability in this setting, just not optimality.
5-225 2Pa, Tps :S + + and Proposition labeling functions relate states to propositions: TPc - Tpg 22 + 10.
Given these definitions of propositions, it is possible to define the liveness and safety properties formally. Wiseenes: = (F, Pa Up, TF, Ry, for fa). the set of states of the liveness property. The propositions can be either subgoals Pa or event propositions Pg. The transition function relates the current FSA state and active propositions to the next FSA state, Tp F Fx22c x2 x + [0, 1]. The reward function assigns a reward to the current FSA state, Re F R. We assume there is one initial state fo and one goal state fg-
The safety property is a Büchi automaton Wsafety, states of the automaton. The propositions can be safety propositions Ps or event propositions PE- The transition function T's relates the current state and active propositions to the next state, Is : Fs x 2 x 2n x Fs + [0, 1]. The reward function relates the automaton state and safety propositions rewards (or costs), Rg Fs x 2Ps R. Fo defines the set of initial states. We do not specify an accepting condition because for safety properties, every state an accepting state.
(Fs, U PF, Ts. Rs, Fo). Fs are the
A.2 THE ENVIRONMENT MDP
There is a low-level environment MDP A, Rg, TE, 7) S is the state space and A is the action space. They can be either discrete or continuous. Rg is the low-level reward function that characterizes, for example, time, distance, or actuation costs. TE S x A x S + [0, 1] is the transition function and is the discount factor. Unlike in the simpler formulation in the paper, we do not combine Rg and the safety automaton reward function Rs in the MDP formulation E.
A.3 LOGICAL OPTIONS
We associate every subgoal Pg with an option Op,, (Ipp:: Tp. 3pg Rg. Tp.). Every Op, has a policy Fp, whose goal is to reach the state Sp, where Py is true. Option policies are learned by training on the product of the environment and the safety automaton, E x Weafety and terminating training only when 8p, is reached. Re Fs S x A + I is the reward function of the product MDP & x Wsafety. There are many reward-shaping poliey-learning algorithms that specify how to define Rg. In fact, learning a policy for E x /ety is the sort of hierarchical learning problem that algorithms excel at, including Reward Machines (Icarte et al. 2018) and (Li al. 2017). This is because in LOF, safety properties not composable, using a learning algo- rithm that is satisfying and optimal but not composable to learn the safety property is appropriate. Alternatively, there are many scenarios where Waafety is a trivial automaton in which each safety proposition is associated with its own state, as we describe in the main paper, so penalties can be assigned propositions and the state of the agent in Wsafety can be ignored.
many ceward-shaping
Note that since the options are trained independently, one limitation of our formulation is that the safety properties cannot depend on the liveness state. In other words, when an agent reaches new subgoal. the safety property cannot change. However, the workaround for this is not too compli- cated, First, the liveness state affects the safety property, this implies that liveness propositions such as subgoals may be in the safety property. In this case, as we described above, the subgoals present in the safety property need to be substituted with "safety twin" propositions. Then during option training, a policy-learning algorithm must be chosen that will learn subpolicies for all of the safety property states, even if those states are only reached after completing complicated task (for example, all of the subpolicies could be trained in parallel in (learte et al. 2018)). Lastly, during metapolicy learning and during rollouts, when a new option is chosen, the current state of the safety property must be passed to the new option.
13

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Learning and Planning with Logical Options
1:
2: Given:
Propositions P partitioned into subgoals Pa, safety propositions Ps, and event propositions Pg
Wivenees = [F, Pc Pg. IF R fo fg) Wsafety = (Fs, Ps PP T Rs, Fo)
Low-level MDP & (S,A, Rg TE TE, 7
Proposition labeling functions Tra S 2o, Trs : - 2P, and
TPs 2 {0,1}
3:
To learn:
4:
Set of options O, one for each subgoal proposition p E Pg
5:
Metapolicy juf, ; fa, 8, o) along with Q fer 8, o) and ((f, fe:
6:
Learn logical options:
7:
For every in Pa. learn an option for achieving p. op = (oo, Top Bay: Roy Top)
8:
Top S
Bag [1
if E (s)
9:
otherwise
10:
Top optimal policy on & Weafety with rollouts terminating when p Tpa (s)
p( k
i E Tr(s')
11:
Top 8 8))
0
otherwise
12:
(S. 8) ([RE(Sa, an) + RR (Ra,,, 02) + +............................... R
13:
Find a metapolicy μ over the options:
14:
Initialize Q: FF x Fs x S x R and V F x Fs x - R
15:
For (k, fff. [I...., x
16:
For o O:
17:
Ss,
Rr(f) + Eger Eger, Eper's Eves To p.)s Tps ( (d)), (
19:
Valf. fe, t- max (f.
fff.fs, arg max fo, oEO return Options O, metapolicy u(ʃ, Say 8, o), and Q(, Ss, 8a)))
21:
22:
end procedure
The components of the logical options are defined starting at Alg. line Note that for stochastic low-level transitions, the number of time steps at which the option terminates is stochastic and characterized by a distribution function. In general this distribution function must be learned, which a challenging problem. However, there are many approaches to solving this problem; (Abel & Winder 2019) contains an excellent discussion.
The most notable difference between the general formulation and the formulation the paper is that the option policy, transition, and reward functions functions of the safety automaton state fa as well as the low-level state s. This makes Logical Value Iteration more complicated, because in the paper, we could assume knew the final state of each option (i.e., the state of its associated subgoal kg). But now, although we still assume that the option will terminate at 8g. we do not know which safety automaton
will terminate in, so the transition model must learn a distribution over safety automaton states, and Logical Value Iteration must account for this uncertainty.
A.4 HIBRARCHICAL SMDP
Given a low-level environment E, a liveness property Wiivenese: a safety property Waa and logical options O, we can define a hierarchical semi-Markov Decision Process (SMDP) M E Wiveeness x Weafety with options O and reward function RSMDP. This SMDP differs significantly from the SMDP in the paper in that the safety property Wsafety is now an integral part of the (f...o..
formulation. ReMDr(J,
14

---

Under review as a conference paper at ICLR 2021
A.5 LOGICAL VALUE ITERATION
A value function and Q-function are found for the SMDP using the Bellman update equations:
E E Tr(fI),TPa(s))
FEF S d'ES
(sy Pe) (Pe)s ( (f Vi(ffJa:s) t max (x S.. oEO
(5)
(6)
B PROOFS AND CONDITIONS FOR SATISFACTION AND OPTIMALITY
The proof' are based on the more general LOF formulation of Appendix [A] as results on the more general formulation also apply to the simpler formulation used in the paper.
Definition B.1. Let the reward function of the environment be Re(Js, which is some combi- nation of Rg(s, a) and Rs(fe.P.) = Rs( (s. Let : FFs x S x S + [0, be the optimal goal-conditioned policy for reaching state 8'. In the case of a goal-conditioned policy, the reward function is Rg, and the objective is to maximize the expected reward with the constraint that s' is reached in finite amount of time. We assume that every state s' is reachable from any state standard regularity assumption in MDP literature. Let V (fs) be the optimal expected cumulative reward for reaching s' from s with goal coal-conditioned policy n². Let sy be the state asso- ciated with the subgoal, and let Ty be the optimal goal-conditioned policy associated with reaching 8g. Let x" be the optimal policy for the environment E.
Condition B.1. The optimal policy for the option must be the same as the goal-conditioned pol- icy that has subgoal $y as its goal: T'" (fs Tgg (f( s|sg). In other words, V (fss s|sy) >
Va s(s) Vfs 8, + 8g.
This condition guarantees that the optimal option policy will always reach the subgoal 8y- It can be achieved by setting all rewards -o < (f,, 8, a) < 0 and terminating the episode only when the agent reaches 5g. Therefore the expected return for reaching 8y a bounded negative number, and the expected return for all other states is -00.
Lemma B.2. Given that the goal state of Wiiveness is reachable from any other state using only subgoals and that there is an option for every subgoal and that all the options meet Condition B. there exists metapolicy that can reach the FSA goal state from any non-tre non-trap state in the FSA.
Proof. This follows from the fact that transitions in Wisvensss are determined by achieving subgoals, and it is given that there exists an option for achieving every subgoal. Therefore, it is possible for the agent to execute any sequence of subgoals, and at least one of those sequences must satisfy the task specification since the FSA representing the task specification is finite and satisfialle, and the goal state fg is reachable from every FSA state ʃ E F using only subgoals.
Definition B.2. From Dietterich (2000): A hierarchically optimal policy for MDP SMDP is a policy that achieves the highest cumulative reward among all policies consistent with the given hierarchy.
In our case, this means that the hierarchically optimal metapolicy is optimal over the available op- tions.
Definition B.3. Let the expected cumulative reward function of an option o started at state (fe, be R). Let the reward function on the SMDP be RSMDP(f. s. = Ro with Rf( 2 ( Let pl FF x Fs x O x F - [0, 1] be the hierarchically optimal goal- conditioned metapolicy for achieving liveness state f". The objective of the metapolicy is to max- imize the reward function RSMDP with the constraint that it reaches f in a finite number of time
'The assumption that RSMDr(f, f,) = (off) and RHMDr(f, s,, Rr( Re (fs, a, a) can be relaxed so that RSMDP and RHMDP are functions that are monotonic increas- ing in the low-level rewards R. and Re, respectively.
15

---

Under review as a conference paper at ICLR 2021
steps. Let Vi fs; be the hierarchically optimal return for reaching f' from (f.fe fe.s) with goal-conditioned metapolicy mai. Let μ be the hierarchically optimal policy for the SMDP. Let fg be the goal state, and Py be the hierarchically optimal coal-conditooned metapolicy for achieving the goal state.
Condition B.3. The hierarchically optimal metapolicy must be the same as the goal-conditioned metapolicy that has the FSA goal state Ig its goal: (1,58) 1g Jss 8|5 In other words, (J, fو5 V (s, V,, [g-
This condition guarantees that the hierarchically optimal metapolicy will always go the FSA goal state fg (thereby satisfying the specification). Here is an example of how this condition can be achieved: If -oo <. Re(Ss; 8, a) < 0 Vs, then [o( 8) our experiments, we set Rf( 1 Ay). RSMDr( J.. 8, 0, Then Rr(f) > 0 (in (o s) < O. and if the episode only terminates when the agent reaches the goal state, then the expected return for reaching fg is a bounded negative number, and the expected return for all other states is -cc
Lemma B.4. From (Sutton et al. 1999): Value iteration on an SMDP converges to the hierarchically optimal policy.
Therefore, the metapolicy found using the Logical Options Framework converges a hierarchically optimal metapolicy that satisfies the task specification as long as Conditions B. and B.3 are met.
Definition B.4. Consider the SMDP where planning is allowed over the low-level actions instead of the options. We will call this the hierarchical MDP (HMDP), as this MDP the product of the low-level environment E, the liveness property Wiinenesss and the safety property Ws fety Let Re 8, a), and let n HHDP be the optimal
Rr(J)= > JJ, and let SImDDPU;ssss policy for the HMDP.
Theorem B.5. Given Conditions B. and B.3 the hierarchically optimal metapolicy 1'g with optimal option policies ng has the same expected returns as the HMDP optimal policy n² and satisfies the task specification.
Proof. By Condition B.I. every subgoal has an option associated with it whose optimal policy is to go the subgoal. By Condition B.3 the hierarchically optimal metapolicy will reach the FSA goal state fg. The metapolicy can only accomplish this by going to the subgoals a sequence that satisfies the task specification. It does this by executing sequence of options that correspond to satisfying sequence of subgoals and are optimal in expectation. Therefore, since Rf( > Vf and RSMDP(J, Ss, 0) R (R 8), and since the event propositions that affect the order of subgoals necessary to satisfy the task are independent random variables, the expected cumulative reward is a positive linear combination of the expected option rewards, and since all option rewards are optimal with respect to the environment and the metapolicy is optimal over the options, our algorithm attains the optimal expected cumulative reward.
C EXPERIMENTAL IMPLEMENTATION
We discuss the implementation details of the experiments in this section. Because the delivery and reacher domains analogous, we discuss the delivery domain first in every section and then briefly relate how the same formulation applies to the reacher domain as well. In this section, we use the simpler formulation of the main paper and not the more general formulation discussed in Appendix A
C.1 PROPOSITIONS
The delivery domain has 7 propositions plus 4 composite propositions. The subgoal propositions are Pa = {a, b, c, h.. Each of these propositions is associated with single state in the environment (see Fig. 12a). The safety propositions are Ps eo. is the obstacle proposition. It is associated with many states the black squares Fig. 12a e is the empty proposition, associated with all of the white squares in the domain. This is the default proposition for when there are no other active propositions. The event proposition is Pe {can). can is the "cancelled" proposition, representing when one of the subgoals has been cancelled.
16

---

Under review as a conference paper at ICLR 2021
To simplify the FSAs and the implementation, make assumption that multiple propositions cannot be true at the same state. However, it is reasonable for can to be true at the subgoals, and therefore we introduce 4 composite propositions, ca a A can, cb b A can, ce c A can, ch = h A can. These can be counted as event propositions without affecting the operation of the algorithm.
The reacher domain has analogous propositions. The subgoals are r, b. and correspond to a, b, c, h. The environment does not contain obstacles o but does have safety proposition e, and it also has the event proposition can and the composite propositions cr, eg, cb, cy for when can true at the same time that a subgoal proposition is true. Another difference is that the subgoal propositions are associated with small spherical region instead of a single state as in the delivery domain; this necessity for continuous domains and unfortunately breaks one of our conditions for optimality because the subgoals are now associated with multiple states instead of a single state. However, the LOF metapolicy will still converge to a hierarchically optimal policy.
C.2 REWARD FUNCTIONS
Next, we define the reward functions of the physical environment Rg, safety propositions Rs, and FSA states Rp. We realize that often in reinforcement learning, the algorithm designer has no control over the reward functions of the environment. However, in our case, there are no publicly available environments such as OpenAl Gym the DeepMind Control Suite that we know of that have a high-level FSA built-in. Therefore. anyone implementing our algorithm will likely have to implement their own high-level FSA and define the rewards associated with it.
Our low-level enviromment reward function Rg : S x A + R is defined to be -1 Vs, a. In other words, it a time/distance cost.
We assign costs to the safety propositions by defining the reward function Rs Ps + R. All of the costs are except for the obstacle cost, Rs(o) = 1000. Therefore, there is a very high penalty for encountering obstacle.
We define the environment reward function Rg : S A Rs(Tr(s)), In other words, it is the sum of Rg and Rs. This reward function meets Condition B.1 for the optimal option policies to always converge to their subgoals.
to be R = (s(8, a) +
Lastly, we define Rr F + R to be RF(s)- 1 Vf. Therefore the SMDP cost RgM 8,0) (s) and meets Condition B.3 so that the LOF metapolicy converges to the optimal policy.
The reacher environment has analogous reward functions. The safety reward function Rs(p) 0 Vp E Ps because there is no obstacle proposition. Also, the physical environment reward function differs during option training and metapolicy learning. For metapolicy learning, the reward function is (g a) = -a' a 0.1 - a time cost and an actuation cost. During option training, we speed learning by adding the distance to the goal state
cost, instead of time cost: Rg(s, a) -a a ||s - syl Although the reward functions and value functions are different, the costs are analogous and lead good performance as seen in the results. Note that this method can't be used for Reward Machines, because it trains subpolicies for FSA states, and the subgoals for FSA states are not known ahead of time, so distance to subgoal cannot be calculated.
C.3 ALGORITIM FOR LOF- QL
The LOF-QL baseline uses Q-learning to learn the metapolicy instead of value iteration. We there- fore use "Logical Q-Learning" equations in place of the Logical Value Iteration equations described in Eqs. and 4 in the main text. The algorithm is described in Alg. 3 A benefit of using Q-lerriing instead of value iteration is that the transition function Tr of the FSA T does not have to be ex- plicitly known, the algorithm samples from the transitions rather than using Tp explicitly in the formula. However, as described in the main text, this comes at the expense of reduced compos- ability, LOF-QQ. takes around 5z more iterations to converge to new metapolicy than LOF-VT
17

---

Under review as a conference paper at ICLR 2021
Algorithm 3 LOF with e-greedy Q-learning
1: procedure LOF-Q-LEARNING
2: Given:
Propositions P partitioned into subgoals Pa, safety propositions Ps, and event propositions PE Environment MDP & = (S, A.TE, Rg, 7)
Logical options O with reward models (o(s) and transition models (s's'ss Liveness property T (F, Pg U UPE, Tr, Rr, fo. fg) (Tr does not have be explicitly known it can be sampled from a simulator) Learning rate a, exploration probability
Number of training episodes n, episode length m
To learn:
4:
Metapolicy ju(f, s, along with Q(f, s, o) and (ff.s) Find a metapolicy μl over the options:
5:
6:
Initialize Q F x S x O - IR and V x S R to
7:
For l E [1.....n] m]]
8:
Initialize FSA state f 0, random initial state from & Pe TTpp ()
9:
10:
For E mi]:
11:
With probability e let o be a random option; otherwise, t arg max Q(f,s,o')
d'E0
12:
8' To(s)
13:
Ty Qa(J,8,0) +
14:
15:
Vx(f,s) + max Qu(fss,)) d'E0
16:
f"
17:
8,) = arg max {,,)
oEO
18:
return Options O, metapolicy μ(f, 8, 0) and Q- and value functions @(),s,o), V(f.s)
19:
end procedure
does. Let Qo(fss, o) be initialized to be all Os. The Q update formulas are given in Alg. lines 14 and 15
C.4 COMPARISON OF LOF AND REWARD MACHINES
Figs. and give a visual overview of how LOF and Reward Machines work, and hopefully illustrate how they differ.
Go grocery shopping OR pick up the kid, then go home.
reb
a
S1
(a) Environment MDP E.
(b) Liveness property T. The natural language rule can be repre- sented as LTL formula which can be translated into FSA.
Figure 4: LOF and RM both require an environment MDP & and an automaton T that specifies task.
18

---

Under review as a conference paper at ICLR 2021
SO
S1
or
Goal State
t
Figure 5: In RM, subpolicies are learned for each state of the automaton. In this case, in state S0, subpolicy is learned that goes either the shopping cart of the kid, whichever closer. In state $1, the subpolicy goes to the house.
option
option
option
t
(a) Step 1 of LOF: Learn logical option for each subgoal.
SO
S1
Goal State
(b) Step 2 of LOF: Use Logical Value Iteration to find metapolicy that satisfies the liveness property. In this image, the boxed subgoals indicate that the corresponding option the optimal option to take from that low- level state. The policy ends up being "grocery shoppping" option the grocery cart is closer and the "pick up kid" option if the kid closer. In the state 51, the optimal metapolicy is to always choose the "home" option.
same RM's policy state S0, optimal metapolicy chooses
Figure 6: LOF has two steps. In (a) the first step, logical options are learned for each subgoal. (b) the second step, metapolicy is found using Logical Value Iteration.
C.5 TASKS
We test the environments four tasks, "sequential" task (Fig. 8). "IF" task (Fig. 9). "OR" task (Fig. 10). and a "composite" task (Fig. IT]. The reacher domain has the same tasks, expect r. b, y replace a, b, c, h, and there safety property safftty the preceding part of the formula is the liveness property @liveness used to construct the FSA.
obstacles Note that in the LTL formulae, Dlo is the
19

---

Under review as a conference paper at ICLR 2021
Go home OR pick up the kid, then go grocery shopping
or
so
6
(a) LOF can casily solve this new liveness property without training new options.
SO
S1
or
Goal State
(b) Logical Value Iteration can be used to find a metapolicy on the new task without the need to retrain the logical options. A metapolicy be found in 10-50 iterations. The policy finds that in state So, "home" option optimal the agent closer to "home", and the "kid" option optimal if the agent closer "kid". state $1, the "grocery shopping" option is optimal everywhere.
Figure 7: What distinguishes LOF from RM is that the logical options of LOF can be easily composed to solve new tasks. this example, the new task is to go home or pick up the kid, then go grocery shopping. Logical Value Iteration can find new metapolicy in 10-50 iterations without needing to relearn the options.
h
init
81
82
83
goal
Figure 8: FSA for the sequential task. The LTL formula (a A @b A (cc natural language interpretation is "Deliver package then b, then c, and then return home h. And always avoid obstacles o".
A (h))) Dlo. The
C.6 FULL EXPERIMENTAL RESULTS
For the satisfaction experiments for the delivery domain, 10 policies were trained for each task and for each baseline. Training was done for 1600 episodes, with 100 steps per episode. Every 2000 training steps, the policies were tested on the domain and the returns recorded. For this discrete domain, we know the minimum and maximum possible returns for each task, and we normalized the returns using these minimum and maximum returns. The error bars are the standard deviation of returns over the 10 policies' rollouts.
For the satisfaction experiments for the reacher domain, a single policy was trained for each task and for each baseline. The baselines were trained for 900 epochs, with 50 steps per epoch. Every 2500 training steps, each policy was tested by doing 10 rollouts and recording the returns. For the RM baseline, training was for 1000 epochs with 800 steps per epoch, and the policy was tested every 8000 training steps. Because we don't t know the minimum and maximum rewards for each task, did not normalize the returns. The error bars are the standard deviation over the 10 rollouts for each baseline.
For the composability experiments, a set of options was trained once, and then metapolicing training using LOF VT, LOF- -QT, and Greedy done for each task. Returns recorded at every
20

---

Under review as a conference paper at ICLR 2021
cV (ean A ma)
$3
can
a A cann
init
81
goal
C -can
V can
$2
A can
Figure 9: FSA for the task. The LTL formula is (0(c A Qa) llean) V (0a A Ocan) Ulo. The natural language interpretation is "Deliver package c, and then a, unless a gets cancelled. And always avoid obstacles o".
V b
init
91
goal
Figure 10: FSA for the OR task. The LTL formula is (((a b) A Qc) Olo. The natural language interpretation is "Deliver package or b. then c, and always avoid obstacles o".
A -can
c A Caa
b) A nen
81
$2
$3
h V cmn
can
CV (cam A -h)
/ can
init
goal
(a v b) A can
can A ma A b
b
aVb
SA
85
Figure 11: FSA for the composite task. The LTL formula (0((a V ((e Qh)) A [lean) (0((a V 6) A (h) A Ocan) A Elo. The natural language interpretation is "Deliver package or b, and then e, unless c gets cancelled, and then return to home h. And always avoid obstacles".
training step by rolling out each baseline 10 times. The error bars the standard deviations on the 10 rollouts.
Code and videos of the domains and tasks are in the supplement.
D FURTHER DISCUSSION
21

---

Under review as a conference paper at ICLR 2021
Average normal lood poward
Ausrage eormall Doed reward
0.0
0.4
0.4
80
0.1
1.4
training
165
training
(a) Delivery domain.
(b) Averaged.
(c) Composite.
Average namaalaos roward
Aweraen adje normalaees arwaard
10
nemaliees
0.6
0.4
0.2
0.0
CA
06
08
10
12
144
9.00
02
64
066
0.8
10
12
14
5.0
02
0.4
06
15
12
14
Number training steps
Number training stops
Number of training steps
(d) OR.
IF
(f) Scquential.
LOF-VI
LOF-QL
Greedy
Flat Options
Reward Machines
Figure 12: All satisfaction experiments on the delivery domain. Notice how for the composite and OR tasks (Figs. 12c and [2d], the Greedy baseline plateaus before LOF-VI and LOF-QL. This is because creedy chooses suboptimal path through the FSA, whereas LOF VVI and LOF-QU QL find an optimal path. Also, notice that takes many more training steps achieve the optimal cumulative reward. This is because for RM, the only reward signal is from reaching the goal state. takes long time for the agent to learn an optimal policy from such sparse reward signal. This is particularly evident for the sequential task (Fig. 12h which requires the agent to take longer sequence of actions/FSA states before reaching goal. The options- based algorithms train much faster because when training the options, the agent receives a reward for reaching each subgoal, and therefore the reward signal is much richer.
Avcroag reward
Averoga raward
60
80
-100
-100
training stops
training stops
(a) Reacher domain.
(b) Averaged.
(c) Composite.
-20
Average roward
Avarage reward
-40
-40
-50
-00
-20
Number
Number traming
106
Number training
104
(d) OR.
(e) IF
(f) Sequential.
LOF-VI
LOF-QL
Greedy
Flat Options
Figure 13: Satisfaction experiments for the reacher domain, without RM results. equivalent to the results on the delivery domain.
The results
What happens when incorrect rules are used? One benefit of representing the rules of the en- vironment as LTL. formulac/automata is that these forms of representing rules much more in-
22

---

Under review as a conference paper at ICLR 2021
23
Avergge reward
Average reward
-100
-100
-22
122
-10
-10
Number
165
Number training
165
(a) Reacher domain.
(b) Averaged.
(c) Composite.
23
rcward
Narrgg reward
Averaga
-10
122
-150
-150
-19
-175
-17
200
-20
200
165
105
(d) OR.
(c) IF
(f) Sequential.
LOF-VI
LOF-QL
Greedy
Flat Options
Reward Machines
Figure 14: Satisfaction experiments for the reach domain, including RM results. RM takes signifi- cantly more training steps to train than the other baselines, although it eventually reaches and sur- passes the cumulative reward of the other baselines. This is because for the continuous domain, violate some of the conditions required for optimality when using the Logical Options Framework particular, the condition that each subgoal associated with single state. In continuous environment, this condition is impossible to meet, and therefore we made the subgoals small spher- ical regions, and we only made subgoals associated with specific Cartesian coordinates and not velocities (which are also in the state space). Meanwhile, the optimality conditions of RM are looser and were not violated, which why it achieves a higher final cumulative reward.
Average normalzzs rewarD
3.0
Awerage natmallzedd EaWarS
3.0
0.6
0.4
0.4
0.
to
183
190
200
200
300
0.0
50
102
150
200
250
Number of metepolicy retreining steps
Number metepolcy retrwining steps
(a) Delivery domain.
(b) Averaged.
(c) Composite.
1.
Average normalaide reward
Average mndemaadddd rahaard
0.4
0.2
100 150
200
23C
302
102
130
230
300
0.0
50
102
200
220
300
Number of metapolicy retr aining steps
Number of metapolicy netr aininng steps
Numbar of metapolicy retraining steps
(d) OR.
IF.
(f) Sequential.
LOF-VI
LOF-QL
Greedy
Figure 15: All composability experiments for the delivery domain.
terpretable than alternatives (such neural nets). Therefore, if an agent's learned policy has bad behavior, a user LOF can inspect the rules to see if the bad behavior is consequence of a bad rule specification. Furthermore, of the consequences of composability is that any modifications
23

---

Under review as a conference paper at ICLR 2021
-30
Avergge rewerd
-20
Average reward
-30
-40
-50
-00
-70
Number metapolicy retreining
Number
(a) Delivery domain.
(b) Averaged.
(c) Composite.
-10
-10
-10
-20
Average reeard
-20
Average reward
-20
-30
-30
-40
-00
-30
Number retraining steps
Number
steps
metapalicy steps
(d) OR.
(c) IF
(f) Sequential.
LOF-VI
LOF-QL
Greedy
Figure 16: All composability experiments for the reacher domain.
the FSA will alter the resulting policy direct and predictable way. Therefore, for example, an incorrect specified task yields undesirable behavior, with our framework it is possible to tweak the task and test the new policy without any additional low-level training (however, tweaking the safety rules would require retraining the logical options).
What happens if there is a rule conflict? If the specified LTL formula is invalid, the LTL-to- automaton translation tool will either throw an error or return a trivial single-state automaton that is not an accepting state. Rollouts would terminate immediately.
What happens if the agent can't satisfy task without violating rule? The solution this problem depends on the user's priorities. In our formulation, we have assigned finite costs to rule violations and an infinite cost to not satisfying the task (see Appendix (B. We have prioritized task satisfaction over safety satisfaction. However, it is possible to flip the priorities around by termi- nating training/rollouts if there is a safety violation. In our proofs, we have assumed that the agent can reach every subgoal from any state, implying either that it is always possible to avoid safety violations or that safety violations are allowed.
Why is the safety property not composable? The safety property is not composable because allow safety propositions to be associated with more than state in the environment (unlike subgoals). The fact that there can be multiple instances of a safety proposition in the environment means that it impossible guarantee that new option policy will be optimal if retraining is done only at the level of the safety automaton and not also over the low-level states. In order to guarantee optimality, retraining would have to be done over both the high and low levels (the safety automaton and the environment). Our definition of composability involves only replanning over the high level of the FSA. Therefore, safety properties are not composable. Furthermore, rewards/costs of the safety property can be associated with propositions and not just with states (as with the liveness property). This because safety violation via one safety proposition (e.g., car going onto the wrong side of the road) may incur different penalty than violation via different proposition (a car going off the road). The propositions are associated with low-level states of the environment. Therefore any retraining would have to involve retraining at both the high and low levels, once again violating our definition of composability.
Simplifying the option transition model: In our experiments, we simplify the transition model by setting 7 1, assumption that does not affect convergence to optimality. In the case where
24

---

Under review as a conference paper at ICLR 2021
7 y= 1, Eq. 2 reduces to =x p(ss, Assuming that the option terminates only state Sg. then Eq further reduces to To($y]s) = and [s) = 0 for all other s' * $g. Therefore no learning is required for the transition model. For cases where the assumption that 7 does not apply, (Abel & Winder 2019) contains an interesting discussion.
=
The option reward model (o(s) the expected reward of it convenient if the policy-learning as well as policy (e.g., Q-learning and PPO). However, computed between pairs of states, not necessary to learn a complete value function. This because during Logical Value Iteration, the reward model is only queried at discrete points in the state space (typically corresponding to the initial state and the subgoals). So as long as expected returns between the initial state and subgoals can be computed, Logical Value Iteration will work.
Learning the option reward model:
carrying out option to termination from state s. It is equivalent to a value function. Therefore, algorithm used learn the options learns a value function
long the expected return can be
Why is LOF-VI so much more efficient than the RM baseline? In short, LOF-VT is more ef- ficient than RM because LOF-VI has dense reward function during training and RM has sparse reward function. During training, LOF-VI VI trains the options independently and rewards the agent for reaching the subgoals associated with the options. This is in effect dense reward function. The generic reward function for RM only rewards the agent for reaching the goal state. There are other high-level rewards to guide the agent through the task. This is very sparse reward that results in less efficient training. RM's reward function could easily be made dense by rewarding every transi- tion of the automaton. In this case, RM would probably train as efficiently as LOF-VI. However, imagine an FSA with two paths to the goal state. One path has only I transition but has much lower low-level cost, and one path has 20 transitions and a much higher low-level cost. RM might learn prefer the reward-heavy 20-transition path rather than the reward-light 1-transition path, even if the 1-transition path results
lower low-level cost. In theory it might be possible to design an RM reward function that adjusts the automaton transition reward depending on the length of the path that the state is in, but this would not be trivial task when accounting for branching and merging paths. We therefore decided that it would be fairer comparison to use trivial RM reward function, just as we use a trivial reward function for the LOF baselines. However, we were careful to not list increased efficiency in our list of contributions; although increased efficiency was an observed side effect of LOF, LOF is not inherently more efficient than other algorithms besides the fact that it automatically imposes a dense reward on reaching subgoals.
25


Reviews:
[{"review_id": "daIPJiREk6T", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the work:\nThe authors propose the Logical Options Framework (LOF) --- a framework for reasoning over high-level plans and learning low-level control policies. This framework uses Linear Temporal Logic (LTL) to specify properties (high-level tasks) in terms of propositions. The authors propose a framework in which a separate sub-task policy is learnt to accomplish each such sub-task proposition. These low-level control policies may be reused, without further training, to accomplish new high-level tasks by performing value-iteration in the proposed Hierarchical SMDP. Experimental results demonstrate the method’s effectiveness for several tasks and experimental domains.\n\nQuality and Clarity:\nThe paper does a good job at intuitively describing the value that the proposed “LOF” framework provides (satisfaction, optimality, and composability). In general, the language used in the paper is clear and easy to read. \nHowever, some of the technical aspects in the paper are difficult to follow concretely. There are various vague statements and definitions throughout the paper. Typos, inconsistencies, and missing explanations/discussion of seemingly important notions make some of the presented ideas imprecise. This raised several questions from me on the general applicability of the framework (as it is presented in this paper) beyond the presented experimental tasks, and on some of the specifics of Theorem 3.1. Given that the focus of this paper is on the development a new framework for RL, fixing these issues is crucial. I have included a more detailed list of feedback for the authors at the end of the review. \n\nOriginality and Significance:\nThe proposed method defines “logical options” – sub-task policies whose goal is to trigger propositions that cause transitions in the automata-based description of the high-level task. Temporally extended tasks may then be accomplished by deploying the appropriate sub-task policy at the appropriate FSA state. This idea seems very similar to learning with Reward Machines. This similarity is acknowledged in the paper. The main conceptual difference between LOF and RMs, is that LOF proposes to learn policies that trigger transitions in an automaton, whereas learning with RMs instead learns separate policies for each state of the automaton. This difference means that in the LOF framework, previously learnt sub-task policies can be reused by composing them to complete new high-level tasks. This is not true for RMs. However, the policies learnt by LOF are not guaranteed to be optimal unless certain conditions are met. \n\nThis is a very good general idea, and as far as I am aware other works have not studied how one might compose previously learned sub-task policies to accomplish new tasks described by automata in this way. However, I am concerned that the significance of the work might be limited to the specific examples of the paper.\n\nFor example, by associating a cost with each safety proposition, instead of forming the safety FSA associated with the safety property, it seems that the only safety properties that can be expressed by  LOF are those of the form: “avoid these states”. Because this is a significant limitation in comparison with all possible safety properties, an explicit discussion of the safety properties that can be represented by LOF would help the reader to understand exactly what problems LOF can solve. \n\nFurthermore, it is unclear how the composability results change in the presence of new and/or changed safety properties. I elaborate further on this point at the end of the next section of the review.\n\nQuestions surrounding theorem 3.1\nThe main theoretical result of this paper is that under appropriate conditions, the hierarchical policy learned through the LOF framework will be equivalent to the optimal policy (optimal when planning is allowed with respect to low-level actions in the FSA-MDP product).\n\nThe proof follows the logic that given the appropriate reward functions, the option policies will always reach the states corresponding to their sub-goals, and that the meta-policy will select a sequence of sub-goals that always reaches the FSA goal state.\nThe proposed method assumes that if an option corresponding to a particular sub-goal is selected by the meta-policy, then no other sub-goal proposition will be triggered before that option is complete. My concern with this assumption is as follows: what happens in scenarios in which an option policy passes through a state associated with a different sub-goal before reaching its own sub-goal? Would it then be possible for the meta-policy to select an option corresponding to a particular sub-goal, but for a different sub-goal proposition to be triggered first, causing an unwanted transition in the FSA? \n\nFor example, suppose in the delivery domain we could complete a task by either of the following sequences of sub-goals: “a then b”, or “b then a then c”. If “a then b” is less costly than “b then a then c”, the optimal meta-policy should result in “a then b”. Furthermore, assume that “b” lies directly between “a” and the initial state of the agent. The optimal policy for sub-goal proposition “a” would be to move directly to “a”, which would cause it to first pass through “b”. This would cause the agent to be forced to follow “b then a then c” even if the meta-policy first chose proposition “a”. Meanwhile, the optimal policy allowing low-level planning in the FSA-MDP product space would be to move to “a” while actively avoiding “b”, and then to proceed to “b”.\n\nAlso, it is unclear whether consideration of obstacles and safety propositions are included in the consideration of theorem 3.1. It is unclear what the reward functions corresponding to the “goal-conditioned policy” is. If R_S is included in the reward function used to train sub-task policies, then these policies will learn to avoid obstacles. When we compose these sub-task policies for a new task with potentially different safety properties, the policies we learned previously could be sub-optimal in the new scenario. \n\nExperimental results:\nThe experimental results demonstrate the effectiveness of the framework for the chosen experimental tasks. I like the videos provided in the supplementary materials; they are nice visualizations of how the sub-policies are strung together to complete the overall task.\n\nFrom the paper’s description, it is unclear how LOF-QL is implemented. How does this algorithm make use of the liveness FSA if it does not have access to the FSA’s transition function?\n\nAlso, I am concerned that the comparison against RMs may not be fair. As stated in the paper, the RM-based method is only rewarded when the final RM state has been reached. Conversely, the reward for the LOF method is much denser. I do not see why the RM-based method could not also be rewarded for each “good” transition.\n\nFinally, the experiments include the “can” proposition which represents when one of the sub-goals has been canceled. It is unclear how the labeling function, which is defined to map specific MDP states to individual propositions, could return this proposition. If the proposition is returned randomly, the formalisms of the labeling function need to be altered to include these types of randomly occurring propositions.\n\nPros\n\n> The general idea of the paper is good. I like the idea of pre-learning sub-task policies, and then of using automata-based task descriptions to find meta-policies that accomplish new tasks without additional training. This is the “composability” described in the paper.\n\n>The authors do a good job of intuitively describing the benefits that this type of method could provide over competing algorithms.\n\n>The experimental tasks (particularly the videos of the tasks being completed) provide a nice visualization/demonstration of the ideas of the paper.\n\nCons\n\n>The technical aspects of the paper are hard to follow concretely.\n\n>Some of the theory seems vague and the paper has various typos and inconsistencies. This could lead to reader misinterpretations and/or author mistakes.\n\n>The method’s applicability seems to be somewhat limited to specific types of tasks, without explicit discussion of exactly what types of tasks can be solved.\n\n>The questions raised surrounding theorem 3.1 need to be clarified.\n\nFurther detailed feedback:\n\n>How are the logical options learned? In particular, how are T_{o_p}(s’|s) and R_{o_p}(s) learned. These are the components of the options that are subsequently used to find the metapolicy. Are they estimated by averaging values over rollouts of the learned policy? What if the environment is highly stochastic and their values vary greatly across different rollouts?\n\n>The assignment for T_{o_p}(s’|s) on line 11 of algorithm 1 seems to assume there is a fixed k in which p will be reached. Would this always be the case if the environment is stochastic? This also seems to be a different definition than is given in equation 2.\n\n>In equation 1, R_{o}(s) is defined as the expected cumulative reward of options given that the option is initiated in state s at time t and ends after k time steps; shouldn’t this make R_{o}(s) a function of k as well? \n\n>In the definition of T_{o}(s’|s), what is p(s’,k)? I assume this is the probability, under the option’s policy, of reaching state s’ after k timesteps from state s. If this is the case, p(s’,k) should be defined.\n\n>In line 9 of the Algorithm 1, T_{P}(s,p) = 1 is written. On line 11 of Algorithm 1, T_{P}(s) = p is written instead, but both have the same meaning: proposition p is returned by the labeling function from state s.\n\n>The liveness FSA’s transition function is defined and treated as a probability distribution. However, the automaton’s transitions appear to be deterministic in the presented examples. If there is a particular reason for it to be defined as a transition distribution, some discussion would be helpful for the reader. \n\n>In the definition of a Hierarchical SMDP, the transition function is defined as a cartesian product of the environment transition distribution, the labeling function, and the FSA transition function. The precise meaning of this notation is unclear. A brief description of how a transition proceeds would be very helpful for the reader to understand the order in which arguments are passed to these three functions. Does the environment transition first, and the proposition of the new environment state cause the FSA to transition?\n\n>In section 3.1 and in appendix A.1, the author writes that “if the optimal option policy equals the goal-conditioned policy, the policy will always reach the sub-goal”. This will not be the case if the environment is stochastic and it is possible for the agent, under ANY policy, to slip into a state from which the sub-goal is not reachable.\n\n>Point 2 of the contributions outlined in section 1.1 states that the options can be composed to solve new tasks with only 10-50 retraining steps. This wording is at odds with the abstract, which states that LOF’s learned policies can be composed to satisfy unseen tasks with no additional learning.\n\n>In Section 3 “These may only appear in the liveness property and there may only be one instance of each subgoal.” The second half of this sentence is unclear. Does this mean that the inverse image of each sub-goal proposition through the labeling function is a singleton set containing only one state?\n\n>In section 3 “Safety propositions are propositions such as ‘the agent received a call’ that the agent has no control over or does not seek out.” This sentence is unclear. It would help if you could express what it means for the agent to “have control over” or to “seek out” a proposition in terms of the MDP states, actions, and proposition labeling function.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y7KAItBWlak", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the author proposes logic option framework for learning policies that satisfy the logic  constraints.  Temporal logic rules are converted into finite state machine and each of them is then converted to a learnable option, where the logic proposition is used as the reward function. Given the options, it searches for the optimal meta-policy over all the options. The LOF is tested on a gridworld and an OpenAI Gym benchmark and is compared against baselines that do not use rules.\n\nI find the idea of integrating logics into RL is an exciting direction for improving agent's interpretability and the proposed LOF does have some novelties in applying the FOL rules. However, I'm not familiar with the RL and option literature and it's difficult for me to tell its original work from the existing ones on the RL side.\n\nSome questions for the author:\n\nJudging from Algorithm 1, it seems the rules and predicates are pre-defined with the environment and their conversion into FSA and reward functions are also done with an existing method. Is there anything original in terms of rule/predicate learning or conversion for the proposed LOF?\n\nIn Algorithm 1, each rule is converted to an option and learned independently. What does the LOF do if rules are correlated or have conflicts?\n\n- Say, rule1 is a pre-requisite of rule2: rule1: \"go to dest1\" and rule2:\"if agent is in dest1 then go to dest2, otherwise check rule1\"\n\n- Or rule1: \"go to dest1 asap\" whereas rule2: \"do not violate the traffic rules\"\n\n- Does the LOF provide mechanism to address the above issues?\n\nI'm also concerned about the scalability of this method. It seems to me that the options need to be evaluated at each possible state in the environment. If the goals are fixed, probably one can store the value beforehand, but for a dynamic environment where the goal is changing, how much does it cost to update the reward function and learn the option policies? And how well does it scale with the size of the state/action space?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ViuDsObsPg8", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper proposes a hiearchical RL framework augmented with linear temporal logic. Low-level policies are trained to reach a set of subgoals with penalty on violating safety constraints, allowing the high-level policy to adapt to different task by composing the low-level policies to reach a set of subgoals specified by an Linear Temporal Logic clause.\n\nMy first comment is on technical novelty. Although the paper states that LOF takes a step beyond RM to enable compositionality, there is no empirical comparison or evaluation. The only experiment on evaluating compositionality (c, d in Figure 2) does not compare LOF against RM.\n\nMy second major comment is on technical exposition. The paper's writing needs a lot of work, especially the method section. The method section started off by describing different concepts used by the framework, but it is unclear how these concepts constitute LOF. For example, how exactly is LTL used in LOF? The introduction mentioned that LOF provides \"compositional\" property, but there is not a single hint of how might each piece of LOF lead to this property. It took me a few read to understand how the low-level reward might be agnostic of the high-level task, which in turn enables fast adaptation to new task because only the high-level needs to be trained, but it is better to state that clearly.\n\nI would suggest the authors to write one or two paragraphs at the beginning of the method to provide a high-level overview of (1) What LOF is, (2) what are different components of LOF (3) how these components interact with each other, intuitively (4) what are the technical challenges each component, or all components jointly, are trying to tackle  (e.g., enabling compositionality). \n\nIn addition, there are many mentioning of using reward function in the form of an FSA. I understand that this was already introduced in Icarte et al., but it is worth reviewing it in the main paper.\n\nComments on experiments:\n- For compositionality experiment, why might RM and Flat not be applicable here (related to my first comment)?\n- I do not see RM curve in (e)\n\n\nMinor:\n- \"\\phi_{liveness} is represented as a finite state automaton\". The paper has been using FSA through except first introduced FSA. It's better to be consistent.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0rc_tPBZgo-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is on a new RL framework that leverages logical reasoning to improve the learning performance of RL agents. In particular, the knowledge is encoded using LTL, and includes both safety knowledge (used for reward function definition) and liveness knowledge (used for constructing FSA). THe developed framework has been evaluated using tasks in both discrete and continuous domains, where the RL agent was realized using Q-learning and PPO respectively. The framework was compared with baselines including another LTL-based RL methods (Reward Machines). Results show that LOF performed better than the baseline methods in learning rate and policy quality (in most cases). \n\nThe whole idea of leveraging human knowledge to improve RL agent's learning performance makes senses. The main concern is that the developed framework looks quite incremental in comparison to the methods from the literature. For instance, there are already methods in the literature using LTL to bias the reward function, e.g., the papers that improved the Reward Machines work. As a result, the novelty of the safety knowledge is rather incremental. At the same time, the \"liveness\" part is quite similar to those methods that plan at a symbolic level to guide RL agents, such as the following: \n\nLyu D, Yang F, Liu B, Gustafson S. SDRL: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. 2019\n\nIt's nice to see the discussions on satisfaction, optimality, and composability. The analysis on optimality is the most important, whereas the other two points are relatively trivial due to the LTL-based FSA. But it turned out the developed approach, LOF, does not guarantee any desired properties beyond those from the literature. In particular, the LTL-based FSA cannot guarantee global optimality, where the baseline of Reward Machines does. \n\nThe reviewer is curious about if Reward Machines can be considered an ablation of LOF, where the \"liveness\" component is disabled (and \"safety\" is retained). If not, what are the differences between the two methods? \n\nKnowledge-based RL can go beyond HRL methods. For instance, the following survey paper summarizes a few other ways of leveraging human knowledge in RL. Some discussions can help improve the related work section. \n\nZhang S, Sridharan M. A Survey of Knowledge-based Sequential Decision Making under Uncertainty. 2020\n\nIn general, it's not surprising to see human knowledge is useful in RL. However, human knowledge is not always correct. It will be nice to evaluate the situations where human knowledge in incomplete or inaccurate, or at least some discussions can be helpful. \n\n----------\nThe reviewer appreciates the response in detail. The new figures (Figs 4-7) are helpful for demonstrating the differences between LOF and RM, while also demonstrating that their outputs can be similar or the same in many cases. The reconciliation between optimality and composability is a nice feature. Overall, the reviewer still feels positive on this work. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This was a borderline paper with a split recommendation from the reviewers.  The authors took great care to answer the reviewer questions in detail, and the clarity and precision of the technical exposition was strengthened.  However, substantial technical content was added to the paper during the rebuttal process, which the reviewers were not able to fully and properly assess.

Overall, this is worthwhile research, but the paper is still maturing.  The contribution was perceived as incremental in light of previous work using LTL and FSAs in RL, despite the authors extensively re-explaining the significance of the work in the rebuttal.  A resubmission is more likely to resonate with reviewers and ultimately achieve higher impact.

For completeness, it would help to also briefly acknowledge and compare to hierarchical RL work that also seeks to capture composable subtask structures, such as:

Sohn et al. "Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies", NeurIPS-2018

Sohn et al. "Meta Reinforcement Learning with Autonomous Inference of Subtask Dependencies", ICLR-2020
Decision: Reject