Compositional Reinforcement Learning from Logical Specifications
Authors: Kishor Jothimurugan
Suguman Bansal
Osbert Bastani
Rajeev Alur
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
options
temporal specifications
hierarchical learning

Abstract: We study the problem of learning control policies for complex tasks given by logical specifications. Recent approaches automatically generate a reward function from a given specification and use a suitable reinforcement learning algorithm to learn a policy that maximizes the expected reward. These approaches, however, scale poorly to complex tasks that require high-level planning. In this work, we develop a compositional learning approach, called DIRL, that interleaves high-level planning and reinforcement learning. First, DIRL encodes the specification as an abstract graph; intuitively, vertices and edges of the graph correspond to regions of the state space and simpler sub-tasks, respectively. Our approach then incorporates reinforcement learning to learn neural network policies for each edge (sub-task) within a Dijkstra-style planning algorithm to compute a high-level plan in the graph. An evaluation of the proposed approach on a set of challenging control benchmarks with continuous state and action spaces demonstrates that it outperforms state-of-the-art baselines.

Compositional Reinforcement Learning from Logical Specifications
Kishor Jothimurugan
Suguman Bansal University of Pennsylvania
University of Pennsylvania
Osbert Bastani University of Pennsylvania
Rajeev Alur
University of Pennsylvania
Abstract
We study the problem of learning control policies for complex tasks given by logical specifications. Recent approaches automatically generate reward function from a given specification and use a suitable reinforcement learning algorithm to learn policy that maximizes the expected reward. These approaches, however, scale poorly to complex tasks that require high-level planning. In this work, we develop a compositional learning approach, called DIRL, that interleaves high- level planning and reinforcement learning. First, DIRL encodes the specification an abstract graph; intuitively, vertices and edges of the graph correspond regions of the state space and simpler sub-tasks, respectively. Our approach then incorporates reinforcement learning learn neural network policies for each edge (sub-task) within Dijkstra-style planning algorithm to compute a high-level plan in the graph. An evaluation of the proposed approach on a set of challenging control benchmarks with continuous state and action spaces demonstrates that it outperforms state-of-the-an baselines.
Introduction
Reinforcement learning (RI.) is promising approach to automatically learning control policies for continuous control tasks e.g.. for challenging tasks such walking [11] and grasping [6], control of multi-agent systems [31 22 and control from visual inputs 28 key challenge facing RL is the difficulty in specifying the goal. Typically, RL algorithms require the user to provide reward function that encodes the desired task. However, for complex, long-horizon tasks, providing a suitable reward function can be daunting task, requiring the user manually compose rewards for individual subtasks. Poor reward functions can make it hard for the RL algorithm to achieve the goal; e.g., it can result reward hacking (3), where the agent learns optimize rewards without achieving the goal.
Recent work has proposed number of high-level languages for specifying RL tasks key feature of these approaches is that they enable the user to specify tasks compositionally i.e. the user can independently specify a set of short-term subgoals, and then ask the robot to perform a complex task that involves achieving some of these subgoals. Existing approaches for learning from high-level specifications typically generate a reward function, which is then used by an off-the-shelf RL algorithm learn policy. Recent works based on Reward Machines [19 35 have proposed RL algorithms that exploit the structure of the specification to improve learning. However, these algorithms are based on model-free RL at both the high- and low-levels instead of model-based
24
RL. Model-free RL has been shown to outperform model- based approaches on low-level control tasks [10]: however, the high-level, it unable exploit the large amount of available structure. Thus, these approaches scale poorly to long horizon tasks involving complex decision making.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.2
SHECTR
(achieve (reach (2) or achieve (reach S2):
1.0
Sx
achieve (reach 53)) ensuring avoid
0.6
0.4
0.2
So
0.0
Su
Zz0
S₁
240
-0.2
0.0
0.5
3.0
1.5
2.0
2.5
Figure I: Left: The 9-rooms environment, with initial region So in the bottom-left, obstacle O in the middle-left, and three subgoal regions S1, S2. S3 in the remaining corners. Middle top: A user-provided specification dex. Middle bottom: The abstract graph 9ex DIRL constructs for dex- Right: Learning curves for our approach and some baselines; x-axis is number of steps and y-axis is probability of achieving dex.
We propose DIRL, novel compositional RL algorithm that leverages the structure in the specification to decompose the policy synthesis problem into high-level planning problem and set of low-level control problems. Then, interleaves model-based high-level planning with model-free RI. to compute a policy that tries to maximize the probability of satisfying the specification. In more detail, our algorithm begins by converting the user-provided specification into an abstract graph whose edges encode the subtasks, and whose vertices encode regions of the state space where each subtask considered achieved. Then, uses a Djikstra-style forward graph search algorithm to compute sequence of subtasks for achieving the specification, aiming to maximize the success probability. Rather than compute policy to achieve each subtask beforehand, constructs them on-the-fly for a Djikstra's algorithm requires the cost of that subtask.
subtask
We empirically evaluate our approach on a "rooms environment" (with continuous state and action spaces), where 2D agent must navigate set of rooms to achieve the specification, as well as challenging "fetch environment" where the goal to use robot arm to manipulate block to achieve the specification. We demonstrate that DIRL significantly outperforms -fate-of-the-art deep RL algorithms for learning policies from specifications, such as SPECTRL, TL.TI, QRM and HRM, as well as state-of-the-arr hierarchical RL algorithm, R-AVI, that uses state abstractions, the complexity of the specification increases. In particular, by exploiting the structure the specification to decouple high-level planning and low-level control, the sample complexity of DIRL scales roughly linearly in the size of the specification, whereas the baselines quickly degrade in performance. Our results demonstrate that DIRL is capable of learning to perform complex tasks in challenging continuous control environments. In summary, our contributions are as follows:
A novel compositional algorithm learn policies for continuous domains from complex high-level specifications that interleaves high-level model-based planning with low-level RL.
A theoretical analysis of our algorithm showing that it aims maximize lower bound the satisfaction probability of the specification.
An empirical evaluation demonstrating that our algorithm outperforms several statc-of-the. art algorithms for learning from high-level specifications.
Motivating example. Consider an RL-aggett in the environment of interconnected rooms in Figure The agent initially the blue box, and their goal to navigate to either the top-left room S or the bottom-right room S2, followed by the top-right room S3, all the while avoiding the red block O. This goal is formally captured by the SPECTRL specification dex (middle top). This specification is comprised of four simpler RL subtasks-namely, navigating between the corner rooms while avoiding the obstacle. Our approach. DIRL, leverages this structure improve learning. First, based on the specification alone, it constructs the abstract graph G.x (see middle bottom) whose vertices represent the initial region and the three subgoal regions, and the edges correspond subtasks (labeled with a safety constraint that must be satisfied).
However, Gea by itself is insufficient to determine the optimal path-e-g.. e.g., does not know that there is no path leading directly from S₂ to S3. which is property of the environment. These differences
Our implementation is available https://gittub.oom//yyhhrrii

---

can be represented as (a priori unknown) edge costs in Sxx At high level, DIRL trains policy Te for each edge e in Gex. and sets the cost of to be c(e; mT) - log P(e, where P(e; ne) is the probability that ge succeeds in achieving e. For instance, for the edge So - S1, Ve is trained to reach S₁ from a random state in So while avoiding O. Then, a naive strategy for identifying the optimal path is to (i) train a policy He for each edge e, (ii) use it to estimate the edge cost c(e; ne), and (iii run Djikstra's 's algorithm with these costs.
One challenge is that Te depends on the initial states used in its training-e.g. training Te for e = S + S3 requires a distribution over Sj. Using the wrong distribution can lead to poor performance due to distribution shift; furthermore, training a policy for all edges may unnecessarily waste effort training policies for unimportant edges. To address these challenges. DIRL interweaves training policies with the execution of Djikstra's 's algorithm, only training T. once Djikstra's 's algorithm requires the cost of edge e. This strategy enables DIRI, to scale to complex tasks; in our example, quickly learns policy that satisfies the specification with high probability. These design choices are validated empirically- as shown in |Figure DIRL quickly learns to achieve the specification, whereas it is beyond the reach of existing approaches.
Related Work. There has been recent work on using specifications based on temporal logic for specifying RL tasks [ [2] 18
39 23]. These approaches typically generate a (usually sparse) reward function from given specification which then used by an off-the-shele RL algorithm to learn a policy. In particular, Li et al. [29] propose a variant of Linear Temporal Logic (LTL) called TLTL to specify tasks for robots, and then derive shaped (continuous) rewards from specifications in this language. Jothimurugan et al. [24] propose a specification language called SPECTRL that allows users to encode complex tasks involving sequences, disjunctions, and conjunctions of subtasks, as well as specify safety properties; then, given specification, they construct a finite state machine called a task monitor that is used to obtain shaped (continuous) rewards. Icarte et al. [19 propose automaton based model called reward machines (RM) for high-level task specification and decomposition as well as an RL algorithm (QRM) that exploits this structure. In later paper (35], they propose variants of QRM including an hierarchical RL algorithm (HRM) to learn policies for tasks specified using RMs. Camacho et al. 9 show that one can generate RMs from temporal specifications but RMs generated this way lead to sparse rewards. Kuo et al. (27) and Vaezipoor et al. (36 propose frameworks for multitask learning using LTL specifications but such approaches require lot of samples even for relatively simpler environments and tasks. There has also been recent work on using temporal logic specifications for multi-agent RL. 16 33
30 17
40
[5]
More broadly, there has been work on using policy sketches [5) which are sequences of subtasks designed to achieve the goal. They show that such approaches can speed up learning for long-horizon tasks. Sun et al. (34] show that providing semantics to the subtasks (e.g., encode rewards that describe when the subtask has been achieved) can further speed up learning. There has also been recent interest in combining high-level planning with reinforvement learning [I 25 13). These approaches all target MDPs with reward functions, whereas we target MDPs with logical task sprcifications. Furthermore, in our setting, the high-level structure is derived from the given specification, whereas in existing approaches it is manually provided. Illanes et al. (20 propose an RL algorithm for reachability tasks that uses high-level planning to guide low-level RL; however, unlike our approach, they assume that a high-level model is given and high-level planning is not guided by the learned low-level policies. Finally, there has been recent work on applying formal reasoning for extracting interpretable policies as well as for safe reinforcement learning 4 26
37 38 21
2 Problem Formulation
MDP. We consider a Markov decision process (MDP) M = (S, P,n) with continuous states s R", continuous actions A C RT, transitions P(s, a, = p(s' s, s,a) R>0 (i.e., the probability density of transitioning from state s to state s' upon taking action a), and initial states
n S + R2 (i.c., n(s) is the probability density of the initial state being s). A trajectory ÇE Z
is either an infinite sequence Ç = 80 do, 21
or finite sequence
80 Go
8t
ax-1 8g. We let 2, denote the set of finite trajectories. A (deterministic) policy π : E -> A maps finite trajectory to a fixed action. Given n, we can sample trajectory by sampling an initial state 80 ~ nn()) and then iteratively taking the action a, (Ço:)) and sampling a next state 8141 p(- | st, a.).
where 8; E and a; E A. A subtrajectory of ( is a subsequence Çr. = 88 "f,
3

---

Specification language. We consider the specification language SPECTRL for specifying reinforce- ment learning tasks (24). A specification & in this language logical formula over trajectories that indicates whether given trajectory successfully accomplishes the desired task. As described below, can be interpreted as a function @ -> B. where B (true, false).
where every E Po is associated with a function [p]] : S + B: we say state s satisfies p (denoted 8 - p) if and only [p] true. For example, given state E S, the atomic predicate [reach s|((') 1) indicates whether the system is in a state close
Formally, a specification is defined over a set of atomic predicates Po.
(IIs' s|| <
with respect to the norm || ||. The set of predicates P consists of conjunctions and disjunctions of atomic predicates. The syntax of predicate b E P given by the grammar b ::= p (bj A b2) (b) V b2), where p E Po. Similar to atomic predicates, each predicate b E P corresponds to function [[b] S + defined naturally over
Boolean logic. Finally, the syntax of SPECTRL specifications is given by
= achieve b Φ1 ensuring b Φ1 02 Φ1 or 22
where b E P.. In this case, each specification ø corresponds to a function [Ø] 2 - IB, and we say E satisfies & (denoted + Φ) if and only if [[] = true. Letting & be a finite trajectory of length f. this function is defined by
< = achieve b
3 B t, st | b if = Φ and 4 S t, s b
< é ensuring b
< = Φ1; 02
if < t, Cu.s -= Φ1 and Gi+1:e F= 62
< = Φ1 d2
if - Φ1 or + d2
Intuitively, the first clause means that the trajectory should eventually reach state that satisfies the predicate The second clause says that the trajectory should satisfy specification while always staying in states that satisfy b. The third clause says that the trajectory should sequentially satisfy 6i followed by Φ2. The fourth clause means that the trajectory should satisfy either Φ1 or d2. An infinite trajectory Ç satisfies Φ if there is such that the prefix Ça+t satisfies é
We assume that are able evaluate [p](() for any atomic predicate p and any state s. This is common assumption in the literature on learning from specifications, and is necessary to interpret a given specification Φ.
Learning from Specifications. Given an MDP M with unknown transitions and a specification d, goal is to compute a policy x² 2 + A such that x¹ E arg max, Prç-D,IS F Φ), where D is the distribution over infinite trajectories generated by π. In other words, we want to learn a policy T² that maximizes the probability that a generated trajectory Ç satisfies the specification ø.
We consider the reinforcement learning setting in which we do not know the probabilities P but instead only have access to simulator of M. Typically, we can only sample trajectories of M starting at an initial state 80 ~ 1). Some parts of our algorithm are based on an assumption that we can sample trajectories starting at any state that has been observed before. For example, if taking action dg in 8o leads to a state 81, we can store 81 and obtain future samples starting at 81.
Assumption 2.1. We can sample p(- s, a) for any previously observed state and any action a.
3 Abstract Reachability
In this section, we describe how to reduce the RL problem for given MDP M and specification á to a reachability problem on a directed acyelic graph (DAG) G5. augmented with information connecting its edges to subtrajectories in M. In Section 4 we describe how to exploit the compositional structure of G to learn efficiently.
3.1 Abstract Reachability
We begin by defining the abstract reachability problem, and describe how to reduce the problem of learning from SPECTRL specification to abstract reachability. At a high level, abstract reachability is defined as a graph reachability problem over a directed acyelic graph (DAG) whose vertices
e Here, achi eve and ensuring correspond to the "eventually" and "always" operators in temporal logic.

---

s
Sb
Figure 2: Abstract graph for achieve b.
correspond to subgoal regions-a subgoal region X S is a subset of the state space S. As discussed below, in our reduction, these subgoal regions are derived from the given specification Φ. The constructed graph structure also encodes the relationships between subgoal regions.
Definition 3.1. An abstract graph g = (U, E. No. F, sate) is directed acyelic graph (DAG)
with vertices U, (directed) edges E _ U x U, initial vertex uo E U, final vertices F C U, subgoal region map / U + 2 such that for each E U, B(u) is a subgoal region and safe trajectories 2ufe UCER sate. where Safe C 2 denotes the safe trajectories for edge E E.
Intuitively, (U, F) is a standard DAG, and uo and F define a graph reachability problem for (U, E). Furthermore, 8 and Zaae connect (U, E) back the original MDP M; in particular, for an edge e + u', - is the set of trajectories in M that can be used to transition from B(u) to B(u').
Definition 3.2. An infinite trajectory (= 80 oo 81 _i ... in M satisfies abstract reachability in and a path
for (denoted Ç += 9) if there is sequence of indices to S i1 uo + U1
ux in G such that
Uk F.
. for all j E {0, ko, we have 81, B(u,), and
k).
for all j < k; letting ej = Mj + Ui+t we have Seydiys E 2
The first two conditions state that the trajectory should visit a sequence of subgoal regions corre- sponding path from the initial vertex to some final vertex, and the last condition states that the trajectory should be composed of subtrajectories that are safe according to Z
Definition 3.3. Given MDP M with unknown transitions and abstract graph G, the abstract reacha- bility problem is compute a policy मं 2 + A such that arg max Prę-D, - g).
In other words, the goal is to find policy for which the probability that generated trajectory satisfies abstract reachability is maximized.
3.2 Reduction to Abstract Reachability
Next, describe how to reduce the RL problem for given MDP M and specification & to an abstract reachability problem for M by constructing an abstract graph Go inductively from o. We give high-level description here, and provide details in Appendix A in the supplement.
First, for each predicate we define the corresponding subgoal region S, = {s E S
denoting the set of states at which b holds. Next, the abstract graph Gş for & = achieve b shown in Figure 2 All trajectories in 3 are considered safe for the edge e = ll -> मn and the only final vertex is i with (u,) Sg. The abstract graph for a specification of the form ó Φ1 ensuring b is obtained by taking the graph Go, and replacing the set of safe trajectories Z for each e E E, with the set E n Z, where Zn {c 2, Vi s; b) is the set of trajectories in which all states satisfy b. For the sequential specification & = d1: d2. we construct Go by adding edges from every final vertex of Gb, to every vertex of Go, that is neighbor of its initial vertex. Finally, choice = Φ1 or Φ2 is handled by merging the initial vertices of the graphs corresponding to the two sub nub-specification.. Figure shows an example abstract graph. The labels the vertices are regions in the environment. All trajectories that avoid hitting the obstacle O are safe for all edges. We have the following key guarantee:
Theorem 3.4. Given SPECTRL specification o, we can construct an abstract graph Go such that, for every infinite trajectory Ç E Z, we have Ç c & if and only if - Go. Furthermore, the number of vertices in Gø O(Ø)) where |ø] is the size of the specification d.
We do not require that the subgoal regions partition the state space that they be non-overlapping.
5

---

Algorithm 1 Compositional reinforcement learning algorithm for solving abstract reachability.
function DIRL(M, 9)
Initialize processed vertices U, Initialize Fw. + } and Iu f- Ø for u uo
Initialize edge policies II
while true do
u NEARESTVERTEX(U \ Up. r, II)
Pa < SHORTESTPATH(T.)
JJ f REACHDISTRIBUTION(e!! II)
if u E F then return PATIPOLICYYPP II)
for & = u + v' E Outgoing do
Te < LEARNPOLICY((S Tu Add Pa o Tw and Te to IT
Add to Up
We give a proof Appendix A As a consequence, we can solve the reinforcement learning problem for & by solving the abstract reachability problem for Ga- As described below, we leverage the structure of G6 conjunction with reinforcement learning to do so.
4 Compositional Reinforcement Learning
In this section, propose compositional approach for learning policy to solve the abstract reachability problem for MDP M (with unknown transition probabilities) and abstract graph G.
4.1 Overview
At a high level, our algorithm proceeds in three steps:
For each edge e = u + w' in G, use RL to learn a neural network (NN) policy Te to try and transition the system from any state (u) to some state s' E (uu") in safe way according to Z Importantly, this step requires a distribution 7u over initial states B(u).
Use sampling to estimate the probability P(e; Te; nu) that m. safely transitions from (()) to ((u').
Use Djikstra's algorithm in conjunction with the edge costs c(e) log(P(e; ne, mn)) to compute a path p² = ug - 21 + + us in G that minimizes c(p)
= log(P(eg; TT. m3)), where e uj uj+1, Ty Te, and 77j Taa
k-
Then, we could choose be the sequence of policies Ti... Th m-- execute each policy n. until it reaches 3( and then switch to πÿ
There two challenges that need be addressed in realizing this approach effectively. First, it is unclear what distribution to use as the initial state distribution Tu to train Te- Second, it might be unnecessary to learn all the policies since subset of the edges might be sufficient for the reachability task. Our algorithm (Algorithm IT addresses these issues by lazily training n. T.-ie,, only training me when the edge cost c(e) is needed by Djikstra's algorithm.
In more detail, DIRL iteratively processes vertices in starting from the initial vertex up, continuing until it processes a final vertex E F. It maintains the property that for every u it processes, it has already trained policies for all edges along some path Pv. from ug to u. This property is satisfied by ue since there is path of length zero from to to itself. In Algorithm I r, is the set of all paths from 2Ap to u discovered so far, r = U,, Tu. and II = (Te c = > w E E, u E Up} is the set of all edge policies trained so far. In each iteration, DIRL processes unprocessed vertex u nearest to uo. which it discovers using NEAREST VERTEX, and performs the following steps:
SHORTESTPATH selects the shortest path from uy u T denoted Pa = Ug -
Uk

---

v'. DIRL chooses the 2. REACHDISTRIBUTION computes the distribution yu over states in (u) induced by using the sequence of policies Teo Te. E II, where e, = u + Uj+1 are the edges in Pu- + u', LEARNPOLICY learns policy Te for using 7/u as the initial
3. For every edge state distribution, and adds मe to II and Pu' to Tw, where Pu' = Uo 7 ... - u + u'; Te is trained to ensure that the resulting trajectories from ((u) to B(u") are in sate with high probability.
4.2 Definitions and Notation
Edge costs. We begin by defining the edge costs used in Djikstra's 's algorithm. Given policy ne for edge e e u- w', and an initial state distribution T/u over the subgoal region 3(u), the cost c(e) of is the negative log probability that n. safely transitions the system from 80 1/u to B(u'). First, we say a trajectory ( starting at 50 achieves an e if it safely reaches f(u')=formally:
Definition 4.1. An infinite trajectory { < so 81 ... achieves edge
+ u' in G (denoted
< - é) if (i) So E B(u), and (ii) there exists (constrained to be positive if u * uo) such that 8, E B(u') and Co:s E 2 satss we denote the smallest such i by e)..
Then, the probability that π achieves e from an initial state 80 ~ 1/u is
P(e; Tes Th) 50 To
Pr
K [[=e]
where D=..so is the distribution Finally, the cost of edge e is c(e) = - -log P(e; Te, Note that c(e) is nonnegative for any edge e.
infinite trajectories induced by using Te from initial state so-
Path policies. Given edge policies II along with path p = Mg - 01 + + us in G. we define a path policy xp to navigate from 3(uo) to (u). In particular, TTp executes -uy- 11 (starting from j = until reaching (( after which increments j + j + 1 (unless j= kt). That is, xp is designed to achieve the sequence of edges in p. Note that Tp is stateful since it internally keeps track of the index of the current policy.
Induced distribution. Let path for all edges along the path have been trained. The induced distribution T) is defined inductively on the length of p. Formally, for the zero length path uo (so u un), we define 1)p to be the initial state distribution of the MDP M. Otherwise, we have p we define Tp to be the state distribution over 3(u) induced by using Te from 80 Tp conditioned on kF e. Formally, 7p is the probability distribution over B(u) such that for a set of states S' C B(u). the probability of S" according to up is
44p + - u = u from ue to u be such that edge policies
=u' - u. Then, e, where
Pr [s E S*1 = spopp
Pr 50 D. Dr
[St(c,e) S [
Tey Mpon)) where = Uj + uj+1 is the j-th edge in and po.j = uo - .... - Uj is the j-th prefix of p.
Path costs. The cost of path = up + ... + us = = is c(p) = - log PlyyiTey,
k-1
4.3 Algorithm Details
DIRL interleaves Djikstra's algorithm with using RL to train policies ne. Note that the edge weights to run Dijkstra's are not given a priori since the edge policies and initial state/induced distributions are unknown. Instead, they are computed on-the-fly beginning from the subgoal region uo using Algorithm [ We describe each subprocedure below.
Processing order (NEARESTVERTEN)
On each iteration, DIRL chooses the vertex u to process next to be an unprocessed vertex that has the shortest path from ug-ic.. e arg weur,, minper,, <(p). This choice is an important part of Djikstra's algorithm. For graph with fixed costs, it ensures that the computed path Pu to each vertex u is minimized. While the costs in our setting are not fixed since they depend on Thas this strategy remains an effective heuristic.
Shortest path computation (SHORTESTPATH), This subroutine returns a path of minimum cost, Pr. arg min, c(p). These costs can be estimated using Monte Carlo sampling.
Initial state distribution (REACHDISTRRBUTTON)) distribution 7a to choose to train policies π. for outgoing edges
key choice DIRL makes what initial state
7

---

initial state distribution 7/ = Mp. to be the distribution of states reached by the path policy xp.. from a random initial state so
Learning edge policy (LEARNPOLICY), Now that the initial state distribution Tu is known, we describe how DIRL learns a policy Te for a single edge e = u + v'. At a high level, trains Te using standard RL algorithm, where the rewards 1 = e) are designed to encourage Te to safely transition the system to a state in ((u'). To be precise, DIRL uses RL to compute Te E arg max, P(e; nT, mn)) Shaped rewards can be used improve learning; see see Appendixx B
Constructing a path policy (PATHPOLICY)). Given edge policies IT along with a path p p= uo +
+ where E F is final vertex, DIRL returns the path policy TTp-
Theoretical Guarantee. We have the following guarantee (we give a proof Appendix C Theorem 4.2. Given path policy xp corresponding to path p uo + uk u, where U E F. we have PIç-D=, Is = 9] exp(-c(p))
In other words, we guarantee that minimizing the path cost c(p) corresponds to maximizing a lower bound on the objective of the abstract reachability problem.
5
Experiments
We empirically evaluate our approach on several continuous control environments; details are in Appendix D
and F
Rooms environment. We consider the 9-Rooms environment shown in Figure and a similar 16-Rooms environment. They have states (x, E R encoding 2D position, actions (v. 0) R For 9-Rooms, we
encoding speed and direction, and transitions s = 8 + (c cos( u siin
consider specifications similar to dex in Figure T For 16-Rooms, challenging specifications $1.-.., Øs; each di encodes a sequence of i sub-specifications, each of which has the same form as Φex (see (ecenddpedi E). We learn policies using ARS [32] with shaped rewards (see Appendix B); each one is fully connected NN with 2 hidden layers of 30 neurons each.
consider series of increasingly
Fetch environment. We consider the Fetch-Pick-And-PPin consisting of robotic arm that can grasp objects and a block to manipulate. The state space is R which includes components encoding the gripper position, the (relative) position of the object, and the distance between the gripper fingers. The action space is IR where the first 3 components encode the target gripper position and the last encodes the target gripper width. The block's initial position is a random location on a table. We consider predicates NearObj (indicates if the gripper of the arm is close to the block), HoldingObj (indicates if the gripper is holding the block), LiftedObi (indicates if the block is above the table), and ObjAt[g] (indicates if the block is close to a goal E IR²).
environment in OpenAI Gym (8],
We consider three specifications. First, PickAndPlace is
Φ = NearObj; HoldingObj; LiftedObi; ObjAtíg).
where g is a random goal location. Second, PickAndPlaceStatic is similar to the previous one, except the goal location is fixed. Third, PickAndPlace Choice involves choosing between two tasks, each of Pltaceetttt..................... We learn policies using TD3 [14]
which is sequence of two subtasks similar with shaped rewards; each one is a fully connected NN with 2 hidden layers of 256 neurons each.
Baselines. We compare our approach to four state-of-the-arr algorithms for learning from spec- ifications, SPECTRL (24), QRM [19], HRM (35), and a TLTL (29] based approach, as well as a ofate-of-the--at hierarchical RL algorithm, R-AVI (25), that leverages state abstractions. We used publicly available implementations of SPECTRL, QRM, HRM and R-AVI. For QRM and HRM, we manually encoded the tasks as reward machines with continuous rewards. The variants QRM+CR and HRM+CR use counterfactual reasoning to reuse samples during training. Our implementation of TLTL uses the quantitative semantics defined in Li et al. 229 with ARS learn single policy for each task. We used the subgoal regions and the abstract graph generated by our algorithm as inputs to R-AVI. Since R-AVI only supports disjoint subgoal regions and furthermore assumes the ability to sample from any subgoal region, we only ran R-AVI on supported benchmarks. The learning curves
'This choice is the distribution of states reaching by the path policy n eventually returned by DIRL. Thus. it ensures that the training and test distributions for edge policies in no equal.
8

---

122
1.2
SECTL
1.2
SPECIAA
1.0
1.0
DAM
0.8
0.6
HTM
0.4
0.2
gedeeaa
0.0
0.0
0.0
-0.2
DOL 10UM
-0.2
-0.2
0.0
0.5
1.0
15
2.0
25
3.0
2
X10*
x10
(a) Half sub-specification
Φ1
(b)
sub-specificatiio
d2.
(c)
sub-specifications D3.
Go. = 2.
G0g
4.
8.
1.0
1.0
SPECTTL
campless
0.8
TUTL
HCM
0.6
0.6
HoMt-Ck
2.0
0.4
1.5
1.0
0.0
1.0
12
x10?
x10
ab
(d) 3 sub-specifiicttons
44.
(e) 4 sub sub-specifications
ds.
(f) Sample complexity curves.
|9a1 = 12.
Gesl
16.
Figure 3: (a)-(e) Learning curves for 16-Rooms environment with different specifications increasing in complexity from from (a) to (e). r-axis denotes the number of samples (steps) and y-axis denotes the estimated probability of success. Results are averaged over 10 runs with error bars indicating + standard deviation. (f) shows the average number of samples (steps) needed to achieve a success probability (y-axis) function of the size of the abstract graph Gol.
for R-AVI denote the probability of reaching the final goal region in the y-axis which is upper bound on the probability of satisfying the specification. Note that DIRL returns policy only after the search finishes. Thus, to plot learning curves, we ran our algorithm multiple times with different number of episodes used for learning edge policies.
Results. Figure shows learning curves on the specifications for 16-Rooms environment with all doors open. None of the baselines scale beyond 22 (one segment), while DIRL quickly converges to high-quality policies for all specifications. The TLTI. baseline performs poorly since most of these tasks require stateful policies, which it does not support. Though SPECTRL can learn stateful policies, it scales poorly since it does not decompose the learning problem into simpler ones, and (ii) does not integrate model-based planning at the high-level. Reward Machine based approaches (QRM and HRM) are also unable handle complex specifications, likely because they are completely based on model-free RI., and do not employ model-based planning at the high-level. Although R-AVI uses model-basee planning at the high-level conjunction with low-level RL. does not scale to complex specifications since it trains all edge policies multiple times (across multiple iterations) with different initial state distributions; in contrast, our approach trains any edge policy at most once.
We summarize the scalability of DIRL in Figure 3f where we show the average number of steps needed achieve given success probability as a function of the number of edges in G (denoted by (G&)). As can be seen, the sample complexity of DIRL scales roughly linearly in the graph size. Intuitively, each subtask takes constant number of steps to learn, the total number of steps required is proportional to |G In the supplement, we show learning curves for 9-Rooms Figure 6) for a variety of specifications, and learning curves for variant of 16-Rooms with many blocked doors with the same specifications described above (Figure 7). These experiments demonstrate the robustness of our tool on different specifications and environments. For instance, in the 16-Rooms environment with blocked doors, fewer policies satisfy the specification, which makes learning more challenging but DIRL is still able to learn high-quality policies for all the specifications.
Next, we show results for the Fetch environment in Figure 4] DIRL leverages compositionality to quickly learn effective policies, whereas the baselines are ineffective. The last task is especially challenging, taking DIRL somewhat longer to solve, but it ultimately achieves similar effectiveness. These results demonstrate that DIRL can scale complex specifications even in challenging environments with high-dimensional state spaces.
The trends are similar to before-

---

1.0
1.0
SECTLL
SPECTAA
0.8
getteca
6.8
HAM
0.5
0.6
0.4
6.4
0.4
0.2
6.2
0.0
0.0
0.0
0.0
02
04
0.6
6.8
1.0
32
14
0.00
0.25 0.50 0.75
1.00 125 1.50 1.5
0.5
6.5
1.0
1.5
2.0
25
3.0
85
(a) PickAndPlace
(b) PickAndPlaceStatic
(c) PickAndPlaceChoice
Figure 4: Learning curves for Fetch environment; r-axis denotes the total number of samples (steps) and g-axis denotes the estimated probability of success. Results are averaged over 5 runs with error bars indicating standard deviation.
Conclusions
We have proposed DIRL, reinforcement learning approach for logical specifications that leverages the compositional structure of the specification to decouple high-level planning and low-level control. Our experiments demonstrate that DIRL can effectively solve complex continuous control tasks, significantly improving over existing approaches. Logical specifications are promising approach to enable users to more effectively specify robotics tasks; by enabling more scalable learning of these specifications, underlying specification language. While we have focused on SPECTRL specifications, we believe approach can also enable the incorporation of more sophisticated features into the underlying language, such as conditionals (i.e., only perform a subtask upon observing some property of the environment) and iterations (i.e., repeat subtask until some objective met).
directly enabling users to specify more complex objectives through the
Limitations
DIRL assumes the ability to sample trajectories starting at any state E S thatt has been observed before, whereas in some cases it might only be possible to obtain trajectories starting at some initial state. One way to overcome this limitation is to use the learnt path policies for sampling-i.e in a vertex in the abstract graph, we could sample an initial state 8o ~ 17 from B(ug) and execute the path policy TT, corresponding to the shortest path Pu. from un to u starting at 8p- Upon successfully reaching 3(u) (we can restart the sampling procedure if (u) is not reached), the system will be in a state the in B(u) from which we can simulate the system further.
order to sample a state from a subgoal region (u) corresponding
Another limitation of our approach is that we only consider path policies. It is possible that optimal policy must follow different high-level plans from different states within the same subgoal region. We believe this limitation can be addressed in future work by modifying our algorithm appropriately.
Societal impacts
Our work seeks to improve reinforcement learning for complex long-horizon tasks. Any progress in this direction would enable roboties applications both with positive impact- e.g., flexible and general-purpose manufacturing robotics, robots for achieving agricultural tasks, and robots that can be used to perform household chores-and with negative controversial impact-e.gh e.g.. military applications. These issues are inherent in all work seeking to improve the abilities of robots.
Acknowledgements and Funding
We thank the anonymous reviewers for their helpful comments. Funding direct support this work: CRA/NSF Computing Innovations Fellow Award, DARPA Assured Autonomy project under Contract No. ARO grant W INF-20-1-0082
ONR award -00014-20-1-21 15, NSF grant CCF-1910769, and
10

---

References
[1] David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In International Conference Artificial Intelligence and Statistics, pages 1639-1650. PMLR, 2020.
[2] Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta. Q-learning for robust satisfaction of signal temporal logic specifications. In Conference on Decision and Control (CDC), pages
IEEE, 2016.
[3] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv: 16X6::660000655633 2016.
[4] Greg Anderson, Abhinav Verma, Isil Dillig, and Swarat Chaudhuri. Neurosymbolic reinforce- ment learning with formally verified exploration. In Advances Neural Information Processing Systems, 2020.
[5] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. International Conference on Machine Learning, pages 166-175, 2017.
[6] OpenAl: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob Mc- Grew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1)3--20, 2020.
[7] Ronen Brafman, Giuseppe De Giacomo, and Fabio Patrizi. Ltf//lIf non-markovian rewards. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[8] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
[9] Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In International Joint Conference on Artificial Intelligence, pages 6065-6073, 7 2019.
[10] Yevgen Chebotar, Karol Hausman, Marvin Zhang, Gaurav Sukhatme, Stefan Schaal, and Sergey Levine. Combining model-based and model-free updates for trajectory-centric reinforcement learning. In International conference on machine learning, pages 703-711. PMLR, 2017.
[11] Steve Collins, Andy Ruina, Russ Tedrake, and Martijn Wisse. Efficient bipedal robots based on passive-dynamic walkers. Science, 307 100110088288,,-,,-- 2005.
[12] Giuseppe De Giacomo, Luca locchi, Marco Favorito, and Fabio Patrizi. Foundations for restraining bolts: Reinforcement learning with Itif/ldIf restraining specifications. In Proceedings of the International Conference Automated Planning and Scheduling, volume 29, pages
128 136, 2019.
[13] Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In NeurlPS, 2019.
[14] Scott Fujimoto. Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, pages 1587-1596, 2018.
[15] Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak. Omega-regular objectives model-free reinforcement learning. Tools and Algorithms for the Construction and Analysis of Systems, pages 395-412, 2019.
[16) Lewis Hammond, Alessandro Abate, Julian Gutierrez, and Michael Wooldridge. Multi-agent reinforcement learning with temporal logic specifications. In International Conference on Autonomous Agents and MultiAgent Systems, page 583-592, 2021.
[17] M. Hasanbeig, Y. Kantaros, A. Abate, D. Kroening, G. J. Pappas, and I. Lee. Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In Conference Decision and Control (CDC), pages 5338-5343, 2019.

---

[18] Mohammadhosein Hasanbeig. Alessandro Abate, and Daniel Kroening. reinforcement learning. arXiv preprint arXiv:1801.08099, 2018.
[19] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning. pages 2107-2116. PMLR, 2018.
[20] León Illanes, Xi Yan, Rodrigo Toro Icarte, and Sheila A. Mcllraith. Symbolic plans as high- level instructions for reinforcement learning. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1):540-550, Jun. 2020.
[21] Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In Internation Conference on Learning Representations, 2020.
[22] Jeevana Priya Inala, Yichen Yang, James Paulos, Yewen Pu, Osbert Bastani, Vijay Kumar, Martin Rinard, and Armando Solar-Lezama. Neurosymbolic transformers for multi-agent communication. arXiv preprint arXiv:2101.03258. 2021.
[23] Yuqian Jiang, Sudarshanan Bharadwaj. Bo Wu, Rishi Shah, Ufuk Topcu, and Peter Stone. Temporal-logic--asee reward shaping for continuing learning tasks, 2020.
[24] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. In Advances in Neural Information Processing Systems, volume 32. pages 13041-13051, 2019.
[25] Kishor Jothimurugan, Osbert Bastani, and Rajeev Alur. Abstract value iteration for hierarchical reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1162-1170. PMLR, 2021.
[26] Sebastian Junges, Nils Jansen, Christian Dehnert, Ufuk Topcu, and Joost-Pieter Katoen. Safety- constrained reinforcement learning for mdps. In International Conference on Tools and Algo- rithms for the Construction and Analysis of Systems, pages 130-146. Springer, 2016.
[27] Yen-Ling Kuo, B. Katz, and Barbu. Encoding formulas as deep networks: Reinforce- ment learning for zero-shot execution of Itl formulas. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5604-5610, 2020.
[28] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research,
2016.
[29] Xiao Li, Cristian-loan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1834-3839, IEEE, 2017.
[30] Michael L. Littman, Ufuk Topcu, Jie Fu, Charles Isbell, Min Wen, and James MacGlashan. Enviroomennt-nndeeendedn task specifications via gltl, 2017.
[31] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettiie environments. arXiv preprint (:X6::1706.0277 2017.
[32] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In Advances in Neural Information Processing Systems, pages 1805-1814, 2018.
[33] Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topeu. Reward machines for cooperative multi-agent reinforcement learning, 2021.
[34] Shao-Hua Sun, Te-Lin Wu, and Joseph J. Lim, Program guided agent. In International Conference Learning Representations, 2020.
[35] Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward machines: Exploiting reward function structure reinforcement learning. arXiv preprint arXiv:2010.03950, 2020.
12

---

[36] Pashootan Vaezipoor, Andrew Li, Rodrigo Toro Icarte, and Sheila Mcllraith. Lt12action: Generalizing Itl instructions for multi-task rl. arXiv preprint 2tt1:22022008888, 2021.
[37] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, pages 5045 5054, 2018.
[38] Abhinav Verma, Hoang M Le. Yisong Yue, and Swarat Chaudhuri. Imitation-projecte pro- grammatic reinforcement learning. In Advances in Neural Information Processing Systems, 2019.
[39] Zhe Xu and Ufuk Topcu. Transfer of temporal logic formulas in reinforcement learning. In International Joint Conference on Artificial Intelligence, pages 4010-4018, 7 2019.
[40] Lim Zun Yuan, Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Modular deep reinforcement learning with temporal logic specifications. arXiv preprint arXiv:1909.11591, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the supplement.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the supplement.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] We compare sample-efficiency which is independent of the platform on which the algorithms are run.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] All assets open source and available under the MIT licence.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] URL to repository is provided.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
13

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wVdZjhZBMEa", "reviewer": "Reviewer_4uY8", "summary": "This paper addresses problems where the task to be accomplished is given by a specification language (Spectrl). Tasks given in this specification language can be represented as reachability problems on an abstracted graph, where nodes in the abstracted graph represent regions of the underlying state space of the original problem. To find a high-level plan to satisfy the task specification, Dijkstra's algorithm is used. To learn low-level controllers to complete each of the subtasks, reinforcement learning is used. The probability of a subtask being completed by a low-level controller is evaluated empirically, and used to update costs in the high level graph so that the lowest cost path in the high-level graph corresponds to the path maximising the probability of completing the task.\n \nI think the paper is well written, and addresses an interesting problem. To my understanding, the general idea of combining high-level model-based planning with RL for low-level control has been addressed in existing works. However, this is the first work to do so for more complex task specifications.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the authors need to be clearer about the contributions made by this paper (I would suggest that the authors explicitly enumerate their contributions in the introduction). In the introduction, the authors seem to indicate that a novelty of their work is integrating high-level model-based planning with learning of low-level control. However, this general idea has been presented in other papers such as Illanes (2020), where the high-level specification is given in PDDL (and also considers MaxProb formulations), or arguably even Eysenback (2019).\n \nTherefore, my understanding is that while other works have considered the idea of high-level planning over subtasks + low-level controllers via reinforcement learning, this is the first work consider more powerful task specifications in the form of tasks specified by Spectrl.\n \nQuestion 1).\nCan the authors please compare their work with Illanes (2020). Is the main difference that Illanes (2020) considers high-level goals specified in PDDL, whereas here goals may be specified using Spectrl, or are there other significant advances made by this work?\n \nThe high-level planner operates on a deterministic graph, and outputs the maximum probability path (rather than a policy for all high-level states). Therefore, if the low-level controller fails to reach the desired sub-goal, and accidentally reaches a different sub-goal, the algorithm will not switch appropriately to a different sub-policy. Given that the empirical transition probabilities between high-level abstract states are computed empirically anyway (to compute the edge costs in the graph), I wonder why we wouldn't just treat the high-level abstract graph as an MDP, and compute a high-level policy for that MDP rather than a path? I understand that this would increase the computational burden as we have to learn sub-policies for more states, but this seems like a more natural formulation for stochastic environments, especially considering that the transition probabilities need to be empirically estimated anyway.\n \nQuestion 2).\nCan the authors comment on the advantages of treating the high-level planning problem as deterministic, rather than an MDP? It seems that an MDP would more naturally handle cases where the sub-policy fails to reach the desired sub-goal, and transition probabilities between sub-goals are already being computed empirically anyway.\n \nMinor comment: It might aid in the writing of the paper by referring to the sub-policies as \"options\" as is often done within RL literature.\n\nReferences: \n \nIllanes, León, et al. \"Symbolic plans as high-level instructions for reinforcement learning.\" Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 30. 2020.\n \nEysenbach, Benjamin, Ruslan Salakhutdinov, and Sergey Levine. \"Search on the replay buffer: Bridging planning and reinforcement learning.\" NeurIPS 2019\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some technical contribution limitations identified.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "pT0lB2pebKp", "reviewer": "Reviewer_yVhC", "summary": "The paper proposes a framework for combining RL with logical specifications. In particular, the task is specified using local statements, which are then converted into a graph and high-level planning (using Dijkstra's algorithm) is used to attain the goal while adhering to any safety constraints. Within this graph, nodes are sets of low-level states, while edges represent the probability of a policy (learned using model-free RL) transitioning between nodes. While there exist other approaches that combine logical (e.g. LTL) specifications with RL, experiments in two continuous control domains demonstrate that the method outperforms these existing approaches, and scales only linearly with the complexity of the specification. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles the problem of solving tasks whose goals and constraints are specified using logical predicates, instead of reward functions. I feel this is an important direction (since the ability to encode goals and safety constraints in a human-understandable form will be critical to real-world applications) and, to the best of my knowledge, the paper makes a novel and interesting contribution towards this. Although the paper was generally well written, I found that certain parts were very hard to follow due to space constraints (reading the supplementary material helped, but it would be better if the main text were more self-contained). I have a few questions to help with clarification, and also one concern about how the graph is constructed in the first place, which I'll outline below. \n\nMain comments\n\n1. One aspect I'm not clear on is the grounding of predicates to MDP states. How exactly is the link between predicates and low-level states established?. Line 177 implies that this mapping needs to be done manually. If so, is this then akin to a human designer manually specifying a symbolic representation (which could be hard for very complex domains) and then learning how the symbolic states are connected? If so, this seems like a fair amount of information that must be encoded manually (other approaches like [1] can autonomously construct them). Are the other baselines provided with similar information? \n2. A follow-up question is the following: since the subgoal regions can contain overlapping states, we could have a low-level state s be in both nodes A and B. If we are learning a low-level policy to reach A, but the agent observes state s, how could it be certain that it has not reached B instead?\n3. I found that I couldn't follow Section 5 without the supplementary material at all. Terms like \"sub-specification\" and \"half sub-specification\" were completely opaque to me, but the longer explanation in the appendix made sense. If possible, more detail could be incorporated into the main text (I feel like a few of the definitions in Section 4.2 could be removed to make room).   \n4. I don't quite follow why on Line 114 the policy is not the regular Markov policy, but rather a function of the history. My understanding is that each edge policy is Markov and acts according to the MDP state, while the path policy could act based on the current node only. Any clarification would be appreciated.\n\nMinor comments\n\n1. In the absence of rewards, it makes sense that the agent should seek a maximally likely policy that reaches the goal. However, are there use cases where this wouldn't work? For example, in a tabular deterministic shortest path setting, all policies are equally capable of reaching the goal with probability 1 (but may take varying amounts of time). Is there any way this can be overcome? \n2. The blue/grey colours in Figure 1 (left) are a bit faint and hard to pick up on, especially when printed. \n3. Line 153 cyclic -> acyclic\n4. Line 164: What is s_{i_j}?\n\n[1] Pacheck, Adam, George Konidaris, and Hadas Kress-Gazit. \"Automatic Encoding and Repair of Reactive High-Level Tasks with Learned Abstract Representations.\" Robotics Research: the 18th Annual Symposium. 2019.\n\n\n****** POST REBUTTAL ******\n\nThank you for the response, which has helped clear up the questions and misconceptions that I had. As one of the other reviewers recommended, emphasising the exact novel contributions of the work in the introduction would be extremely helpful for an updated version. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the paper discusses a few of its limitations, if I'm understanding correctly, then one additional limitation is that a mapping from states to predicates be given upfront, and all predicates (nodes) be known before learning begins. This requires human expertise, and may be very hard for complex tasks. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "nxf61SwWXy9", "reviewer": "Reviewer_YbXN", "summary": "This paper studies the problem of using logical specifications of a task to derive an abstract graph, come up with a plan, and train low-level policies more effectively. Given a logical specification written in SPECTRL syntax, it is first converted into an abstract MDP. Dijkstra's algorithm is executed on this abstract MDP, assigning probabilities to edges when they are encountered for the first time. A policy is trained for each edge (S_0, S_1) in the abstract MDP where a random state in S_0 is the initial state and a random state in S_1 is the goal state. The success probability of the policy is used to assign the probability of the corresponding edge. The model is evaluated on two rooms environments and a fetch environment from OpenAI gym. The model is shown to outperform previous models.", "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": "Originality: It is not clear how the proposed DIRL model differs from available abstract MDP literature. Different from previous logical specification literature, this work explores utilizing abstract MDPs for effective planning. The paper mentions that it is different from previous abstract mdp literature since this work focuses on learning from logical specifications. I believe, if the corresponding abstract mdp is given, this would be a planning on abstract mdp problem where there is only a few related work in the paper. Especially, [1] is very relevant to this paper and shares some similarities. Please compare and clarify.\n\nQuality: \nThere are multiple assumptions in the paper that makes the problem a bit synthetic and not applicable to broader RL problems. It feels like the problem is very simplified as conversion from logical specifications to abstract mdp, planning on the abstract mdp, and training the agent on sub-tasks are all straightforward. I detailed some of these below.\n\n(i) Mapping from sub-regions to abstract states is assumed to be given. This is a crucial assumption where both terminal conditions for each subtask and execution of the high level plan depends on.\n\n(ii) The paper assumes the simulator can be modified. This allows the model to sample states more uniformly, especially since the set of states that correspond to a given abstract state is given. It is not clear if previous work that the paper compares also utilizes this. Please clarify.\n\n(iii) Is the safety constrain really required? There might be different safety requirements in general but this is already implied by the success of the low-level policy (and their edge probabilities) and the example in Figure 1 is more related to task success rather than a safety constrain. It is not clear if this is used in experiments as well. Please clarify.\n\nClarity: Paper is overall clear but it makes heavy use of notations which at times feel repetitive.\n\nSignificance: Results are significant and relevant to the RL community.\n\n[1] \"Abstract Value Iteration for Hierarchical Reinforcement Learning\", https://arxiv.org/pdf/2010.15638.pdf", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper makes several assumptions. In addition to the ones listed in the paper, it assumes logical specifications can be converted into an abstract mdp deterministically and a set of states that correspond to an abstract state is known.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "ltN8T1gcLn6", "reviewer": "Reviewer_WvH4", "summary": "This paper addresses the problem of synthesizing (using reinforcement\nlearning) a policy that satisfies a logical specification. The key\ninsight in this, and related works, is that the implicit structure\nof the specification can be used to decompose the learning problem\ninto several, ideally simpler, learning problems.\n\nTechnically, this work operates by first syntactically restricting the\nspace of (infinite horizon) tasks. This class is fairly expressive and\nhas the important property that tasks can be abstractly monitored\nusing a *finite* DAG - with (abstract) satisfaction now being a path\nfinding problem on the DAG abstraction. The conversion is automatic\nand the complexity grows linearly in the syntactic structure.\n\nThe graph structure then admits a nature mechanism to split the task\ninto sub-tasks, corresponding to traversing an edge in the DAG. Thus,\nby leveraging classic shortest path finding algorithms, where the cost\nis determined by the traversal probability - which is itself\ndetermined by training a policy in the workspace and empirical\nevaluation - one obtains a hierarchical policy. This defines an iterative algorithm which the paper shows\ncan be used to increase sample efficiency compared to various baselines.\n\n", "questions": "", "limitations": "", "rating": 7, "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": "At a high level, I found the writing and the exposition of the topics\nwell done. Furthermore, I feel that the topic of using logical\nformalisms for defining tasks in RL is a rich and important topic.\nThis work illustrates, for example, tasks can be naturally decomposed\nincreasing the efficiency of learning - and perhaps even the\ninterpretability and verifiability of the agent.\n\n## Empirical Evaluation\nI think the authors have done a fairly good empirical evaluation. I\nparticularly appreciated the inclusion of the two reward machine based\nalgorithms, which I would have a-priori considered to be natural\ncomparisons. One missing comparison I would have liked to see, but am\nok not having is an off-the-shelf hierarchical RL algorithm where the\nspecification DAG is treated as an MDP. This would have given me a\nbetter sense if the primary contribution is the decomposition of the\nproblem or the shortest path training scheme. That said, I am fairly\nconfident this approach would outperform such a base-line.\n\n## Clarification about Path policies\nMy understanding is that it may not always be the case that an edge is\nsuccessfully traversed in the DAG abstraction. One thing I would like\nclarified is what the high level polices do in such cases. The path\npolicies defined on line 238 seem to suggest that a path is first\nselected and then the system updates the path index. But if the edge\ntraversal fails, is this a stuttering transition? Or is it just that\nit takes an unbounded (possibly infinite) amount of time?  For example,\nif the agent accidentally enters a sink in the underlying MDP? While I think\nI understand how to fill in these holes, a more explicit discussion would\nhave been appreciated.\n\n## Role of reward shaping\nThe class of tasks considered in inherently sparse. The authors\npropose a reward shaping scheme, but I can't help but wonder how such\nan approach would compare with recent advances in learning directly\nfrom sparse rewards, e.g., Hindsight Experience Replay. It seems that\none of the reasons splitting up the task would improve performance\nwould be that sparse rewards need less long term planning. This would\nbe with the benefit of not accidentally introducing a reward bug due\nto shaping, which without knowing the dynamics, cannot be performed\nsafely in general.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that this line of research, in particular incorporating high\nlevel reasoning based on logical properties, is an important\ningredient safe AI.\n\nRegarding the limitations, I was pleased to see that the major\nlimitation I had noting when reading the paper was explicitly\naddressed in the conclusion. Namely, in order to trade edge policies\nit is important to be able to reliably initialize the system to an\narbitrary state, or a similar assumption. While in many domains, e.g.,\nsimulation, this may be reasonable, in other complex domains this\npresents a non-trivial problem and sub-task of its own. Nevertheless,\nI feel that this work is still valuable and the above limitation could\nbe overcome.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an approach to learning to solve a task from logical specifications by defining an abstract graph, planning on it, and learning the required low-level skills.
There were several concerns raised by the reviewers that were largely addressed in the discussion, leading to a positive evaluation of the paper.
Specifically, there were questions about the exact contribution, which the authors should make explicit in the final paper. The authors are expected to make the promised changes, including the suggested background and additional baselines, as well as further providing further discussions on the assumptions.

Decision: Accept (Poster)