Instructing Goal-Conditioned Reinforcement Learning Agents with Temporal Logic Objectives
Authors: Wenjie Qiu
Wensen Mao
He Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: Goal-Conditioned Reinforcement Learning
Linear Temporal Logic
TL;DR: We propose a novel approach that enables simple goal-conditioned RL agents to follow arbitrary LTL specifications without any additional training over the LTL task space.

Abstract: Goal-conditioned reinforcement learning (RL) is a powerful approach for learning general-purpose skills by reaching diverse goals. However, it has limitations when it comes to task-conditioned policies, where goals are specified by temporally extended instructions written in the Linear Temporal Logic (LTL) formal language. Existing approaches for finding LTL-satisfying policies rely on sampling a large set of LTL instructions during training to adapt to unseen tasks at inference time. However, these approaches do not guarantee generalization to out-of-distribution LTL objectives, which may have increased complexity. In this paper, we propose a novel approach to address this challenge. We show that simple goal-conditioned RL agents can be instructed to follow arbitrary LTL specifications without additional training over the LTL task space. Unlike existing approaches that focus on LTL specifications expressible as regular expressions, our technique is unrestricted and generalizes to $\omega$-regular expressions. Experiment results demonstrate the effectiveness of our approach in adapting goal-conditioned RL agents to satisfy complex temporal logic task specifications zero-shot.

Instructing Goal-Conditioned Reinforcement Learning Agents with Temporal Logic Objectives
Wenjie Qiu" Rutgers University SesT@ss.rutgerr
Wensen Mao Rutgers University wm3000cs rut.orss..rtggrseeee
He Zhu
Rutgers University h23750cs rutgerus.
Abstract
Goal-conditioned reinforcement learning (RL) is powerful approach for learning general-purye purpose skills by reaching diverse goals. However, it has limitations when it comes to task-conditioned policies, where goals are specified by temporally extended instructions written in the Linear Temporal Logic (LTL) formal language. Existing approaches for finding LTL-satisfying policies rely on sampling a large set of LTL instructions during training to adapt to unseen tasks at inference time. However, these approaches do not guarantee generalization to out-of-distribution LTL objectives, which may have increased complexity. In this paper, we propose novel approach to address this challenge. We show that simple goal-conditioned RL agents can be instructed to follow arbitrary LTL specifications without additional training over the LTL task space. Unlike existing approaches that focus on LTL regular expressions, technique is unrestricted
specifications expressible and generalizes to w-regular expressions. Experiment results demonstrate the effectiveness of our approach in adapting goal-conditioned RL agents satisfy complex temporal logic task specifications zero-shot.
Introduction
coal-conditioned learning Liu et al. [2022] is type of reinforcement learning (RL) task where agent learns to achieve a specific goal in a given environment. The goal can defined various ways, such particular state of the environment its current observations to actions that bring it closer to the goal. By providing a high-level goal, the agent effectively learn generalize its behavior and adapt changing conditions.
desired outcome, and the agent learns to map
However, goal-conditioned RL agents struggle with generalizing to more complex, task arientreettdd policies when the goals are specified by temporally extended instructions typically written in Linear Temporal Logic (LTL) languages, which creates much larger task space than simple goals. such cases, as the LTL task space is vast and difficult to exhaustively sample, it becomes more challenging for the agent to identify the correct sequence of actions needed to accomplish a task, which results in slow learning and poor generalization.
We propose novel approach that enables simple goal-conditioned RL agents follow arbitrary LTT specifications without any additional training over the LTL. task space. This is in sharp contrast to existing approaches for finding L.TL-satisfying policies, which require sampling a large set of LTL instructions from the task space during training "goals" Vaezipoor et al. [2021], Kuo et al. [2020]. Such methods have no guarantee in generalizing to unseen tasks outside their training distribution of LTL objectives. As example, the capability of most existing learning algorithms for LTL-satisfying policies is restricted to specifications over regular expressions that can modeled by reward machines Icarte al. [2022, 2018]. Our technique handle w w-regular LTL specifications
Wenjjie Qiu and Wensen Mao contributed equally this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

over infinite control sequences even though the underlying goal-conditioned agents have never seen such specifications during training.
Our main contribution lies in a policy learning algorithm for LTL. satisfaction, which decouples complex low-level environment interaction from high-level task planning. Specifically, we leverage a goal-conditioned RL agent to interact with low-level environments to learn how to achieve basic goals without considering higher-level tasks. The goal-conditioned RL agent has the capability of measuring the difficulty of transitioning between goals in the goal space. To solve an unseen LTL instruction ye, our method applies a weighted graph search algorithm that engages in high-level planning over the difficulty of achieving the specified goals to choose the optimal sequence of sub- goals in y for the goal goal-conditioned agent to reach. We present experimental results demonstrating the effectiveness of our technique in adapting condicondi RL agents to satisfy complex LTL task specifications of varying complexity zero-shot.
2 Background
Goal-Augmented Markov Decision Processes (MDPs) extend standard MDPs by incorporating a set of goals 9 within the system state space S. We assume the existence of a state-goal labeling function L: - 2 that maps each state set of atomic propositional symbols used to describe the observation of a system state where an atomic propositional symbol с G is a variable that takes on truth. Throughout the paper, the terms "goals" and "propositions" used interchangeably.
As an example, consider ZoneEnv, a Safety Gym environment Achiam and Amodei [2019] adapted from Vaezipoor et al. [2021]. The environ- ment (Fig. 1) is a walled 2D plane with colored zones that correspond to task propositions. Both the zones and the point robot randomly po- sitioned on the plane. this exam- ple,
2
W
rr
init
y
7
Figure 1: An LTL Task for ZoneEnv.
set of atomic proposi- tions G = {y, w, r. that represents the four colors yellow, white, red, and jet black.
L, Formally, we model a goal-augmenter MDP as a tuple (,, R, that consists of a state space S. action space A, goal space defined by a set of atomic propositions G, transition function T: Sx A S + [0, 1] that maps each state-action- attton-ston transition to a probability, a labeling function L, and reward function defined with the goals R: Sx 5xGxx x R that maps each state-action transition to a scalar reward for a particular goal in g. 7 e [0, 1) is discount factor that controls the relative importance of immediate versus future rewards.
In a augmentedd MDP, the agent's objective is to reach goal via a goal-conditioned pol- icy S G x A [0, 1] that maximizes the expectation of the cumulative reward: J(T) (p..)))) EE RR Ir, [t)] where Pg be distribution over goals in G. The optimal pol- Tu._T(()....)))
icy x¹ arg max, (TT) maximizes the expected cumulative return over all possible goals, weighted by their probability under the goal distribution Pg- This formulation encourages the policy to be effective at achieving a diverse set goals, rather than simply optimizing for single goal. For example, in the colored zone environment in Fig. (left), goal-conditioned agent policy T ({ass.)) can be trained to reach a specific colored zone E G = {y, w. w.r,
The value function for goal-conditioned reinforcement learning V* (**(s,g) returns the expected cumulative discounted reward obtained by following policy マ starting from state 8t with the goal g as the target: 4 (*)(stg) E a.-)(()).9); [E:0 ? R(s..g.a)) The coal-conditioned Q-function as,,)(()ss.s))))
Q* (St, 9, a) returns the expected cumulative discounted reward obtained by taking action in state 8t, and then following policy æ thereafter, with the goal g as the target: Q* 9, a) = r(tt, G, a) E (8t-1/82,4 (T)((((*+111)) The goal-conditioned Q and V functions may be learned using model-free RI. algorithms such as Q-learning or policy gradient methods. In training, we assume goals can be uniformly sampled. We also assume that tmax is the maximum horizon and goal-

---

conditioned agent receives positive reward signal only when it successfully achieves the specified goal by the end of training episode by framing a reward function:
r(st. 9. 1[t mmar] 1[g e L(s:)]
(I)
where the indicator function. This reward function has the following interpretation: given a state
St, will the goal-conditioned policy get to goal g after I. time steps of attempting to reach g.
Linear Temporal Logic (LTL) a formal language used specify the temporal properties of system. LTL formulas are built from a set of temporal operators, such as X ("next"), F (" ("eventually") "), G ("always"), and U ("until"). LTL formulas are constructed over a finite set of atomic proposition symbols G. Formally, the syntax of LTL formulas is defined recursively as follows:
== -p & s so yp Xip pUpp
Eyp
Gy where g g
Intuitively, the formula Xy holds if y holds at the next time step, (p1 U2p holds if (p1 holds until (22 holds, Fyp holds yp holds at future step, and Gip holds yp holds at the current and all future steps.
An LTL. formula op is said to be satis- fied by a state transition system with state space S if and only all infinite sequences of states of the system sat- isty sp We assume the existence of labeling function L S 2 that maps each state to the atomic proposi- tions that are true in that state. Given an infinite sequence of system states
s; = g if g is an atomic proposition and g L(s;) holds.
s, F =F g.
#F s; y and s; F 92-
8 F #1 V 62 & 41 or 8; 4
s; +xp 8 sf+1 Pp.
(so, $1, ... generated by a system, = models the satisfaction relation = between an LTL formula y and the sequence of system states Formally, 7 F yp if and only if so y which. We can define 8; F induc- tively, as illustrated on the right.
Fy if there exists j i such that sy F 4.
8, GGp if for all j i, F
8; 1= yp Usp2 if there exists j 2 i such that 8j 922 and for all i s l <j. 401-
In the ZoneEnv example in Fig. 1 (left), the robot is tasked to oscillate between yellow zones and white zones while always avoiding red zones. Assume set of atomic propositions G {y. w, wrr. that represents the four colors yellow, white, red, and jet black. The LTL objective for this task can be specified as:
GF A XFw) G(-r)
Büchi Automaton is type of automaton used to recognize languages that consist of infinite sequences of symbols. A Büchi automaton is defined by a tuple EQ go F), where Q is a finite set of automaton states, is a finite alphabet of symbols, 6 : Q x L 2 is transition function that maps each state and symbol to set of states, qo Q is the initial state, and F' Q is a set of accepting states. Informally, a Büchi automaton recognizes a language consisting of all infinite sequences of symbols (corresponding automaton runs) that visit accepting state infinitely often.
Büchi Automaton Construction from LTL. Büchi automata can be used represent temporal specifications in LTL. Given an LTL formula &p over set of propositional symbols in G, Büchi automaton B can constructed that recognizes all infinite sequences system states that satisfy y. The alphabet Σ of the Büchi automaton B is over the set of atomic propositions G of yp, i.e., Σ= = 29. That is, an infinite sequence system states So, $1; $2.... satisfics yp if and only if there exists an infinite sequence of automaton states qo, 91, 92.... in B such that qo is the initial automaton state, for all i 2 O, if s; |= w, where w; E Σ then 8(4, w;) contains at least one state, and the set of states that occur infinitely often in the sequence qu. 91, .2.... is subset of the accepting states of B.
For example, for the ZoneEnv task in Fig. 1 (left), the converted Büchi automaton for the LTL task in Eq. 2 is depicted in Fig. (right). The only accepting state in this machine is state 2. To reach the accepting state, a yellow zone must be visited first. The Büchi automaton accepts when state reached infinitely often, meaning that the agent must always make a loop back to state 2 from state 3 and then state by visiting a white zone and a yellow zone. This kind of infinite looping behavior cannot be expressed by regular expression.
3

---

3 Instructing Goal-Conditioned Agents with LTL Objectives
Task-Augmented Markov Decision Processes. We now formalize the problem of instructing an RL agent to follow LTL objectives. To this end, we generalize Goal-Augmented MDPs to Task- Augmented MDPs A, Φ L, T) where the definitions for state space S, action space A, goal space G, labeling function L (from states to atomic propositions in 9), state transition function remain the same. & the universe space of LTL formulas that can be constructed from the propositions in G. We would like to construct policy π Talss, sp) such that for any possible LTL formula y e Φ the policy π (a|s, :p) has the highest probability L.L specification satisfaction with respect to yp:
x arg max (+h))) [[[T=
In this formulation, a task- augmented MDP does not have a reward function. Instead, the objective is to generate the most number of LTL-satisynnng runs for given LTL task. The MDP does not have a maximum horizon as the agent is expected to run over an infinite time horizon to satisfy an (w-regular) LTL instruction (e.g., Fig. 1).
Solving task lask-augmented MDPs turns out to be significantly more challenging than learning for goal-augmented MDPs due to the extremely large task space, which grows exponentially with the number of goals. The agent must identify the correct sequence of sub- goals to accomplish an LTL task. For the ZoneEnv example in Fig. 1, agent may be instructed reaching a white zone first and then proceeding to a red zone two distinct phases. In each phase, the to avoid changes (avoiding jet black and then yellow). We specify this task in Eq. 4 whose Büchi automaton representation is depicted in Fig. 2.
init
w
accomplish task by
Figure 2: Another LTL task for ZoneEnv.
-jU(w (-yUr))
(4)
The two LTL tasks in Eq. 2 and Eq. 4 express very different requirements and require distinct logic to solve, The agent expected to successfully fulfill both tasks during inference.
3.1 LTL Task Planning on Büchi Automata
Our approach relies on the principle that an accepting of Büchi au- tomaton must contain an accepting state that is reachable from the initial state and lies on a cycle (e.g., Fig. 1). This means that accepting runs of Büchi automaton can be searched on top of directed graph representation of the automaton. A goal-conditioned agent can then be used to subsequently achieve the goals along the search paths for task execution.
8
(2,1)
2
(0,2)
(2,2)
init
(2.0)
(1.I)
(3.1)
(3.3)
Figure 3: An LTL Task for Ant-166oome 16rooms where the red path is more feasible than the black path.
However, this simple strategy may yield suboptimal task performance. Consider a Mujoco ant navigation task in 16-room environment depicted in Fig. 3(eft). The rooms are separated by thick walls and are connected through bi-directional doors. The agent is initially positioned at the center of the bottom-left room and is given the following LTL instruction to traverse through the centers of series of rooms with choices:
() (2,0)) 2(2,2) A F(((2.1) v (3,2)) A F((3,1) ((((L,)) AF(L,
Here an atomic proposition g G is in the form of (r,c) c) denoting the room in the r-th row and c-th column. The bottom-left corner is room (0.0). 0). Given an environment state define = (r,c) is true the position of the Mujoco ant in s close to the center of the (r, e)-th room within threshold. The Büchi automaton B converted from the LTL instruction is given in Fig. 3(right). There are 8 paths on to reach the accepting state 6. graph search algorithm could yield any of these paths for the Mujoco ant to traverse along the chosen route. However, not all of them are equally optimal.

---

62
0,33
(8)
[b]
W =ye -0
L(a)) =Ay
8t
91
91
41
91
V -y Bi
V AA By
V -A 8J
(e)
Figure 4: Graphs (a), (b), and (c) are converted from the Büchi automata in Fig. 3, Fig. 1, and Fig. 2. (d), (e), and (f) are types of transitions in graph representation of Bücci automaton.
Some of the routes require the ant to take a detour to avoid the black obstacles placed in certain room centers. In the worst case, the agent may be blocked by the obstacles and cannot complete the task.
In order to optimally accomplish the sequences of tasks defined in an L.T. instruction with atomic propositions in g, we perform high-level reasoning by evaluating the difficulty of achieving the specified goals (i.e. atomic propositions) in yp in the goal space G. Our technique exploits the value function V"(s, ("(ss g) of a goal-conditioned agent T (+|s, g) to capture the agent's s transition capabilities. For any pair of goals, we learn goal value function V S x G G - I to estimate the capability of taking the goal-conditioned policy π to go from one goal to another goal on average. The function parameterized by environment state because the agent's 's capability to transition between goals can differ depending on various environment layouts and agent states. To get the desired estimate, we regress V towards the value function of by minimizing:
(5) with r ~ B (a replay buffer), t ~ {0... tmaz]. St, at, S141 ~ ~ =T {0, h ~ f tmax J. and L as the state labeling function. We train V together with goal-conditioned learning algorithm.
min (V(tt, (*)).Bt:)))) where 9a ((8s)) A g (s(s)
With the learned goal value function V of goal-conditioned agent as a measurement to assess its capability to transition between goals, reduce the task of learning an LTL specification satisfying policy to finding the optimal accepting run in the Büchi automaton representation of the LTL specification. We convert a Büchi automaton B (Q, E, 8. go. F) as directed graph GB (2, Σ, A, Fo,F, L) with nodes 2, node transitions (edges) A over the same alphabet Σ, a set of initial nodes 2o and accepting nodes F. The conversion from B to graph GB starts with setting Q = Q A 8, Oo { and F F. The node labeling function L maps nodes in Q to atomic propositions (or goals) in the alphabet Σ. Intuitively. L approximates the specific region in the goal space where the agent should be positioned at given node. For each non-self transition (q:, v q;) in B where v encodes the goal space to which the transition enabled, we have L(g, v. As an example, Fig. 4(a) depicts the converted graph representation Gg from the Büchi automaton in Fig. 3rightt.. For the transition from the initial node to node 1, the node labeling function maps node to goal room (0. 2). This transition denotes that the agent reaches room (0, from the initial room. If there are several incoming transitions with different alphabet symbols to q in B, we duplicate qj and its outgoing transitions in G3 so that each duplicated node for qj captures one of the possible transitions to qj- For example, Fig. 3, there are two non-self Büchi automaton transitions to state 1 which are encoded as node transitions from the initial room to room (0,2) and (2, 0) respectively in Fig. 4(a). An exception for constructing the node labeling function L occurs when d takes the form of A& -Ok negative, indicating a specific area in the goal space that must be avoided to activate the transition. In this case, the designated goal area outlined by vé for g can be excessively large. We instead assign [(g;)= = L(q.). Intuitively, if gk does not intersect with the current state on ((g:). the agent can trivially fulfill the avoidance requirement by making "jumped" transition to qj- For example, the "avoidance" transition from state 2 to state on the Büchi automaton in Fig. (rright) is encoded as the rightmost non-self transition in the graph representation of the automaton in Fig. 4(b).
non-self transition (gi, ti, q3) where all atomic propositions 9k
We interpret the semantics of graph representation GB converted from a Büchi automaton B through the different kinds of non- transitions that Gg may have, as visualized in Fig. 4(d), (c), and (f). In
5

---

Fig. 4(d), on non-self transition (g, 15, .)),), in order to transit to qj, the goal-conditioned agent is tasked to reach the goal region v = A 9j from the goal region [(g)) A, 9t- The "self-transition" on node di describes a goal-related constraint v As -Ot that must be maintained until the goal-conditioned agent can transit to Gj- The agent can take an unlimited number of steps to reach the goal region vi, provided that each step avoids entering any undesired region Ik within v/L. For weighted graph search, we assign the weight of such a transition as:
W(s, (g:, 2) (;)) = max - log (i,,gi.9;) where [())) Asi gi and vp 9
(6)
9:.9;
The weight encodes the capability of a goal-condition agent to transit from to qj from an obser- vation at environment state s. In Fig. 4(d), we restrict L(g:). eb and vi to conjunctions of atomic propositions or negated propositions. In Appendix G.3, we extend this definition to include formulas as conjunctions of propositions and their negations to support more complex LTL tasks, such as F -92).
In Fig. 4(e), the transition is similar that of Fig. 4(d), and the agent can also take many steps as necessary to reach the goal region specified by & by utilizing the self transition on the source node 9₁- However, there are no specific avoidance requirements to consider. We use Equation to weigh this kind of transition. In Fig. 4(f), the goal-conditioned agent is required to reach the goal region & in exactly one step as there is not any self transition that can be taken upon qt. We set W(s, (4: (,g;;) q;)) = 0 (the full capacity) if ((g:) < db i.c. the agent can directly "jump" to gj (e.g. see the rightmost non-self transition in Fig. 4(b)). Otherwise, we assign it the lowest capacity W(s, (g:, v, (;);)) co. This is because our approach cannot explicitly pick an action to reach goal region in a single step (we instead depend on the gond-cond agent to take as many steps as needed for goal reaching).
3.2 Algorithm Summary
Our technique generates policies for LTL specification yp based goal-conditioned RL agent and a learned goal value function V as follows:
1. We first convert o to Büchi automaton B, which is subsequently converted to graph representa- tion Gg using the technique illustrated in Sec. 3.1.
2. Associate each transition (g;, vh. qj) on GB with weight W(s, (4, 1, q;)) according to Equation 6 measure the capability of the goal-conditioned agent to make the transition. In our implementation, we set as the initial state of an episode. A more advanced planning strategy may conduct task planning every l timesteps from current environment state for the remaining sub-goals on G3 and update the weight of any transition based on the current state before replanning.
3. Decompose GB into strongly connected components (SCCs) using Tarjan's algorithm Tarjan [1972].
4. To find an optimal path on Gg for task execution to satisfy the LTL so, we follow these steps:
For each accepting state 8a within a maximal SCC Geldenhuys and Valmari [2004], we use Dijkstra's algorithm to find the shortest path from the initial state to 8a, denoted as p.
Next, we apply Dijkstra's 's algorithm to find the shortest cycle from back to 8a in the maximal SCC, denoted as q.
The optimal path for the accepting state is pq where of times the shortest cycle executed. The cost of the optimal path is calculated as w(p)+ w()) where wp) or w(q) is the sum of the weights of the transitions on p or q. In the implementation. we use w = to estimate the path cost.
represents the number
Finally, we select the optimal path on Gg the least-cost path any accepting state of Gg.
5. For task execution, on the searched optimal path pg" we use a goal-conditioned agent to subsequently achieve the goals along the path p and reach the goals on q iteratively in a loop to satisfy p. For any transition (q;, th, qÿ) on searched path, the agent employs its gond-conditioned policy (-Is,.) e) to reach the targeted goal region vo (Fig. (()).
Justification. Recall that our objective of learning a LTL specification satisfying policy (Equation 3) finding n² = arg max, (. [1[ yl], which generates the maximum number of LTT.- satisfying runs for a given LTL property sp. Our formalization of goal-condition RL uses sparse

---

binary reward function (Equation 1) reward of I is provided only when the specified goal is successfully achieved by the end of training episode. In this setting, when the discounted factor 1, the weight w of transition on Gg, which is determined by the learned value function )/ (e.g. W! log V()), is inversely proportional
the probability of reaching the goal region represented by the target node from that represented by the source node. As such, based on the capability of the goal-conditioned agent (i.e. the learned value function V), the task planning algorithm seeks the optimal path as the one the agent is most likely to succeed.
3.3 Handling Avoidance
As depicted in Fig. 4(d), our method uses the goal-conditioned agent policy f to fulfill a reach-avoid subtask defined as #(-|s, A gj.Ax -9x) from a state s an agent is required avoid several regions It (A 2 1) before reaching the target region A 9j in the goal space. Our method only performs avoidance in situations where there is a high likelihood of colliding with any ge- The likelihood of a collision occurring with IL from a current state s can be assessed by evaluating the value function V(s.gk) 9k) of the con-icondi agent. If Vss gs) exceeds a threshold o,, indicates high likelihood of collision. We formally define the reach-avoid policy मे as follows:
The strategy is to find the most dangerous It to avoid. A predicted value ((*,gt) below the threshold (e.g., 0.85) signifies that Jk is not considered dangerous and does not need to be avoided. We then take goal-reaching action arg max, min, (*((19) 9j. a) Tasse et al. [2020] for reaching the overlapped goal space covered by Aj 9j. Otherwise, we select safe action arg ming Q(s, gk: a) that moves the agent away from the dangerous zone 9I: and identify dangerous action d arg max, Q(+, Ik: a) that moves the agent directly to the dangerous zone Gs- We then select "blocked" goal-reaching action arg m&Xard min; Q" 9j. a) to elim- inate the impact from the dangerous action d. For continuous environments, we generate the com- bined action + that accounts for both safety and reachability. For discrete environments, simply return to block the effect of unsafe ac- tions.
0z -9h)=
1 k
let k arg max (( in
if Vss.gh) <o
then arg magmaxma min Q" (j)))
else
let d arg max Q( fk.
let s= arg min Q J2.
let f = arg max min Q" 95. and
8 s+1
Figure 5: Handling reach-avoid subtasks by goal-
conditioned agents in GCRL-LTL.
Experiments
We implemented our algorithm a tool called GCRL-LTL that extends goal-condition RL to task-oriented RL where tasks are specified by LTL objectives.
We evaluate GCRL-LTL in the ZoneEny environment shown in Fig. and the Ant-16rooms environ- ments depicted in Fig. 3. We also include a 7x7 discrete grid-based enviromment LetterWorld from Andreas et [2017]. In this environment, 12 unique letters occupy 24 positions out of 49 squares, where each letter is presented twice. This denotes the agent can satisfy an atomic proposition by reaching any of the two. The initial positions of the robots and the zones or letters are random in every episode. More information about these environments is provided in Appendix G.I.
Primitives. As shown in Fig. our agent policy requires enumerating the action space perform an avoidance maneuver when a collision is imminent. To support efficient enumeration over continuous action space, we pretrain four neural primitive skills that can move the Point robot in ZoneEnv and Mujoco ant in Ant-In6oon 6rooms along the four cardinal directions UP. DOWN, LEFT, RIGHT. Each of the skills is trained for 0.5 million steps. More details for primitive training are given in Appendix G.2. To ensure fair comparison, both our learning algorithm and the baselines get access to the neural primitives, which enable discrete action space for both.
*GCRL-LTL is available at https: :/:::t//gtttt www/co////////eeee Automated wawttmatted-eedseinnnnng Croup/GCRL-IL
7

---

LafterWedd Wefiudy-Ordree Saits
Lottie BEIi Partialy Oedered Thaks
LetterWori Anvedance Soits
Lotter/erne boustance Tass
GERLOL
0.
02
1PERS
(a)
(b)
(c)
Figure 6: (a) and (b) shows success rates and discounted rewards of LetterWorld partially- ordered tasks, respectively. (c) and (d) shows success rates and discounted rewards on avoidance tasks, respectively. We report the average results random seeds, where each data point is acquired by collecting results from 100 episodes.
Figure 7: Comparisons of (a) success rate and (b) dis- counted rewards in ZoneEnv on avoidance tasks. We re- port the average results 5 random seeds, where each data point is acquired by collecting results from 50 episodes. The initial mil- lion steps are omitted due to the training of the dynamic primitives.
ZoneEavi Avoidance Tasks
ZoneEnv: Avoidance Tasks
1.0
OERL LTL
0.0
OCIL LT!.
08-
0.7
[ 0.4
0.3
0.2
0.1
0.1
02
03
04
05
0.5
07
0.6
0.
1.0
3.5
02
03
0A
05
08
03
0.5
09
1.0
13
(a)
(b)
We extend Proximal Policy Optimization (PPO) (Schulman et al. [2017]) to goal-conditioned RL. algorithm to train the goal-conditioned agents for LetterWorld and ZoneEnv. We use an extension of the GCSL Ghosh et al. [2021] algorithm to train goal-conditioned agent for Ant-16rooms. More details about the training algorithms are provided in Appendix B.
4.1 Evaluation in Multi-Task Settings
Baseline. We compared GCRL-LTL with LTL2Action (Vaezipoor et al. [2021]). This baseline exemplifies the Mfte-of-theear learning algorithms for LTL-satisfying policies that use advanced neural architectures to encode LTL task formulas for policy decision making. In contrast, GCRL-LTL employs weighted graph search decompose LTL tasks into basic reach-avoid tasks that can be accomplished by goal-conditioned agents.
socision-making...
We consider the following L.T. task spaces to evaluate GCRL--ITI. and the baseline.
Partially-Ordere Tasks. Such a task consists multiple streams of sub-tasks. sub-task contains a sequence of goals that must be satisfied in specified order. For instance, possible task can be F(p F(q ^ Fr)) F(s Fq). This task can be described as "satisfy p. q. r that order; and satisfy q in that order". One valid solution is to reach 4, in order to satisfy all sub-tasks.
Avoidance Tasks. Similar partially ordered tasks, sequence of propositions must be satisfied in order, while some propositions must be avoided. Visiting a prohibited position leads to failure. An example avoidance task is -jU(w A (-yUr)) (Fig. 2), which can be interpreted as a two-stage task: "reach w while avoiding j in the first stage, then reach while avoiding y in the second stage".
During training, LTL2Action has access the large set of possible task spaces described above for each training episode. GCRL-LTL does not use the task sampler and is only trained to reach random goals. In evaluation, tasks are randomly sampled in each episode for both agents. We choose a = 0.85 in Fig. and perform ablation study on this value in Appendix G.3.
task sampler that produces random LTL task from
Figure shows the evaluation results across training iterations on both partially ordered and avoidance tasks in LetterWorld. Fig. 7 demonstrates the results for avoidance tasks in ZoneEnv. GCRL-LTL outperforms L.T.2Accion by a large margin despite having no access to the task sampler during training. Furthermore, assess the generalizability of GCRL-LTL and the baseline by testing
8

---

Figure 8: Figures (a) and (b) depict the performance of trained goal-conditioned agents in satisfying the w- loop and w-stability tasks in the ZoneEnv environment. Each data point represents the average performance ob- tained from evaluation on 20 episodes, and the results are averaged over random seeds.
2.
ZoneEmw: s-Loop Tasks
750
ZoneErv; u-Stability Tacks
144
350
110
150
0.4
150
90
02
03
644
05
0.6
67
08
02
03
04
05
68
10
(a)
(b)
Environment
Tasks Partially-Ordere
Timeout
Ours
LTL2Action
75
0.996(0.423)
0.661(0.129)
LetterWorld
Partially- Ordered + Depth
Pariaall-Ordered
225
0.986(0.259)
0.477(0.033)
Partially-Ordered + Conjuncts ft
225
0.992(0.410)
0.567(0.049)
Avoidance
1000
0.958(0.632)
0.934(0.601)
ZoneEnv
F(a (ooAX((UUe)) G(-d)
1000
0.928(0.543)
0.342(0.304)
F(a F(C Fd))
2000
0.926(0.220)
0.060(0.020)
Table I:
Performance of trained agents on original and out-of-distribution tasks. We report the
success rate and discounted return(in parentheses). Results are averaged over 1000 episodes.
them on more complex tasks that are out-of-distribution to task sampler used in baseline training. Specifically, for partially ordered tasks in LetterWorld, we increase the maximum depth from to 15, and the number of conjunctions from to 12. Similarly, we extend the avoidance tasks in ZoneEnv to a more difficult setting where the agent needs to avoid one extra zone in the second stage (a A X(-bUc)) A G(-d)). Additionally, we test if agents trained in ZoneEnv can efficiently solve tasks in which a long sequence of consecutive zones must be reached (F(a F(b F(c A Fd))). The experimental results, as detailed in Table I, indicate that GCRL-LTL significantly outperforms the baseline in its ability to generalize unseen tasks.
w-regular LTL Tasks. We conducted experi- ments to evaluate the performance of GCRL- LTL in satisfying w-regular LTL objectives. w-Stability Tasks: such task requires the agent to satisfy task proposition by reach- ing goal region and remaining in the goal region infinitely, woLoop Tasks: such a task in the form GF(( XF6) G(-c) requires the agent to continuously cycle between two specific zones, and b, while always avoid- ing another zone, c. For example, in the task GF(r A XFy) G(-w), the agent expected to traverse between the Red and Yellow zones indefinitely, while
(a)
(b)
Figure 9: Figures (a) and (b) illustrate agent trajec- tories that solve the w-loop task GF(r XFy) ) A G(-w) in the ZoneEny environment. The initial positions of the robot are represented by orange diamonds
visiting any White zone. We evaluate the satisfiability of w-loop and w- stability tasks in the ZoneEnv environment dur- ing the coal-conditioned agent training process. The results are presented in Figure 8. The x-axis represents the number of environment interaction steps, while the y-axis represents the number of occurrences. In the w-loop tasks represents the number of rounds completed by the agent in looping between specific zones, and in the w-stability tasks it represents the number of transitions the agent successfully remains
desired zone, within the first 1500 timesteps (higher values indicate better performance). The results confirm that GCRL-LTL can handle w-regular L.TL. specifications even though the underlying goal-conditioned agents have never seen such specifications during their training time. Figures 9a and 9b illustrate agent trajectories that solve the above w- WLLTL task. In both

---

trajectories, the robot quickly reaches the Red zone and subsequently oscillates between the Red and Yellow zones. More examples can be found in Appendix E.
4.2 Comparison with Compositional RL
We also compare our approach with DiRL ( Jothimurugan et al. [2021]), which is state-of-the-ar compositional RL algorithm for LTL-satisfying policies. DiRL simultaneously learns low-level policy for each sub-goal transition and a high-level policy to plan over the sub-goal space. However, is restricted to a small fragment of LTL, cannot handle w-regular LTL properties (e.g. Fig. 1), and cannot be applied to multi-task RL because the low-level policies are specific to a single environment setting and do not generalize across different environments. We used 8 LTL task specifications. These tasks have increasing levels of difficulty as they require the agent to sequentially reach a growing number of sub-goals. An example instruction is given in Fig. 3. DiRL has to train separate agent for each of the LTL specifications. In contrast, GCRL-LTL trains a single goal-conditioned agent and evaluates this agent over all LTL specifications. Our agent achieves success rate of approximately 90% in fulfilling all specifications after being trained with 3e6 environment steps, whereas the DiRL method has to exercise 3e6 steps for each of the specifications to match the success rate of GCRL-LTL. More comprehensive evaluation results are given in Appendix F.
5 Related Work
There exists a large amount of previous work in using linear temporal logic (LTL) for specifying or
shaping the reward functions for reinforcement learning (RL) Aksaray et al. [2016], Littman et al. [2017], Sadigh et al. [2014], Hasanbeig et al. [2018], Cai et al. [2021], Hahn et al. [2018], Camacho al. [2019], Hasanbeig et al. [2020]. Jothimurugan et al. [2020], Icarte et al. [2018. 2022]. These methods primarily concentrate on learning a single, specific task defined by an LTL objective. In contrast, our approach involves learning task-oriented policies akin to cond-conditi RL agents within a multitasking framework. In this setup, a new arbitrarily complex LTL task is sampled as a goal for each episode.
Past research efforts have also aimed to empower RL agents to handle previously unseen multi- task instructions expressed in LTL. One common solution decomposing complex LTL tasks into smaller, independent subtasks to simplify the learning process. For example, Araki et al. [2021] develops hierarchical options framework that learns various neural networks each specialized for one subtask, and optimally composes these learned options via value iteration to solve temporal logic specifications. However, subtask execution does not consider what the agent must do afterward and hence might perform sub-optimally in solving the full task. León et al. [2022] progresses towards completion of an LTL task by greedily identifying subtasks of the original LTL instruction that remain to be addressed, which may result in myopic behaviors. Recent works show that the agents' neural architecture to embed LTL specifications is the key to improving the performance of RL agents in unseen environments. Kuo et al. [2020] presents a novel network architecture framework to compose neural networks one for each L.L. operator and environment object to mirror the formula structure. In a similar vein, Vaezipoor et al. [2021] uses neural encodings to interpret full L.TI. specifications to guide an RI. agent to learn task-conditioned policies in multitask settings. Voloshin et al. [2023] developed eventual discounting that exploits the fact that optimally satisfying the LTL specification does not depend on the length of time takes to reach accepting states (e.g., "eventually always reach the goal") to find LTL-satisfying policies with the highest achievable probability. We discuss the other related work in a more general context in Appendix C.
Conclusion
This paper presents GCRL-LTL to learn task-oriented policies where tasks are specified by Linear Temporal Logic (LTL) instructions. Unlike existing methods that sample a vast set of LTL instructions during training, our approach enables simple coal-conditioned RL agents to follow arbitrary and complex LTL specifications without the need for additional training over the LTL task space. GCRL- LTL is capable of handling diverse and intricate LTL specifications including w-LTL objectives over infinite time horizons. Through extensive experiments, we demonstrated the effectiveness of GCRL-LTL to seamlessly satisfy complex temporal logic task specifications zero-shot manner.
10

---

Acknowledgements
We thank the anonymous reviewers for their comments and suggestions. This work was supported by NSF Award #CCF-2124155 and NSF Award #CCF-2007799.
References
Minghuan Liu, Menghui Zhu, and Weinan Zhang. Goal-conditioned reinforcement learning: Problems and solutions. Luc De Raedt, editor, Pruceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, IJCAI 2022. Vienna, Austria, 23-29 July 2022, pages 5502-5511, 1.jaaio... 24963/ 12493//icaaa /aa////j...a/// 2022/770.
ijeai.org, 2022. doi:
10.24967/ URL
Pashootan Vaezipoor, Andrew C. Li, Rodrigo Toro Icarte, and Sheila A. Mcllraith. Ltl2actio:: Generalizing LTL instructions for multi-task RL. CoRR, abs/2102.06858. 2021. URL https://arxiv org/ abs 2202. 06858.
Yen-Ling Kuo, Boris Katz, and Andrei Barbu, Encoding formulas as deep networks: Reinforcement learning for zero-shot exccution of LTL formulas, In IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2020, Las Vegas, NV, USA, October 24, 2020 - January 24, 2021, pages 5604-5610. IEEE, 2020. doi: 10.1 201.:000
URL https: / /ttp///o..oo/oo org/10 10. (009/R0055743 2020 9341325.
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73:173-208, jan 2022. doi: 10.1613/jair. 1.t.air...1144...... 12440. URL https: org/10 10. 1613%22 12440.
Rodrigo Toro Iearte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2107-2116. PMLR, 10-15 Jul 2018. URL https: html.
//proceedings. mlr. grress/800icartteo
Joshua Achiam and Dario Amodei. Benchmarking safe exploration deep reinforcement learning. 2019. URL bestps///apl. wemanticscholl............. www.ccccoooooooooooooooeeeeeeeee Corps/Dr 208283920.
Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2)146-160, 1972, doi: 10.1137/0201010 URL https: org/10 10. 1137 /0201010.
Jaco Geldenhuys and Antti Valmari. Tarjan's 's algorithm makes on-the-fly fly LTL verification more efficient. In Kurt Jensen and Andreas Podelski, editors, Tools and Algorithms for the Construction and Analysis of Systems, 10th International Conference, TACAS 2004, Held Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 April 2, 2004, Proceedings, volume 2988 of Lecture Notes Computer Science, pages 205-219. Springer, 2004. doi: 10.10007978-3-540022 30-21_18.. URL https:/ / //oo//i.o//// orgii.ogg11... 1007/978--30 ---77777--------- 20:30022470-22
Geraud Nangue Tasse, Steven D. James, and Benjamin Rosman. A boolean task algebra for reinforcement learn- ing. In Hugo Larochelle. Mare' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tiae Lin, editors.Advunce Advances in Neural Information Processing Systems 33; Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 1- 2020, virtual, 2020. URL https: / htppp/occeednns... neurips wwtpppppp/pp/ptpppccpoteeeeeaeat 2020/ hae00/hahhh/bbaae
Abstract html.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches, 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.066 063347,7777 2017. URL http: //arxivvaivvi///aa org/ abs/1707 .03347.
Dibya Ghosh, Abhishek Gupta, Ashwin Reddy, Justin Fu, Coline Manon Devin, Benjamin Eysenbach, and Sergey Levine. Learning reach goals via iterated supervised learning. In 9th International Conference on Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.nee, 2021. URL https: http://///peeeeeeeeeeeeeeeee/eee http://oruum/ddrrAAAXX 1dxrALA0
Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforcement learning from logical specifications. CoRR, 0ts/2106.13990 2021. URL attpss://arxia www.ooo///////////////oo/eee abs/aaass.1//// 13906.
Derya Aksaray, Austin Jones, Zhaodan Kong. Mac Schwager, and Calin Belta. Q-learning for robust satisfaction of signal temporal logic specifications, 2016.

---

Michael L. Littman, Ufuk Topcu, Jie Fu, Charles Lee Isbell Jr. Min Wen, and James MacGlashan. Environment- independent task specifications via GLTL. CoRR, 704.0441, 2017. URL http:://atiii....../// org/ abs/ 1704. 04341.
Dorsa Sadigh, Eric S. Kim, Samuel Congan, S. Shankar Sastry, and Sanjit A. Seshia. A learning based approach to control synthesis of markov decision processes for linear temporal logic specifications. In 53rd IEEE Conference on Decision and Control, pages 1091-1096, 2014. doi: 10.1109CCDC.201147005557
Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening, Logically-coorrcttciinnoor CoRR, abs/1801.0809) 2018. URL
lcarning.
Mingyu Cai, Mohammadhosein Hasanbeig, Shaoping Xiao, Alessandro Abate, and Zhen Kan. Modular deep reinforcement learning for continuous motion planning with temporal logic. IEEE Robotics and Automation Letters, 6(4))7973-7980, oct 2021. doi: 10.1 109/1r02021.310000 2F1ra. 202.23002211111 3101544.
URL httph:ttp////et http::://ddoo//or////e//
1109%
Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtezak. Omega-regular objectives in model-free reinforcement learning. CoRR, 0bs/1810.00950/ 2018. URL
http://arxiv.oo abs/ /1000.1000000 00950.
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 Procedings of the Twenty-Fighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 6065-6073. International Joint Conferences Artificial Intelligence Organization, 7 2019. doi: 10.24963/jcci.2019999 2019///4..01//0000
URL https: //doii./////////// org/ 10. 24963/24944// ijcaiiiaai.... 2019/840.
Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep reinforcement learning with temporal logics. In Nathalie Bertrand and Nils Jansen, editors, Formal Modeling and Analysis of Timed Systems, pages 1-22, Cham, 2020. Springer International Publishing. ISBN 978-3-030-57628-8,
Kishor Iothimurugan, Rajeev Alur, and Oshert Bastani. A composable specification language for reinforcement learning tasks, 2020.
Brandon Araki, Xiao Li, Kiran Vodrahalli, Jonathan A. DeCastro, Micah J. Fry, and Danicla Rus. The logical options framework. CoRR, abs/2102.12571, 2021. URL https://arxiv wwtpriiii.oo/aaaooooo aa//a/b///2200 12571.
Borja G. León, Murray Shanahan, and Francesco Belardinelli, In a nutshell, the human asked for this: Latent goals for following temporal specifications. In International Conference on Learning Representations, 2022. URL htPL::tt///opeereerie net peee//oorummmddddusSSw3]]
Cameron Voloshin, Abhinav Verma, and Yisong Yue. Eventual discounting temporal logic counterfactual
experience replay, 2023.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1312-13200 Lille, France, 07-09 Jul 2015. PMLR. URL https: http://///..oooog......m mlr. .ttess/ / /v33//33////// 337/schal115 html.
Alexander Trout, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your distance: Solving sparse reward lasks using self-balancing shaped rewards, 2019.
Soroush Nasiriany, Vitchyr H. Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned policies, 2019.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Scarch on the replay buffer: Bridging planning and reinforcement leamning, 2019.
Elliot Chane-Sane Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditiona reinforcement learning with imagined subgoals, 2021.
Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World model a graph: Learning latent landmarks for planning. 2021.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay, 2018.
Paulo Rauber, Avinash Ummadisingu, Filipe Mutz, and Juergen Schmidhuber. Hindsight policy gradients, 2019.
12

---

Menghui Zhu, Minghuan Liu, Jian Shen, Zhicheng Zhang, Sheng Chen, Weinan Zhang. Deheng Ye, Yong Yu, Qiang Fu, and Wei Yang. Mapgo: Model-assisted policy optimization for goal-oriented tasks, 2021.
Lewis Hammond, Alessandro Abate, Julian Gutierrez, and Michael J. Wooldridge. Multi-agent reinforcement learning with temporal logic specifications. CoRR. abs/2102.00588,, 2021. URL https://aaxiiv org/abb...rrr//..s/./// 2102.00582
Shao-Hua Sun, Te-Lin Wu, and Joseph Lim. Program guided agent. In International Conference Learning Representations, 2020. URL http://ppeeeeee..eeeteee B
Zelin Zhao, Karan Samel, Binghong Chen, and Le Song, Proto: Program-guidee transformer for program-guided tasks, 2021.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, pages 5026-5034 2012. 10.1 111.11//...000..666666666 2012.6386109.
Horia Mania, Aurelia Guy, Benjamin Recht. Simple random search of static linear policies com- petitive for reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: httpp//ooceenn....//// ieseeddinns.nuuiis........ wweurips.ccppappeeepeeeeeeeeeeep http:/eeppppeeeeeeeepeeeeeeeeeee /ttps//t//////pp/////////l/ (ageeaaaaeedi0111118871eeeeee...
Paper Paper-pdf.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking Safe Exploration in Deep Reinforeement Learning. 2019.
Antonin Raflin, Ashley Hill. Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable- baselines3: Reliable reinforcement learning implementations, Journal of Machine Learning Research, 22 (268):1-8, 2021. URL. http: http: http::://mmmrr http://mmoorrrrr../ papers/ htapper///2////
1364 /2200///////2000136....
html.
Wenjie Qiu and He Zhu. Programmatic reinforeement learning without oracles. In International Conference on Learning Representations, 2022. URL http:://opeerrevieeee wwtp:/nttetoooooooddodotttoeeeee
Tuomas Haarnoja. Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforeement learning with a stochastic actor. CoRR, abs/1801.01290, 2018. URL http: //arxiv. wwtp://././/aaaaaae////ooossseat 012100190...........
Joshua Achiam. Spinning Up Deep Reinforcement Learning. 2018.
13

---

Appendix
Table of Contents
A GCRL-LTL Limitations
15
B Pseudo Code for Goal-Conditioned Reinforcement Learning
15
B.1 Pseudo Code for the Goal-Conditioned PPO Algorithm
15
Pseudo Code for the Goal-Conditioned Supervised Learning Algorithm
C Additional Related Work
16
C.I Goal-conditioned Reinforcement Learning
16
C.2 Reinforcement Learning Meets Logic and Specifications
17
D Demonstrations of the LTL. Tasks in Sec. 4
18
D.1 Avoidance Tasks
18
Avoiding More Tasks
................................
D.3 Goal Chaining Tasks.
E Demonstration w-LTL Tasks
20
E.1 w-Loop Tasks
20
E.2
w-Stability Tasks
20
F Demonstrations of the LTL Tasks on Ant 16-room Environments
20
F.1 Tasks: LTL Specifications
21
F22 Results.
22
F3 Ablation Study
23
G Implementation Details
24
G.1 Environment Details
24
G,2 Primitive Policies Details
26
Handling Transitions
27
G.4 Hyperparameters
28
14

---

A GCRL-LTL Limitations
The main limitation of our method is that we assume the atomic propositions in LTL properties can only be goals within the goal space of the underlying goal-conditioned policy e.g. colored zones in ZoneEnv navigation. We do not allow other sources of atomic propositions e.g. external environment signals that are out of the agent's control. For example, our current algorithm does not apply when the agent needs to pursue different tasks based on an external signal.
A potential solution to the aforementioned limitation is using a task monitor, which acts as an external memory, maintain record of completed sub-goals and past external environment signals. During task execution, when receiving new environmental signal, our task planning algorithm can dynamically revise the high-level path for the remaining sub-goals that the goal-conditioned agent needs to achieve. We leave it for future work.
The other limitations of GCRL-LTL include (I) the overapproximation of the true optimal probability by our task fask-planning algorithm for w-regular LTL properties by bounding w to a finite number in task-
Sec. 3.2; (2) dynamic handling of avoidance during test time instead of during planning planning algorithm does not consider the goal-conditioned agent's ' ability to stay safe before reaching sub-goal; (3) the lack of an alarm system for unsatisfiable task specifications. We experimented with unsatisfiable task specifications. For properties such as F(a A b), when the goal regions a and b close but not overlapping the agent's behavior mirrors that of GF A GF b, oscillating between and b. However, if these goal regions are far apart, our agent does not exhibit good-looking behavior.
B Pseudo Code for Goal-Conditioned Reinforcement Learning
B.1 Pseudo Code for the Cond-Cond PPO Algorithm
Algorithm illustrates the pseudocode for our goal-conditioned proximal policy optimization (PPO) algorithm. This algorithm builds upon the standard PPO algorithm (Schulman al. [2017]). Notable variations in the training process include the following: (1) when gathering experiences from the environment, is crucial synchronize the environment, goal representation, and the reward function; (2) an extended version of the value function V (s. g) and policy To To(s.g) g) is necessary, which take both an environment state and one of the goal representations g as inputs.
Including the goal as an input in goal-conditioned reinforcement learning algorithms enables the agent explicitly incorporate the desired objectives into its decision-making process and to learn policy that is explicitly aware of the desired goals. As such, the policy provides a mechanism for the desired outcome, allowing
the agent condition its behavior tailored to the specific goal at hand. When the goal is included as an input to the value function, it helps the agent estimate the value of being in particular state while aiming for specific goal. This assists in determining the quality or potential of state.
generate actions that
As discussed in the paper, leverage goal-conditioned RL agents to interact with low-level environ- ments to learn how to achieve basic goals without considering higher-level tasks. To solve an unseen LTL instruction, in the goal space to optimally achieve the sequences of tasks specified in the LTL objective. To this end, learn function V: G G R to estimate the capability of taking the goal-conditioned policy и to go from one goal to another goal on average. We regress V towards the value function of the a goal-conditioned agent by minimizing:
engage in high-level reasoning
the difficulty of achieving the specified goals
min (V(s.. 9k) (*).. where gu e L(88) A gi (st))
with T ~ B (a replay buffer), ~ {0... .. {maz), St, Ct, St-1 ~ T, j ~ {0,t), k ~ {t 1...tmaz! mox) and I. being given the goal labeling function. In Algorithm 1, we train V together with the goal-conditioned PPO algorithm.
B.2 Pseudo Code for the Goal-Conditioned Supervised I Learning Algorithm
Algorithm 2 extends goal-conditioned supervised learning (GCSL) ( (Ghosh et al. [2021]), following its iterative procedure sampling trajectories, relabeling them, and training a policy until convergence. It trains an agent to achieve specific goals in given environment. The primary enhancement
15

---

Algorithm Coal-Conditioned Proximal Policy Optimization Algorithm
Require:
Initial policy parameters Oo. initial value function parameters Φo. initial Q function param- eters 3, initial goal value function parameters w, goal-labeling function L: S G from state space S to goal space G, discount factor y, clip range
Ensure:
Goal-conditioned policy (s,,.g)
for k= 0, 2, NN do
D; 0 0
for m 0, 2. M do
Collect goal-conditioned trajectories
Sample Im 9. 80
D Tm (...,
9m: Im: ai, r.)...))
DE D Di
D Acquire trajectories by running policy Ty (1, = क (0x)
end for Compute rewards-to-go Rs
Compute advantage function Ag based on the current value function V Update the policy
min( (e(a Tg)
0 arg max
Σ Σ
n ag. f(e, n (8t: Tg. at)),
D TED 1-0
To, (atlst, Tg)
where Ty is the goal of rollout and f(c,A) =
(1+ (1- A <<0
A
D Update the Q function Q3
1
Bk+1 = arg min
min
Σ
(Qp(st (re Vox (8+11, (8t41,
D
reD 1=
D Update the goal value function V
T t-1 I
Wk+1 arg min
Σ (Voz (k)) Vo 9t) reDx O0
Σ ΣΣΣ
where Oh = L(8k). (18k).9. L(x)), and so is the initial state of r
Update the value function V
Σ [(Vo(s,,T)) f2,)2
ØK+1 arg min
D TED, 1=0
end for
involves organizing past goals into graph structure G based their reachability to improve agent exploration. This graph represents connections between goals, with nodes representing past goals and edges indicating that one goal can be reached from another. Our algorithm explicitly uses the goal value function ((50, 92) (which is learned together with the policy) to measure the capability of reaching a goal node 92 from goal node Ø1 from the viewpoint at an initial state Su-
Assume L is a goal-labeling function from state space to goal space G. Algorithm 2 works as follows. (1) Its samples goal from goal space G and an initial state from state space S. (2) collects a trajectory 7 = (sp, An, , 8c) to a goal node o' on G that is the closest node to (distances between goal nodes horizon. During this step, at each current state 8, finds the shortest past p from L(s) () to g', where P I(s), 9t-1 Ii-22---;5 and then calling the policy ((11),9++1) to reach the goal Ji-1- (3) It executes the current policy for T - steps in the environment to collect a trajectory 7 to reach the sampled goal g. (4) It concatenates 7 and 7 and relabels the trajectory to add new expert tuples (st.g g Sith Og, R¹) for h + h
measured by V) until either T.(st) g or exceeds the maximum
the training dataset. (5) It performs supervised learning on the entire dataset to update the goal value function V and the policy π via maximum likelihood.
C Additional Related Work
C.1 Goal-conditioned Reinforcement Learning
Goal-conditioned Reinforcement Learning(GCRL.) is popular topic that has been studied for long time in many previous works. characterize Goal- Augmented MDP, Schaul al. [2015] provides straightforward method that extends the standard value function to goal-conditioned value function,
16

---

Algorithm 2 GCSL with organizing past goals into a graph structure G
Require: Initial goal value function V(so,gl 91, 922). initial policy <(-1s.g)
Require: Maximal horizon T. discounted factor 7,, (unknown) environment transition relation P.
goal-labeling function L S + & from state space S to goal space G
Require: Goal graph G with nodes in G, edges E, and edge weight We for e E for k 3... do
Sample g ~G So ~ S
g' arg ming'ev Vx(So: 9'
Log a trajectory T (Su, ag: $1, ,1....,.7 8t) until L(st)= = - or t T with 8141 ~ P(ss, a:), a, ( where Ji+1 is the shortest path p from L(s;) to g' in G w.r. edge weight
W 01 = Va (#0,9) 91992) for any nodes 9l, 92 E G. and p= L(8:). : gi+l, 9i42, ...,-.
Log trajectory T' (81, 0t,00t;.... "ot......... ST) where 8i+1 ((s ac+1), 1,,, 0++1 Th (8,
7 = r @+
> Concatenate and r'
> Update goal graph G
For each state on T, add L(s;) to vertices V, add (L(s:), ((s--)) to edges E of G,
D, {(811== Sith, 0t, Ri)) t, h> O, 1,+ h T) with R.
- (r a(tk)
A=D
D4+1 DD
Vx+1 arg min E R (V [(8t).9) R₂)²
Update the goal value function
V
Tk-1 arg max B (r.gor.... [log (at st.9)]
>> Update the policy
end for
called universal value function approximation (UVFA). UVFA serves as basis in many following research works. How to define an appropriate reward is one of the basic challenges in GCRL. Some work reshapes the reward with the distance between the achieved goal and the desired goal but without any knowledge of the environment, i.c. Trott et al. [2019]. However, the local optimal policy it produces cannot finish many of the tasks in different environments. To solve long-horizon tasks, many planning methods on the abstract level above the robot control level are proposed. Nasiriany et al. [2019] introduced goal-conditioned value function to measure the reachability of the next sub-goal given the previous sub-goal by analyzing how close the goal-conditioned policy gets to the goal after specific number of time steps. Eysenbach et al. [2019] broke apart the task of reaching a distant goal into a sequence of way-points selected by learning distributional Q-value function which indicates how many steps the current state and goal away from one another. For the data as images, Thane-Sane et al. [2021] imagines possible sub-goals in a self-supervised fashion and uses them to facilitate training. By embedding goals into latent space that captures some notion of temporal distance between goals, Zhang et al. [2021] learns set of latent landmarks scattered across the goal space to enable scalable planning.
More generally, motivated by the fact that human learns from failure experience, Andrychowicz et al. [2018] provided a famous approach called Hindsight Experience Replay (HER), which can relabel the desired goals in the replay buffer with any reached goal within the same trajectory. Moreover, HER mitigates the sparse reward issue. In addition, many works try to extend the idea of HER. For instance, Rauber et al. [2019] demonstrates how hindsight can be introduced to policy gradient methods and generalize this idea successful class of reinforcement learning algorithms; Drawn intuition from the observation that any trajectory is a successful trial for reaching its final state, Ghosh al. [2021] proposed self-imitation algorithm named goal-conditioned supervised learning (GCSL). To enhance the diversity of relabeled goals, Zhu et al. [2021] develop based reinforcement learning approach with new relabeling strategy that relabels the goals by looking into the future with learned dynamics model.
C.2 Reinforcement Learning Meets Logic and Specifications
In recent years, instructing agents using LTL formulas has been studied in wide range of research works (Aksaray et al. [2016]. Littman et al. [2017], Sadigh et al. [2014], Hasanbeig et al. (2018), Cai et al. [2021], Hahn al. [2018], Camacho et al. [2019]). Among these approaches, retrieving information from and handling values in reinforcement learning is the mainstream implementation.
17

---

However, these Q-learning based approaches are not suitable for complex environment with continu- ous action space, until is extended by Hasanbeig et al. [2020]. The above methods typically analyze given L.TI. specification and then formulate a (usually sparse) reward function correspondingly. Then it could be used by any RI. algorithm to learn a policy. Specifically, Jothimurugan et al. [2020] designed and implemented a domain-specine decompose a complex task with sequences, disjunctions and (or) conjunctions of simpler sub-tasks, and can define the safety properties. Based on the above information, they construct a finite state machine named task monitor that generates shaped rewards. Icarte et al. [2018] build a model based on automaton called reward machines (RM). The R.Ss used to represent and decompose complex high-level LTL specifications, so that a curated RL algorithm called QRM may be applied to exploit the structure of the RMs. In their following work of Iearte et al. [2022], they propose hierarchical RI. algorithm called HRM that acquires policies using RMs. Besides research works focusing on classic single-agent RI. environments, there few recent works on RL with logic specifications in multi-agent RI. environments (Hammond et al. [2021]). D) Still, experiments show training RI. agents using classic RL algorithms without considering the formulation and semantics of LTL may lead to sub-optimal myopic policies (Vaezipoor et al. [2021]. Icarte et al. [2022]). To this end, policy sketches may be used in achieving the LTL formula, where sequence of sub-tasks is relatively easier to solve than a complex task as a whole. Andreas et al. [2017] 7] show that such sketches are useful when solving long-horizon horizon tasks. Sun al. [2020] and Zhao et al. [2021] show that injecting semantics to a programmatic agent can speed up learning for complex long-horizon tasks.
language for specifications called SPECRL. Users may
D Demonstrations of the LTL Tasks in Sec. 4
In this section, we provide a detailed explanation of the general format for each Linear Temporal Logic (L.TL) task presented in the paper. Additionally, we present specific examples of trajectories that illustrate how our method addresses a diverse range of challenging tasks across various environments. These trajectories serve as concrete demonstrations of our method's effectiveness in tackling these tasks.
D.1 Avoidance Tasks
The avoidance task follows general format represented as -aU(b (-cUd)). where a, b,b,,, c, correspond to propositions or goals relevant to task completion in our context. In Figures 10a and 10b, we showcase two trajectories generated by our trained agent solve a specific avoidance task: -yU(jA A (-wUr)). This task can be intuitively understood as a two-stage process: the agent needs to reach the "Jetblack" zone while avoiding the "Yellow" zone in the first stage, and subsequently reach the "Red" zone while avoiding the "White" zone in the second stage. Figures 10a and 10b serve as clear demonstrations of the agent's ability to reach the desired zones while never entering the prohibited zones.
D.2 Avoiding More Tasks
The avoiding more task follows general format represented as F(a A X(-bUc)) A G(-d), where a. b, d are task propositions or goals in our context. Figures 10c and 10d illustrate trajectories generated by our trained agent to solve an avoiding more task: F(j X(-yUr)) ^ G(-w). Similar to avoidance tasks, avoiding more tasks requires the agent to traverse sequence of zones in two stages while avoiding specific zones. The distinction is that avoiding more tasks require the agent to avoid one additional zone in the second stage, making it more challenging. Informally, the example can be interpreted as follows: in the first stage, the agent needs to reach the "Jetblack" zone while avoiding the "White" zone; in the second stage, the agent must reach the "Red" zone while avoiding the "White" and "Yellow" zones. The trajectories showcased in Figures 10c and 10d demonstrate the ability of our trained agent to effectively navigate through the required zones, avoiding the designated zones as specified by the avoiding more task.
From Figures 10a and 10c, we can observe how the presence of additional zones to avoid affects the trajectories, given identical initial states and sequences of goals (Jetblack and Red). Specifically, in the second stage of the avoidance task -yJU(a (-wUr)), the agent is expected to reach the Red zone while visiting a Yellow zone is not prohibited. However, in the second stage of the avoid more task F(J A X X(-UUr) G(-w), it is not allowed to visit any Yellow zone. In order to avoid the Yellow
18

---

(c)
(d)
Figure 10: Figures (a) and (b) depict trajectories that solve the avoidance task: Uyj(A (-wtrr). On the other hand, Figures (c) and (d) showcase trajectories that solve the avoiding more task: F(j A (.((((yU))) A G(-w). The initial positions of the robot are represented by orange diamonds The different colors of the zones, namely Red, Yellow, White, and Jetblack, correspond the task propositions y. j. respectively. It is important to note that the initial positions of the robot and the zones are randomized. The initial states of Figures (a) and (c) are the same, while the initial states of Figures (b) and (d) are identical.
zones the second stage of the avoid more task, the agent takes additional steps (as shown in Figure 10c) to bypass a Yellow zone and eventually reach a Red zone. Figures 10b and 10d demonstrate that identical trajectories can solve different LTL tasks. This occurs when the extra zones to avoid located far away from the robot throughout the entire execution, rendering impact the trajectories.
D.3
Goal Chaining Tasks.
The goal chaining task follows general format expressed F(a F(b F(c Fd)). where o, b, c, represent propositions goals that are relevant to task completion in our context. Figures 1 and 1lb display the trajectories for solving goal chaining tasks, specifically F(j F(w F(r Fy)). In this particular LTL task, the agent is required to navigate through zones with the colors Jetblack, White, Red, and Yellow in that specific order. The trajectories depicted in Figure demonstrate how our methods enable the robot smoothly and efficiently reach the desired zones in the prescribed order. These trajectories showcase that our trained agent can efficiently adjust the robot's state after completing sub-task and promptly proceed toward the next goal zone.
effectively
19

---

(b)
Figure 11: Figures (a) and (b) depict trajectories that solve the goal chaining task: F(j A F( F(r Fy)). The initial positions of the robot are represented by orange diamonds The different colors of the zones, namely Red, Yellow, White, and Jetblack, correspond to the task propositions r, w, j. respectively. It is important to note that the initial positions the robot and the zones are randomized.
E
Demonstration on w-LTL Tasks
E.1 w-Loop Tasks
An w-loop task, expressed in the form GF(a A XFb) G(-c), intuitively requires the agent to continuously loop between two specific zones, and while always avoiding another zone, c. For example, in the task GF(r A XFy) G(-w), the agent is expected to traverse between the Red and Yellow zones indefinitely, while never visiting any White zone. Figures 12a and 12b illustrate trajectories that solve this w-LTL task. In both trajectories, the robot quickly reaches the Red zone and subsequently oscillates between formula only requires the avoidance of While zones. Therefore, the trajectory shown in Figure 12b, which visits Jetblack zone, is still valid. Theoretically, to satisfy an w-L.T. task, our trained agent should run indefinitely if not falsified. However, in Figure 12, only plot trajectories for the first 1500 steps to demonstrate that our trained agent is capable of solving w-loop tasks.
Red and Yellow zones. is important to note that the LTL
F.2 w-Stability Tasks
An w-stability task requires the agent to satisfy a task proposition by reaching a goal region and re- maining the goal region infinitely. Figures 13a and 13b depict two trajectories that (approximately) satisfy the stability task: FGy. In both figures, the agent can eventually reach desired Yellow zone and then stabilize that zone. Since the stability task runs infinitely, we report the first 1500 steps to demonstrate that our agent is capable of stabilizing at zones of the specified color.
F
Demonstrations of the LTL Tasks on Ant 16-room Environments
We conduct experiments to assess the effectiveness of our approach to navigating an Ant through a challenging environment consisting of 16 rooms separated by thick walls. In this environment, each room has the same size 8 divided by walls and corridors with thickness (Fig. 16). There are two obstacles denoted by black squares in the environment. We place Mujoco (Todorov et al. [2012]) Ant robot in this environment for navigation. To solve the task, the ant should depart from the center of the bottom-left room reach the desired goal positions. The initial state of the ant is created with random noise, which can keep the position the ant around the center of the bottom-left room.
Here an atomic proposition G is in the form of (r, e) denoting the room in the r-th row and e-th column. The bottom-left corner room 0). Given an environment state 8, define = (r,c) true if the position of the Mujoco ant in close to the center of the (r, c)-th -th room within threshold.
20

---

Figure 12: Figures (a) and (b) illustrate trajectories that solve the w-oo task: GF(rA G(-w). The initial positions the robot are represented by orange diamonds The different colors of the zones, namely Red, Yellow, White, and Jetblack, correspond to the task propositions Y; j. respectively. is important to note that the initial positions the robot and the zones are randomized.
(a)
(b)
Figure 13: Figures (a) and (b) illustrate trajectories that solve the w-stability task: FGy. The initial positions of the robot are represented by orange diamonds The different colors of the zones, namely Red, Yellow, White, and Jetblack, correspond to the task propositions r y. w, j. respectively. is important to note that the initial positions of the robot and the zones are randomized.
Tasks: LTL Specifications
We evaluate our approach using five LTL specifications taken from DiRL Jothimurugan et [2021] denoted as Φ1 to Φs. These tasks have increasing levels of difficulty they require the agent to sequentially reach growing number of sub-goals. In order reach each sub-goal, the ant allowed maximum of 1000 steps to move within the environment. In Figure 16, the sub-goals are represented by colors, starting from blue and progressing respectively. The agent has the option to choose between two possible paths when transitioning from one sub-goat aabg to the next. For instance, in the most complex specification, the agent must depart from the blue point and sequentially reach the sub-goals at orange, yellow, green, and finally purple. The five specifications are described below:
orange, yellow, green, and purple for Φ1 to ds
F((0,2) 2) (2.0)).
21

---

It corresponds to reaching the center of either room (0,2) or room (2,0) in the Ant Grooms environment.
2 F(((0.2) (2.0)) A 2)).
After completing the task specified by Φ1, the ant should then proceed to reach the center of room (2,2) in the Ant16rooms environment.
Ø3 F(((0.2) (2, (( 2) F(((2,1) v (3, A F(3. 1))))
After completing the task specified by Φ2 the ant should then proceed to reach the center of room (3,1) in the Antl I 6rooms environment. The ant has the option to go through the center of either room (2, 1) or room (3,2) on its way to the target location.
04 F(((0.2) (2,0)) F( 2) F( 1) (3. 2)) F((3, 1) A((((L (3,3)) F),,
After successfully completing the task defined by dg. the ant's next objective is to reach the center of room (1.3) in the Ant Grooms environment. The ant has the choice to pass through the center of either room (1,1) or room (3,3) while making its way to the designated location.
ds == F(((O.2) (() (((2 ((3)) F(((1, 3((1,3) AF(((1,)) (0,3)) A F(O.
(3,3))
Upon completing the task specified by 64, the ant's subsequent goal is to reach the center of room (0.1) in the Ant 6rooms environment. The ant has the option to traverse through the center of either room (1.1) or room (0,3) as moves towards the target location.
Additionally, to demonstrate the generalization capability of our approach, we incorporate two additional specifications, namely óe and Φ7, which were not included in the original study by DiRL ( Jothimurugan et al. [2021]). Furthermore, we introduce an w-regular LTL specification, denoted as dy. which is not supported by DiRL.
Og ((()2)) (0. 1)) F(((211) = F((12) F(( (1.3)) F(3,3) ((3.3))))))-
It corresponds to the following sequence of sub tasks: First, reaching the center of room (2,1) by passing through either room (2.0) or room (0,1). Next, reaching the center of room
(1,2) by passing through either room (2,1) or room (1,1). Finally, reaching the center of room (3,3) by passing through either room (3,2) or room (1,3).
o F(((0) v (0, 2( A F(((2.1) (1.2)) F((1, A F(((O) 1) v (1,3)) F 3).,))))))
It corresponds to the following sequence of sub tasks: First, reaching the center of room (2,2) by passing through either room (2,0) or room (0,2). Next, reaching the center room
(1,1) by passing through either room (2,1) or room (1,2). Finally, reaching the center of room (3.3) by passing through either room (3.1) or room (1,3).
dg == F(((2,0) v (0, 2)) A GF, 2) ^ x(F((2,1) A XF(1,)))))
It corresponds to the following sequence of sub tasks: First, reaching the center of room (2,2) by passing through either room (2,0) or room (0.2). Then, taking an infinite loop from room (2,2) room (2,1) + room (1,1) + room (1,2) - room (2,2)...
F2 Results.
We also compare our approach with DiRL (Jothimurugan al. [2021]), which is state-of-the-ar LTL-satisfying RL algorithm. Similar to ours, DiRL leverages the compositional structure of a task specification enable learning. However, there are some differences between our approach and DiRL. In DiRL, a unique low-level policy is learned for each sub-goal transition, and high-level policy plans over the sub-goal transition space by evaluating the quality of the various low-level policies. One limitation of DiRL is that it is restricted to small fragment of LTL. Particularly, it cannot handle w-regular LTL properties that involve infinite state sequences, as not possible to learn unique low-level policy for each transition in an infinite sequence. Additionally, DiRL not applicable to multi-task RL scenarios because the low-level policies are specific to a single environment setting and do not generalize across different environments.
22

---

Methods
DiRL
DiRL+ GCSL
Ours
Ablation
@
0.910 (0.022)
0.923 (0.082)
0.967 (0.006)
0.722 (0.073)
@2
0.770 (0.083)
0,953 (0.037)
0.925 (0.049)
0.713 (0.046)
0.367 (0.147)
0.967 (0.017)
0.935 (0.028)
0.667 (0.039)
@4
0.183 (0.046)
0.937 (0.031)
0.875 (0.041)
0.593 (0.086)
0.043 (0.061)
0.913 (0.017)
0.868 (0.038)
0.533 (0.083)
(1G
0.857 (0.004)
0.565 (0.045)
0.882 (0.018)
0.617 (0.043)
0.903 (0.045)
0.655 (0.039)
Table 2: The success rate of the LTL specifications Φ1 Øs on Anoo6rooms. The success rates shown are the average values obtained from three individual training experiments (for each training experiment, we evaluate the final trained agent against a specification 200 times) Since DiRL and GCRL cannot be applied to multi-task RL, we train a separate agent for each of the LTL specifications Φ1 to Φ5 using 3e6 environment steps. In contrast, our algorithm trains a single goal- conditioned agent using Algorithm 2 via 3e6 environment steps and evaluates this agent over all eight LTL specifications
In our experiment, we consider both DiRL and DiRL+GCSL as our baselines. DiRL uses the Augmented Random Search (ARS) algorithm (Mania al. [2018]) 8)) to learn the low-level policy for each sub-goal transition. DiRL+GCSL, the other hand, replaces the ARS learning algorithm with our extended GCSL algorithm (shown Algorithm 2) with a fixed sub-goal for learning each low-level sub-goal transition policy. This allows for a fair comparison as our method is based on this learning algorithm. Since DiRL and DiRL+GCSL cannot be applied to multi-task RL, we train a separate agent for each of the LTL specifications d1 to ds using 3e6 environment steps. In contrast, our algorithm trains a single coal-conditioned agent using Algorithm via 3c6 environment steps and evaluates this agent over all five LTL specifications.
Table 2 presents the success rates of the baseline approaches DiRL, DiRL+GCSL, and Our approach on all the LTL specifications. The success rates shown are the average values obtained from three individual training experiments (for each training experiment, we evaluate the final trained agent against a specification 200 times). As the complexity of the specifications increases, the performance of DiRL gradually deteriorates, while the other baseline approach, DiRL+GCSL, maintains stable success rate acToss all LTL specifications (from Φ1 to Φg)). Our goal-conditioned agent achieves comparable performance to DCRL+GCSL, despite using significantly fewer samples to solve these LTL tasks (see the explanation above). In addition, our approach demonstrates immediate high success rates on the two additional LTL specifications, Øb and Φ7, without the need for additional training. In contrast, the DiRL baselines require retraining from scratch for these additional tasks. This showcases the capability of our technique to use a simple goal-com condiiondd RL agent to follow arbitrary LTL specifications without additional training over the LTL task space. Unlike the DiRL baselines, which are designed for LTL specifications expressible as regular expressions, our technique is not limited to regular expressions and handle more complex w-regular expressions. This is demonstrated by the success rate of our agents on the w (loop) specification dys, where the agent is evaluated based on its ability to complete the loop twice. To further illustrate the performance of our approach, we provide examples of evaluation rollouts for specifications ranging from Φ1 to ds in Figure 14.
F33 Ablation Study
Random path selection. Recall that our algorithm uses the goal value function V* 91, 92) to measure the capability of reaching goal 92 from goal Φ1 from the viewpoint of the agent at an initial state sg. This information is crucial for performing path planning over the graph representation of Büchi automaton, enabling the optimal execution of the sequence of tasks defined in an LTL instruction. In this ablation study, we investigate the importance of path planning in our algorithm. We create an ablated version of our approach where acceptable paths are randomly generated from the Büchi automaton of an LTL specification, and the goal-conditioned agent executes towards the goals along these randomly selected paths. The success rates for the ablated version of our algorithm across all specifications are presented in the last column of Table 2, and the example trajectories of the agent for Φ to ós in this ablated setting are depicted in Figure 15. Our experiment reveals that without the path planning guided by the goal value function V. the performance in satisfying specifications Φ1 to
23

---

+
+
(a) Example (1
(b) Example of (22
(c) Example Φb
+
(d) Example d4
(e) Example of ds
(f) Example of de
+++
(g) Example of ΦT
(h) Example of ds
Figure 14: Figures (a) (e) depict examples of agent trajectories for each specification from di to Φs. these figures, the * symbol represents the final goal position required by the respective specifications. Notably, for ós. which is an w-regular LTL specification involving infinite state sequences, there is no final goal for this specification.
é8 significantly deteriorates. This decline can be attributed to the randomly selected paths sometimes crossing obstacles in certain rooms, making challenging for the Mujoco ant to navigate through them. By comparing Figure 14 (which showcases 15, we observe that our algorithm's ability to select obstacle-fre paths (thanks to the goal value function V) significantly improves the agent's capacity to satisfy the given specifications.
full algorithm with path planning) with Figure
G Implementation Details
G.1 Environment Details
ZoneFnv. The ZoneEnv environment is derived from OpenAl's Safety Gym (Ray et [2019]). and it features continuous action and observation space. The square-shaped walled environment

---

++*
(a) Example of Φ1 with random  segueence of sub-goals
(b) Example of Øz with random S sequence of sub-goals
(c) Example of és with randoni sequence sub-goals
+
(d) Exxampil of di with random Requerin sub-goals
(e) Example of és with random (f) Example of ée with random sequence of sub-goals
sequer
sequence sub-goals
+++
++
+
(g) Example of Φ7 with random (h) Example of Φss with random sequence of sub-goals
sequence of sub-goals
trajecttoon
Figure 15: The examples of failed trajectories of each specification for the abated version of our algoriins In these figures, the * symbol represents the final goal position required by the respective specifications. Randomly selected paths sometimes cross obstacles in certain rooms, making aaaaeaali
c challenging for the Mujoco ant to navigate through them.
has zones (2 of each color). The colors correspond to the task propositions. use a simple robot from Safety Gym called Point, with one actuator for turning and another for moving forward or backward. An agcntt can observe the LiDAR information of its surrounding zones. Given this indirect geographical information, it has to visit and/or avoid certain zones to satisfy sampled LTL task gelcctionss. To acquire agents to generalize to any task, the initial positions of zones and the robot are random in every episode. Within this environment, the robot has the ability to perceive its own state, including factors such as velocity, acceleration, and LiDAR information. The observation comppisse compen four distinct groups of LiDAR information, each corresponding to specific color.
corressploys
To capuure LiDAR information for each color, the environment employs a set of 16 hypothetical light bins emitted from the robot. These bins are evenly distributed, with intervals of 30 degrees between them. Each bin capable of detecting the presence a desired color zone its direction returns memmalizeed distance value indicating the proximity of the zone. The returned distance values range
25

---

from O to I, with lower values indicating closer zones, 0 denoting overlap between the agent and specific color zone, satisfying the corresponding proposition, and indicating the absence of desired zone in that direction. In cases where a bin can intersect with two zones simultaneously. the returned value is determined by the zone that closer to the robot. The state representation in the ZoneEnv environment employs a 76-dimensional vector, consisting of 12 dimensions for the robot and 64 dimensions for the LiDAR information (16 dimensions per color).
In this environment, the goal-labeling function L acts as an event detector, providing truth assign- ment for all propositions related to the four colors G j. w. r, r.y. The goal-labeling function triggers when the propositions in G hold true in the environment. For example, r L(s) if and only if the agent is located on top of red zone at specific environment state
Ant-16roons This environment with continuous observation and action space is adapted from the 16 rooms environment from Jothimurugan et al. [2021]. J. In this walled environment with rooms, each room has the same size 8 8 divided by walls and corridors with thickness (Fig. 16). There are two obstacles denoted by black squares in the environment. We place Mujoco (Todorov et al. [2012]) Ant robot in this environment for navi- gation. To solve the task, the should depart from the center of the bottom-left room to reach the desired goal positions. The initial state of the ant created with random noise, which can keep the position of the ant around the center of the bottom-left room.
Figure 16: Ant 16 rooms
LetterEnv. The LetterEnv is grid-based environment with a size of 7 x 7, featuring discrete action and observation spaces. Within this environment, the agent has a complete view of the grid, including its own position. Specifically, for each type of letter, there is a 7 7 matrix that contains multiple integers. A value of 0 in a grid cell indicates that the letter is not present that position, while a value of denotes the presence of letter instance. addition to these 12 matrices representing the letters, there is additional matrix indicating the position of the agent. By considering both the letter positions and the agent's 's position, the goal-labeling function can determine which task propositions are satisfied unsatisfied each step.
G.2 Primitive Policies Details
Dynamic Primitives of ZoncEnv. order to obtain a discrete action space for the Point robot in Safety Gym (Ray et al. [2019]), we trained set of four dynamic primitives in the ZoneEnv environment using reinforcement learning. Each dynamic primitive was trained for 0.5 million steps. These four dynamic primitives responsible for guiding the robot move in the cardinal directions of UP, DOWN, LEFT, and RIGHT respectively. The reward function used to train these primitives is defined as follows:
Oper 1Uperl
Zzne Udirection
where Udirection is the velocity of a given direction, and Uper denotes the velocity of the direction that is perpendicular to the given direction. In order to train the UP and DOWN primitives, Udirection = tracks velocities on æ.r-axis; similarly, to train the LEFT and RIGHT policies, we set Udirention 1 to keep track of velocities along +y-axis. Coefficients ca, Gper are set to be and 0.05, respectively. All dynamic primitives for the ZoneEnv environment were trained using the PPO algorithm (Schulman al. [2017]) implemented in the
RL framework (Raffin et al. [2021]).
Dynamic Primitives of Ant. For the MuJoCo ant, follow Qiu and Zhu [2022] and train of four basic primitive policies, i.e., UP, DOWN, LEFT and RIGHT for million steps for each. The reward function to acquire the above four primitives is defined as:
Tant Cy Udirection Ch. ((Isccalthy) ca |aal22 cs - floottactl2
(8)
26

---

where edirection is the velocity of given direction. I r(IsHealthy) is a Boolean function that de- termines the health condition of the agent, action a is an 8-dimension vector, and feontact a vector that encodes the contact force of the agent. In order to train the UP and DOWN primitives, Udirection = i/ tracks velocities on #7-axis; similarly, to train LEFT and RIGHT policies, we set Edirection , to keep track of velocities along +y-axis. Coefficients Cu. Ch. Ca and of are set to be 1, 1, 0.5, 5 10"*, respectively. All dynamic primitives for the MuloCo ant are trained using the Soft Actor-Critic algorithm (Haarnoja al. [2018]) implemented in the OpenAl Spinning Up RL framework (Achiam [2018)).
Training a Goal-Conditioned agent for ZoneEnv. We employ the goal-conditioned Proximal Policy Optimization (PPO) algorithm, shown in Algorithm to train condiioond agent that can satisfy all task propositions (goals) in the ZoneEnv environment, which involves reaching zones of different colors. For each color (Yellow, Red, White, and Jetblack), we vector of 24 dimensions as the goal representation. During training, we sample the goal colors and correspondingly adapt the reward function and the goal representation of the ZoneEnv environment. is crucial to ensure the synchronization of these elements within each episode. For instance, when instructing the agent to reach Red zone, we use the reward function to detect the proposition and exclusively utilize the appropriate goal representation for Red. To achieve a balanced agent that can successfully reach zones of all colors with equal rates, we sample the goal colors uniformly. The reward function for acquiring the goal-conditioned agent is defined as follows:
random
1,
satisfied
Toolor 0, unsatisfied
where color denotes a goal (i.e., one of r y, j) that the agent must reach an episode. We employ sparse reward function that only provides a reward of 1 when the desired color is satisfied, while all other situations receive a reward of zero. We do not penalize the agent for stepping into zones of different colors. Our focus is solely on whether the agent can effectively and efficiently reach the desired color.
Training Goal-Conditioned agent for LetterEnv. We utilize the coal-conditioned Proximal Policy Optimization (PPO) algorithm, as shown in Algorithm 1, to train a goal-conditioned agent capable of satisfying all task propositions (i.e., reaching all letters) in the LetterEnv environment. To represent each letter as a goal, we employ a random matrix with a size of 7 x 7. The training process for the goal-conditioned agent follows the same methodology as in the ZoneEnv environment to ensure synchronization among goals, reward functions, and goal representations in each episode. The reward function for acquiring the goal-reaching primitive defined as follows:
Tletter = { 0, unsatisfied
1, satisfied
(10)
where letter denotes one of the goal letter that the agent must reach. We employ sparse reward function that provides a reward of if the desired goal is achieved and otherwise.
Training Coal-Conditioned agent for Ant 16 rooms. We apply the goal-conditioned supervised learning algorithm described in Algorithm 2 to train a goal-conditioned agent that can navigate in the Ant16rooms environment. The reward function is defined follows:
Fg {
1. goal reached
(11)
0. goal not reached
where g is a randomly sampled goal in the goal space.
G.3 Handling Transitions
In our graph representation Gg a Büchi automaton B, a "selff-ransition"" on a node q describes the goal-related constraint v/' that must be maintained until the agent can transition to neighbor node of q with the underlying goal-conditioned policy и. If g is on the planned optimal path, the agent for B needs to use π to simultancously ensure yi while transitioning to the target region. In the paper,
27

---

primarily focus on reach avoidance, where < A -9k encodes regions in the goal space to avoid. At a current environment state s, when the value function V (s 9k) greater than threshold, we take a safe action arg min, Q" Is,0) that moves the agent away from the most dangerous zone 9k- Similarly, our strategy applies to cases where v/ Au Il encodes goal regions that the agent must stay within before transitioning out from g. In such cases, if the value function V (8, 9k. ) is less than a threshold, we could take an action arg max, Q* (s, 9k a) that encourages the agent to remain in ge. As our navigation benchmarks do not support the evaluation of this feature, we plan to explore it in our future work.
In the paper, we restrict the target region for transition as v 95 Our tool supports more diverse target regions in the form of &
A 9j ^ -9: handle tasks such as Fgi A A92-- The strategy is to reuse our avoidance strategy to avoid Ø2 when the agent is deemed close to the goal region 91 i.e. the value function out- put V* (*(s, 91) is above the threshold a. Fig. 17 presents example to solve tasks in the form of Fg1 A -92-
In the handling avoidance in ZoneEnv and LetterEnv, finding appropriate value thresh- olds to define dangerous is quite necessary. As we discussed in Sec. G.2, we use sparse reward functions that only yield O or 1 in the training process, so the expected threshold to be deemed as dangerous should be located somewhere close to (but less than) 1. We perform experiments to study success rates given different value thresholds for both environments. The results are summarized in Table 3. From the table, we can see that a relatively smaller works better with ZoneEnv, while larger value threshold tends to be a suitable choice for LetterEnv. According to the results, we set the 0.85 for ZoneEnv, and 0.92 for LetterEnv.
(a) F(j AT)
(b) F(J -r)
Figure 17: Fig (a) and (b) show our capability to handle overlapping goal regions. In (b), the agent takes a detour to avoid touching the red zone.
Value threshold
Environment
0=0.80
0=0.85
0=0.87
a=0.90
g=0.92
o=0.95
ZoneEnv
0.912
0.958
0.941
0.932
0.902
0.878
LetterEnv
0.635
0.788
0.812
0.804
0.845
0.820
Table 3: Performance of trained agents on avoidance tasks with different value thresholds a. We report the success rates averaged over 1000 episodes.
G.4 Hyperparameters
The following hyperparameters used train the dynamic primitive policies for ZoneEnv with PPO (Schulman et al. [2017]).
Discount factor = 0.998.
SGD optimizer; actor learning rate 0.001; critic learning rate 0.001.
Mini-batch size n 256.
The following hyperparameters are used to train the dynamic primitive policies for LetterEnv with PPO.
Discount factor y 0.94.
SGD optimizer; actor learning rate 0.001; critic learning rate 0.001.
Mini-batch size n 256.
The following hyperparameters are used train the goal-conditioned agent for ZoneEny with the goal-conditioned PPO algorithm shown in Algorithm 1.
28

---

Discount factor 0.998.
SGD optimizer; actor learning rate 0.0003; critic learning rate 0.0003.
Mini-batch size n 1000.
The following hyperparameters are used to train the goal-conditioned agent for LetterEnv with the goal-conditioned PPO algorithm shown in Algorithm 1.
Discount factor 0.94.
Adam optimizer; actor learning rate 0.001; critic learning rate 0.001.
Mini-batch size n 256.
The following hyperparameters are used train the dynamic primitive policies for Ant 16 rooms with the SAC (Haarnoja et al. [2018]) algorithm.
Discount factor = 0.99.
SGD optimizer; actor learning rate 0.001; critic learning rate 0.001.
Mini-batch size 100.
Replay buffer size 100000.
Soft update targets 0.005.
Target update interval and gradient step are set to be 1.
The following hyperparameters are used to train the goal value function V and policy with our extended goal-conditioned iterative supervised learning algorithm shown in Algorithm 2.
For goal value function V
Discount factor 7 0.99.
Adam optimizer; learning rate 0.001.
Mini-batch size 100.
For policy
Adam optimizer; learning rate 0.0005.
Replay buffer size 20000000.
Mini-batch size 512.
For all training with PPO algorithm, of iterations when optimizing the surrogate loss to be 10.
GAE À = 0.97, clip range 0.2, and we set the number
Table 4 summarizes the neural network architectures used by reinforcement learning algorithms. All neural networks are multi-layer foed-forward neural networks.
Policies
Environment
Hidden Units
PPO dynamic
ZoenEnv
(64, 64)
PPO dynamic
LetterEnv
(64, 64)
PPO geal-ing
ZoneEnv
(512, 1024, 256)
PPO goal-reaching
LetterEnv
(256. 512, 128)
SAC dynamic
Ant
(256, 256)
Goal--onitioned value
Ant16rooms
(256, 256,256)
GCSL
Ant16rooms
(256, 256,256)
Table 4: Neural
Network Structures.
29


Reviews:
[{"review_id": "0Ix1cpxwi2", "reviewer": "Reviewer_VFCf", "summary": "This paper considers the problem of learning to solve a linear temporal logic\n(LTL) tasks in a Markov Decision Process (MDP). Given a fixed Markov Decision\nProcess, this is done by:\n\n1. Pre-training a goal-conditioned policy to solve a uniform sampling of reach-avoid tasks,\n   where goals correspond to atomic propositions.\n1. The input LTL sentence is translated into a Buchi automata.\n1. The Buchi automata is transformed into a weighted graph.\n   - Weights are determined using the value function of the pre-trained policy.\n1. A path is generated by solving a sequence of shortest path problems.\n\nThe approach is then experimentally validated against the LTL2Action method using \nthe prior works domain and concept class.\n\n\n---- update ----\n\nAfter re-reading and being pointed to Appendix section D, it seems my major concerns are accounted for. What remains is the question of how to incorporate this into the main text. As such I am increasing my score to erring toward accept.", "questions": "1. How does the system generalize to infinite horizon queries?\n1. When is the proposed heuristic guaranteed to work vs have arbitrary failures.", "limitations": "See weakness 1.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The approach tackles an important problem. Namely, learning to solve sparse\ntasks represented in a formal specification language defined over infinite runs\nof the system.", "weaknesses": "1. The proposed approach is ultimately heuristic and is susceptible to being\n   \"catastrophically myopic.\" In particular, the greedy sequence of shortest\n   path problems is necessarily biased toward solutions that work for finite\n   horizons, but says nothing about the infinite time behavior, e.g., the \"lassos\"\n   generated by sequence of shortest path queries. It is not hard to imagine\n   constructing an adversarial Buchi automata that uses a sequence of easy\n   to reach accepting states to lead the agent into a long term bad position.\n\n1. The paper claims to address infinite horizon specifications, but then\n   compares against a regular language benchmark. This undercuts the stated\n   motivation. For example, all of the base-line problems have a finite\n   accepting prefix, e.g., as opposed to G(x -> F y).\n\n1. The approach should be compared to hierarchical, meta RL, and compositional\n   RL works. For example, the graph approach seems very similar to [1] but adapted\n   to goal conditioned policies.\n   \n[1] Jothimurugan, Kishor, Rajeev Alur, and Osbert Bastani. \"A composable specification language for reinforcement learning tasks.\" Advances in Neural Information Processing Systems 32 (2019).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful feedback and constructive comments! We present our response to each of your concerns and questions below.\n\n**R1. The proposed approach is ultimately heuristic and is susceptible to being \"catastrophically myopic.\" In particular, the greedy sequence of shortest path problems is necessarily biased toward solutions that work for finite horizons, but says nothing about the infinite time behavior, e.g., the \"lassos\" generated by sequence of shortest path queries.**\n\nAs illustrated in the global rebuttal, our task planning algorithm considers both the shortest path $p$ to an accepting state and the shortest cycle $q$ from the accepting state. Please see Fig (j) and (k) in the global rebuttal as an example. For a complex LTL property $\\varphi_1 \\vee \\varphi_2$ for Ant 16-room navigation in Fig (j), our algorithm picks $\\varphi_2$ for the goal-conditioned agent to execute in Fig (k) as it deems $\\varphi_1$ more costly although the ``lassos\" in $\\varphi_1$ is closer to the agent's initial position. We acknowledge that using a bounded $\\omega$ overapproximates the true probability for optimal path selection $pq^\\omega$, which is a limitation. However, we have the flexibility to use arbitrarily large $\\omega$ without incurring additional costs in planning. \n\n**R2. When is the proposed heuristic guaranteed to work vs have arbitrary failures?**\n\nOur task planning technique for temporal properties is based on a goal-conditioned agent trained for reachability properties. For an $\\omega$-regular LTL property, while our technique has the flexibility to use arbitrarily large $\\omega$ in planning a path for LTL-satisfying runs, it can lead to good-looking bad policies, which induce trajectories that eventually fail to reach the desired accepting state but along the way visited the accepting state arbitrarily many times (potentially prolonging until the heat death of the universe).\n\n**R3. The paper claims to address infinite horizon specifications, but then compares against a regular language benchmark. This undercuts the stated motivation**\n\nWe included experimental results of evaluating our algorithm against $\\omega$-regular LTL specifications in line 663, Sec. D of the supplementary material (as well as Fig. 14d) which is referred to in the submitted paper. We will incorporate these important experimental results in the main body of the revised paper. Please also see the additional evaluation results in Fig. 8 of the global rebuttal.\n\n**R4. The approach should be compared to hierarchical, meta RL, and compositional RL works.**\n\nWe compared our work with DiRL [1], a state-of-the-art compositional RL algorithm for LTL properties. We used DiRL instead of SpecRL [2] as suggested by the reviewer because DiRL is a stronger baseline and empirically outperforms SpecRL on our benchmarks. **The experiments and results were illustrated in line 689, Sec. E of the supplementary material.**\n\nThe comparison is conducted on the Ant 16-room environment. The agent needs to navigate a Mujoco Ant in 16 rooms separated by thick walls (Fig. 3). We use 8 LTL specifications (line 700 Sec E.1) including 5 properties taken from DiRL. These tasks have increasing levels of difficulty as they require the agent to sequentially reach a growing number of sub-goals.\n\nSimilar to ours, DiRL leverages the compositional structure of a task specification to enable learning. However, there are some key differences. First, in DiRL, a unique low-level policy is learned for each sub-goal transition. Second, DiRL does not support $\\omega$-regular LTL properties. Lastly, DiRL is not applicable to multi-task RL scenarios because the low-level policies are specific to a single environment setting and do not generalize across different environments. As a result, we trained a separate agent for each of the LTL specifications for DiRL. In contrast, our algorithm trains a single goal-conditioned agent and evaluates this agent over all 8 LTL specifications.\n\nThe results in Sec E.2 show that our agent is able to satisfy all specifications with ~90% success rate trained using 3e6 environment steps, whereas the DiRL method has to exercise 3e6 timesteps for each of the specifications to match the success rate of our approach. Our approach demonstrates immediate high success rates on arbitrarily new LTL specifications without the need for additional training. In contrast, DiRL requires retraining from scratch for new tasks. More comprehensive evaluation results are in Sec E.2 and E.3.\n\nWe also compared our approach with a state-of-the-art hierarchical RL algorithm, R-AVI [3]. We used the abstract graph of an LTL specification as input to R-AVI. We found that R-AVI does not scale to the complex LTL specifications for Ant 16-room navigation and can only achieve less than ~40% success rate for all of them when trained using 3e6 environment steps. \n\nWe did not compare our approach with DiRL and R-AVI using the colored ZoneEnv environment because this is a multi-task benchmark, which is out of the capability of the learning algorithm in DiRL and R-AVI. \n\nWe will move the comparison with DiRL and R-AVI to the main paper in a revised version.\n\n[1] Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. \"Compositional reinforcement learning\n990 from logical specifications.\" Advances in Neural Information Processing Systems 34 (2021).\n\n[2] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. \"A composable specification language for reinforcement learning tasks.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[3] Kishor Jothimurugan, Osbert Bastani, and Rajeev Alur. Abstract value iteration for hierarchical reinforcement learning. International Conference on Artificial Intelligence and Statistics (2021). \n\n**R5. How does the system generalize to infinite horizon queries?**\n\nPlease see R1 and the global rebuttal."}, {"review_id": "1aqiGXON3M", "reviewer": "Reviewer_Q7B2", "summary": "This paper presents a method to transfer learned or planned goal-directed skills in domains to novel tasks represented by linear temporal logic within the same domain. The key idea of this paper is to train goal conditioned policies to achieve (and avoid) Boolean goals, and to compose them temporally to achieve temporal logic goals. \n\nThe paper proposes to first convert the automaton corresponding to the LTL specification into a Buchi automaton, which is then converted into a directed graph with a target state. The algorithm also estimates the cost-to-go heuristic at each node to estimate edge traversal costs, and finally combines an optimal graph search along with learned goal conditioned policies to achieve the temporal logic goals. \n\nThe authors primarily benchmark against LTL2Action where the specification is embedded into a feature vector using a graph neural network, and this embedded latent feature vector is used alongside a state-feature vector in a through a Deep-RL algorithm to compute the final policy. The authors demonstrate that their approach beats LTL2Action on range of randomly sampled tasks, and two specific avoidance tasks.  ", "questions": "These questions pertain to the limitations of the approach proposed, please clarify if your approach can handle it, or update the limitations to include them:\n1. Can this approach handle simultaneity? for example ensure goals $a$ and $b$ are true at the same time instant as in $\\diamond (a \\wedge b)$\n2. Can this approach handle self transition that requires maintaining some proposition as true until a goal is reached? For example $\\diamond b \\wedge a U b$\n3. Can the graph search be adopted for recurrence type formulas from Manna and Pnueli's temporal hierarchy [4] (TLDR https://spot.lre.epita.fr/hierarchy.html) $\\square \\diamond a \\wedge \\square \\diamond b$\n4. What are the implicit assumptions you are making on the environment for the validity of the proposed approach? Please clarify these explicitly\n\n[4] - Manna, Z. and Pnueli, A., 1990, August. A hierarchy of temporal properties (invited paper, 1989). In Proceedings of the ninth annual ACM symposium on Principles of distributed computing (pp. 377-410).", "limitations": "I do not believe that the limitations are adequately identified and acknowledged. Please refer to the weakness and questions section.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "**Sound problem definition**: The authors are correct in their statement that with competent goal-conditioned policies available to the agent, the agent can solve temporal LTL tasks through composition of these policies. There has been a lot of recent interest in this approach, and the authors have demonstrated that in two navigational environments that have been utilized in research on RL + temporal goals. There are however some issues with the assumptions made by the authors as I describe in the following sections.\n\n**Evaluations**: The authors might have chosen just two navigational domains, but have focused on evaluating over a wide range of temporal logic formulas. Such evaluations are much more valuable in the space of RL for temporal tasks as is considered in this paper.\n\n**Originality and significance**: Prior work suffers from lack of transferrability to all novel tasks as the library of learned skills is inadequate to transfer to all possible tasks. The authors propose to pre-train a goal conditioned skills that should offer more coverage of the logical transition-space. The idea is well demonstrated in the zones and letters environment in the paper, but there are some additional concerns that I highlight in the next section.\n\nOverall, the idea of composing pre-learned skills to novel task scenarios is not original in and of itself. But the combination presented in this paper is novel to the best of my knowledge. However, there are elements of similarity with prior work that have not been addressed adequately ", "weaknesses": "**Positioning in context of prior work**: The core idea of skill reuse is not entirely novel. There are prior works addressing this [1],[2],[3] that appear to be missing from discussion. Infact both these works handle a wider variety of logical composition for the transition edges which appear to not be considered by this paper. While the core idea in this paper is distinct, it deserves to be discussed in context of these works that appear to handle the problem with greater generality.\n\n**Correctness concerns**: The authors claim that their approach is applicable to all $\\omega$-regular automata. However their approach appears to have a strong reliance on a single unique accepting state, in all the examples that they test on. Generalized Buchi acceptance condition requires that the system visit atleast one state in each accepting set infinitely often, and the approach described here is incompatible with such a specification. An example of this would be the patrolling task $\\square \\diamond a \\wedge \\square \\diamond b$. Here an accepting run would require the agent to visit both $a$, and $b$ infinitely often, but this would not be discoverable by the graph search algorithm described here.\n\nA second correctness concern relates to the type of edge transitions that can be accomplished by the goal conditioned policy. In general an edge transition in automata is described by the self-transition edge that is maintained until the transition trigerring truth evaluation is reached. The goal conditioned policy implicitly assumes that the trigger transition is reached as the first distinct transition in the truth values of the propositions. This might be true for navigational tasks, where each state has at most one proposition true, but may not be true in general when not all propositions are controlled by the agent, or even in cases where simultaneous satisfaction of multiple propositions might be required. For instance the specification $\\diamond(a \\wedge b)$. [2] would appropriately identify this specification as unsatisfiable, and abort task execution, whereas the behavior of the system proposed in this paper is uncertain. In particular, none of the goal conditioned policies are applicable to this outcome. In contrast [1] can compose the policies logically to satisfy the specification if it is indeed satisfiable. If we study the type of transitions occuring within automata, then there are many such edge cases pertaining to self-transition, and simultaneous truth value changes that cannot be handled by this approach. These limitations must be explicitly acknowledged in the submission.\n\n**Difficulty of training goal-conditioned policies**: This approach relies on having a good goal conditioned policy to perform the task. However, this is in general a challenging problem, and I am not aware of any works that have managed to train competent goal conditioned policies beyond grid world domains that achieve good coverage over all possible logical goals. I would appreciate if the authors add some text to evaluate the quality of goal conditioned policies before using them for this algorithm, or point to works that address this issue.\n\n[1] - Nangue Tasse, G., James, S. and Rosman, B., 2020. A boolean task algebra for reinforcement learning. Advances in Neural Information Processing Systems, 33, pp.9497-9507.\n\n[2] - Liu, J.X., Shah, A., Rosen, E., Konidaris, G. and Tellex, S., 2022. Skill transfer for temporally-extended task specifications. arXiv preprint arXiv:2206.05096.\n\n[3] - Xu, D. and Fekri, F., 2022. Generalizing LTL Instructions via Future Dependent Options. arXiv preprint arXiv:2212.04576.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful feedback and constructive comments! \n\n**R1. Positioning in context of prior work**\n\nWe appreciate your suggestion to discuss the related work [1,2,3]. In particular, we will credit [1] for inspiring our approach to managing the logical composition of value functions. Briefly, our method differs by supporting $\\omega$-regular LTL properties, which are not immediately applicable in these prior works. Our approach provides equivalent expressivity in terms of logical composition for the transition edges compared to these prior works. Please refer to responses R3-R6 below.\n\n**R2. Single Unique Accepting State** \n- \"However their approach appears to have a strong reliance on a single unique accepting state. An example of this would be the patrolling task $GF a \\wedge GF b$. Here an accepting run would require the agent to visit both $a$, and $b$ infinitely often, but this would not be discoverable by the graph search algorithm described here.\"\n\nWe respectfully clarify that this is a misunderstanding of our technique. A Büchi automaton accepts an input if and only if it passes through an accepting state infinitely many times as it reads the input. Consider the converted graph representation of the Büchi automaton for the LTL task $GF w \\wedge GF y$ depicted in Fig (a) of the global rebuttal. While there is just one accepting state, it only accepts trajectories in which the accepting state is reached infinitely often in a loop, meaning that the agent must visit the white zone ($w$) and the yellow zone ($y$) in Fig (b) infinitely often. This kind of infinite looping behavior $(wy)^\\omega$ can be handled by our technique with a goal condition agent capable of reaching $w$ and $y$. As illustrated in the global response, we also support multiple accepting states.\n\n**R3. The type of edge transitions that can be accomplished by a goal-conditioned policy.**\n- 3.1 Can we handle simultaneous satisfaction of multiple propositions? \n\nYes. Our approach supports simultaneous satisfaction such as $F(g_1 \\wedge g_2)$. As illustrated in line 919, Sec F.3 in the supplementary material, to use a goal-conditioned policy $\\pi$ to reach the overlapped goal space covered by $g_1$ and $g_2$, at any environment state $s$, we take an action $\\arg\\max_a{min(Q^\\pi(s, g_1, a), Q^\\pi(s, g_2, a))}$. Fig. (g) in the global rebuttal provides an example. \n\n- 3.2 Can we handle self-transition that requires maintaining some proposition as true until reaching a goal? \n\nYes. In our graph representation $G_\\mathcal{B}$ of a Büchi automaton $\\mathcal{B}$, a \"self-transition\" on a node $q$ describes the goal-related constraint $\\phi$ that must be maintained until the agent can transition to a neighbor node of $q$ with the goal condition $\\psi$. If $q$ is on the planned optimal path, the agent for $B$ needs to use a goal-conditioned policy $\\pi$ to ensure $\\phi$ before accomplishing $\\psi$. In the paper, we primarily focus on reach avoidance, where $\\phi = \\bigwedge_k \\neg g_k$ encodes regions in the goal space to avoid. At a current environment state $s$, when the value function $V^\\pi(s, g_k)$ is greater than a threshold, we take a safe action $\\arg\\min_a {Q^\\pi(s, g_k, a)}$ that moves the agent away from the dangerous zone $g_k$ (see line 908 for the formalization). Fig. (i) in the global rebuttal provides an example. \n\nDually, our strategy applies to cases where $\\phi = \\bigwedge_k g_k$ encodes goal regions that the agent must stay within before transitioning out from $q$. In such cases, if the value function $V^\\pi(s, g_k)$ is less than a threshold, we can take an action $\\arg\\max_a {Q^\\pi(s, g_k, a)}$ that encourages the agent to remain in $g_k$. As our navigation benchmarks do not support the evaluation of this feature, we plan to explore it in future work.\n\n**R4. Training goal-conditioned policies**\n\nOur training algorithms are illustrated in Sec. A of the supplementary material.  We evaluated our goal-conditioned policies for ZoneEnv and Ant 16 rooms over 1000 rollouts. We randomly sample the initial agent state and the goal to reach in each rollout. The length of a rollout for ZoneEnv is 500 and for Ant 16 room is 1000. The goal-reaching success rate is 97.2% for ZoneEnv and 67.8% for Ant 16 rooms (evaluated over 3 trials of training). A typical failed case in Ant 16 rooms is shown in Fig. (o) in the global rebuttal where the ant gets stuck at wall corners. Fig (p) highlights the usefulness of LTL instructions to guide the agent to explore a detoured path to the goal.\n\nIndeed, goal-conditioned RL has made substantial progress in recent years. We recommend the following paper that surveys state-of-the-art algorithms for training competent goal-conditioned policies in high-dimensional continuous environments:\n\nMinghuan Liu, Menghui Zhu, Weinan Zhang. Goal-Conditioned Reinforcement Learning: Problems and Solutions. CoRR abs/2201.08299 (2022)\n\n**R5. Can this approach handle simultaneity? e.g. $F(a \\wedge b)$?**\n\nYes. Please see R3.1.\n\n**R6. Can this approach handle self transition that requires maintaining some proposition as true until a goal is reached e.g. $F b \\wedge a U b$?**\n\nYes. Please see R3.2.\n\n**R7. Can the graph search be adopted for recurrence type formulas from Manna and Pnueli's temporal hierarchy $(GF a \\wedge GF b)$?**\n\nYes. Please see Fig (b) in the global rebuttal as an example.\n\n**R8. What are the implicit assumptions you are making on the environment?**\n\nWe assume the atomic propositions in LTL properties *can only be goals* within the goal space of the underlying goal-conditioned policy e.g. colored zones in the ZoneEnv navigation benchmark. We do not allow other sources of atomic propositions e.g. external environment signals that are out of the agent's control. For example, our current algorithm does not apply when the agent needs to pursue different tasks based on an external signal. We will clarify this important assumption in the paper."}, {"review_id": "eu06jk0zFW", "reviewer": "Reviewer_szt3", "summary": "The paper proposes a new technique for multi-task RL when the tasks are specified using a high-level language (LTL in this case). The approach involves identifying a set of skills corresponding to a set of reachability and safety objectives and training policies for them. While training these policies (which are represented using a single goal-conditioned policy), a separate value function is trained to measure, for every pair of goals, the expected return for the task of reaching one goal from another. Then, given an LTL formula, a subtask graph structure is constructed which is used to compute a high-level plan for performing the task using the learned skills. Experimental results suggest that the proposed approach outperforms a state-of-the-art method for multi-task RL (for LTL tasks) and is better suited for multi-task performance than another compositional approach which is designed for single-task RL.", "questions": "- It is mentioned that disjunctions can be handled by adding separate transitions. But conjunctions seem to be restrictive too. For example, the assumption doesn't allow for a transition with predicate $a\\land\\lnot b$. How are such things handled?\n- How is the cycle to loop within an accepting SCC picked after reaching an accepting state?\n- How are the goals (predicates) chosen for training the goal-conditioned policy during an episode?\n- Is there a class of MDPs or LTL formulas for which the proposed approach of computing a single path in the automaton can be justified?", "limitations": "As mentioned in weaknesses, there are some limitations to the proposed approach which should be discussed in the paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The ability to learn a set of skills that can be used to perform a wide range of long-horizon tasks specified using LTL is very useful. This proposed approach is a simple and natural way to achieve this.\n\n- Although the idea of planning over a graph structure in order to perform a complex temporal task is not new, the paper provides a way to achieve this for all of LTL (rather than a subset of LTL considered in prior work) and furthermore applies the idea to multi-task RL. \n\n- The experimental results look promising and show that the proposed approach can be used in a wide range of environments to solve complex tasks without further training (after training the goal-conditioned policy)", "weaknesses": "- The main weakness, in my opinion, is that the approach doesn't seem to be general enough to handle all of LTL as claimed by the authors. For instance, the LTL task is eventually reduced to following a single path (with a loop at the end) in the automaton graph. But it might not be optimal to follow a single path and one might have to use different high-level strategies from different states of the MDP. Furthermore, the high-level plan is computed using the trained value function which does not consider the ability to stay safe and avoid triggering alternate transitions when measuring the ability to trigger a specific transition in the automaton. The heuristics for handling such avoidance constraints during test time seems reasonable but it is a bit ad-hoc and it is unclear why it is good in general (an ablation study might improve the paper).\n- The clarity of the paper could be improved. Many assumptions are made throughout the paper (such as transitions using conjunctive predicates and goals being disjoint). It appears that some of these assumptions can be removed. A clearer presentation could help mitigate doubts about what assumptions are necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful feedback and constructive comments! We present our response to each of your concerns and questions below.\n\n**R1. Single path problem:** \"The LTL task is eventually reduced to following a single path in the automaton graph. But one might have to use different high-level strategies from different states of the MDP.\"\n\nWe clarify that our task planning algorithm may choose different high-level paths for the same LTL task, contingent upon the specific initial environment states. For example, consider the Ant 16-room navigation environments shown in Fig (m) and Fig (n) in the global rebuttal. Based on the learned value function (formalized in line 185), for different initial environment states, our task planning algorithm chooses distinct high-level paths tailored for these initial states.\n\n**R2. What are our assumptions?**\n\nWe assume the atomic propositions in LTL properties *can only be goals* within the goal space of the underlying goal-conditioned policy e.g. colored zones in ZoneEnv navigation. We do not allow other sources of atomic propositions e.g. external environment signals that are out of the agent's control. For example, our current algorithm does not apply when the agent needs to pursue different tasks based on an external signal. We will clarify this assumption.\n\n*This limitation is related to the *single path problem* raised in R1.* A potential solution is using a task monitor, which acts as an external memory, to maintain a record of completed sub-goals and past external environment signals. During task execution, when receiving a new environmental signal, our task planning algorithm can dynamically revise the high-level path for the remaining sub-goals that the goal-conditioned agent needs to achieve. We leave it for future work.\n\n**R3. Handling avoidance constraints:** \"The high-level plan is computed using the trained value function which does not consider the ability to stay safe and avoid triggering alternate transitions. The heuristics for handling such avoidance constraints during test time seems reasonable but it is a bit ad-hoc and it is unclear why it is good in general (an ablation study might improve the paper).\"\n\nWe acknowledge the reviewer's valid point regarding the limitation of our task-planning approach, which does not consider the goal-conditioned agent's ability to stay safe before reaching a sub-goal. One solution is to learn an *extended* value function as described in [1]. A Boolean composition of the extended value functions for goal reaching and staying away from unsafe zones can provide a more accurate estimation of the agent's capability of triggering a specific transition in the automaton. We leave the integration with [1] for future work and will clarify this limitation.\n\nWe indeed provided an ablation study for handling avoidance at test time. The results were included in the supplementary material line 924, Sec F.3. We investigated the impact of the value threshold $\\sigma$ for avoidance. Given a goal-conditioned policy $\\pi$, If the value function $V^\\pi(s, g) \\ge \\sigma$ at an environment state $s$ (implying the agent is close to a region $g$ in the goal space to avoid), the agent must take safe actions to move away from $g$ (line 908). As we used sparse reward functions that yield only 0 or 1 for training $\\pi$, $\\sigma$ should be set somewhere close to (but less than) 1. The results were summarized in Table 3, where we observe that an excessively large value of $\\sigma$ compromises the agent's ability for goal reaching, while an insufficiently small value negatively impacts the agent's ability to stay safe.\n\n[1] Nangue Tasse, G., James, S. and Rosman, B. A boolean task algebra for reinforcement learning. NeurIPS 2020.\n\n**R4. How do we handle conjunctive predicates for a transition?**\n\nOur strategy supports environments with overlapping subgoal regions (line 919 in the supplementary material). Given a goal-conditioned policy $\\pi$, we support $F(g_1 \\wedge g_2)$ by at any environemnt state $s$ taking an action $\\arg\\max_a{min(Q^\\pi(s, g_1, a), Q^\\pi(s, g_2, a))}$. We support $F(g_1 \\wedge \\neg g_2)$ by reusing our avoidance strategy to avoid $g_2$ when the agent is deemed close to the goal region $g_1$ i.e. the value function output $V^\\pi(s, g_1)$ is above the threshold $\\sigma$. Please see an extended discussion on our avoidance strategy in line 896, Sec F.3. Fig (g) and (h) in the global rebuttal provide examples demonstrating how conjunctive predicates are handled for transitioning. Compared with the path in Fig (g), the agent in Fig (h) takes a detour to avoid touching the red zone.\n\n**R5. How is the cycle to loop within an accepting SCC picked after reaching an accepting state?**\n\nAfter reaching an accepting state, we apply Dijkstra's algorithm to find the shortest cycle in the SCC that contains the accepting state. Edge weights are determined by the trained value function that measures, for every pair of goals, the expected return of reaching one goal from another.\n\n**R6. How are the goals chosen for training the goal-conditioned policy during an episode?**\n\nOur technique assumes the existence of a goal-labeling function $L$ that maps environment states to valid goals. The goals in ZoneEnv are colored zones: Yellow $y$, Red $r$, White $w$, and Jetblack $j$. For example, $r \\in L(s)$ if and only if the agent steps onto a red zone at an environment state s. For each color, we use a fixed random vector as the goal representation for the goal-conditioned policy. The goals in Ant 16 rooms are in the form of $(r, c)$ that denotes the horizontal and vertical (integer) positions of the Mujoco ant. Given an environment state $s$, define $L(s) = (r, c)$ if the position of the ant in $s$ is close to $(r, c)$ within a threshold. During training, we randomly sample initial states and goals and correspondingly adapt the reward function and the goal representation. More details are in the supplementary material Sec E."}, {"review_id": "easdm2uSIp", "reviewer": "Reviewer_oQVB", "summary": "This paper considers the problem of instructing goal-conditioned RL agents to follow specifications expressed in Linear Temporal Logic (LTL) formulae. The proposed method works as follows. First, construct a Buchi automaton from the LTL specification, which is then converted to a directed graph representation. Then, use a weighted-graph search algorithm to solve for a high-level plan that satisfies the LTL specification, utilizing the value function of the goal-conditioned agent as a surrogate of the difficulties of achieving each goal. Finally, execute the high-level plan using the goal-conditioned agent. The proposed method is evaluated on three benchmark environments: LetterWorld, ZoneEnv, and Ant-16rooms. The method is compared with two baselines for learning LTL satisfying policies. It is shown to outperform the two baselines, as well as generalize better on out-of-distribution tasks.\n", "questions": "Are the baselines also given a goal-conditioned agent, and focusing on solving the high-level planning problem? \n", "limitations": "I did not find a discussion on the limitations in this paper. One possible aspect for discussion is what to do when the task cannot be divided into high-level LTL solving and low-level goal achieving. For example, the case where how to achieve each goal is context dependent.\n", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper focuses on a promising direction and targets an important problem of the field: how to learn/search policies that can generalize to complex, compositional task specifications, while using less or no additional training on the new tasks. The problem formulation of LTL specifications is a fruitful step towards this general direction, therefore of great potential significance. \n\nThe proposed method of using Buchi automaton and weighted graph search (using value functions as weights to measure difficulty of achieving each goal) to solve high-level plans for LTL tasks is technically interesting and novel to my knowledge. It also makes sense intuitively and seems to be a good method for this problem. ", "weaknesses": "In my view, there are several improvements that needs to be made in terms of experimental settings and expositions of the paper before it is ready to publish here. \n\n- The proposed method considers the setting where low-level policies to achieve each goal are given, and targets the problem of how to solve for a high-level plan that can satisfy the LTL task specification. In this case, the baselines should be alternative methods for computing a high-level plan, with the same assumption that the low-level policies are given. Then the experiments can show how good the proposed method is in solving the problem it targets. It seems that the current baselines do not operate on the same premise (i.e., given low-level policies for each goal, how to solve high-level plan). \n- The writing of the paper could be improved to help with clarity. For example, it would be helpful to briefly introduce how the proposed method works and summarize the experimental results in the introduction section. There are also a few typos in the paper, e.g., line 70 “white zones”. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful feedback and constructive comments! We present our response to each of your concerns and questions below.\n\n**R1. Comparison with the baselines**: \"The baselines should be alternative methods for computing a high-level plan, with the same assumption that the low-level policies are given.\"\n\nWe thank the reviewer for this valuable suggestion. In the supplementary material line 792 Sec E.3, we included a baseline for random high-level path selection, evaluated using the Ant 16-room environment and LTL specifications 1 to 8 (line 700 Sec E.1). Recall that our algorithm uses the goal value function $\\mathcal{V}(s_0, g_1, g_2)$ to measure the capability of reaching goal $g_2$ from goal $g_1$ from the viewpoint of the agent at an initial state $s_0$. This information is crucial for performing high-level task planning over the graph representation of a Büchi automaton. The baseline randomly generates high-level paths from the Büchi automaton of an LTL specification, and the goal-conditioned agent executes toward the goals along these randomly selected paths. The success rates for the ablated version of our algorithm across all specifications are presented in the last column of Table 2, and the example trajectories of the agent for LTL specifications 1 to 8 in this ablated setting are depicted in Figure 15. This result reveals that without high-level path planning guided by the goal value function $\\mathcal{V}$, the performance in satisfying LTL specifications 1 to 8 significantly deteriorates. This decline can be attributed to the randomly selected paths sometimes crossing obstacles in certain rooms, making it challenging for the Mujoco ant to navigate through them.\n\nDuring the rebuttal period, we additionally compared our approach with the Logical Options Framework (LQF) [1] baseline. The LQF baseline learns a meta-policy for choosing amongst the options to reach subgoals to reach the final state of the finite state automaton representation of an LTL property. The learning algorithm is based on value iteration over the product of the finite automaton and an environment. That is on every step in the environment, two transitions are applied: the option transition and the finite state automation transition. The options can be recombined to fulfill new tasks. Compared to our technique, LQF only supports co-safe LTL [2] where the \"always\" operator is not allowed and the \"next\", \"until\", and \"eventually\" operators can only be used in positive normal form. We compared our technique with LQF given the same goal-condition policy for subgoals using the Ant 16-room environment and LTL specifications 1 to 7 (line 700 Sec E.1). We excluded specification 8 because it is not supported by LQF.  We find the two strategies learned the same high-level planning strategy but LQF takes ∼50-100 retraining steps, while our technique generalizes zero-shot to these specifications and we additionally support the $\\omega$-regular specification 8. We will include these additional results in a revised version of our paper.  \n\nWe did not compare our approach with LQF using the colored ZoneEnv environment because this is a multi-task benchmark, which is out of the capability of the meta-policy learning algorithm in LQF. We are unaware of any existing high-level planning algorithms for LTL that generalize to multi-task and out-of-training-distribution environments in a zero-shot manner. To our best, our technique is the first algorithm that can do so.\n\n[1] Brandon Araki, Xiao Li, Kiran Vodrahalli, Jonathan A. DeCastro, Micah J. Fry, Daniela Rus. The Logical Options Framework. ICML 2021: 307-317\n[2] Amit Bhatia, Lydia E. Kavraki, Moshe Y. Vardi. Sampling-based motion planning with temporal goals. ICRA 2010: 2689-2696\n\n**R2. The writing of the paper could be improved to help with clarity**\n\nWe appreciate your suggestion for improving the writing of our paper. We will introduce how the proposed method works at a high level and summarize the experimental results in the introduction section, and we will correct the typos in the paper.\n\n**R3. Are the baselines also given a goal-conditioned agent, and focusing on solving the high-level planning problem?**\n\nPlease see R1 above.\n\n**R4. Limitations:** \n\nWe thank the reviewer for the suggestion to explicitly discuss the limitations of our approach. Indeed, we assume the atomic propositions in LTL properties *can only be goals* within the goal space of goal-condition policies e.g. colored zones in the ZoneEnv navigation benchmark. We do not allow other sources of atomic propositions e.g. external environment signals that are out of the agent's control. For example, our current algorithm does not apply when the agent needs to pursue different tasks based on an external signal. The reviewer is indeed correct in pointing out that our current strategy may not be sufficient when achieving each goal depends on context-dependent external environment signals. We will clarify this limitation in a revised version of the paper. Please also refer to our global response for a justification of our current strategy.\n\nA potential solution to the aforementioned limitation is using a task monitor, which acts as an external memory, to maintain a record of completed sub-goals and past external environment signals. During task execution, when receiving a new environmental signal, our task planning algorithm can dynamically revise the high-level path for the remaining sub-goals that the goal-conditioned agent needs to achieve. We leave it for future work."}]

Author rebuttal:
We greatly appreciate the valuable feedback and suggestions provided by the reviewers! We will begin by addressing the primary concern raised by the majority of the reviewers in the global rebuttal. We will address the concerns of each reviewer in the individual review responses.

### **How do we support $\omega$-regular  LTL properties?**

Our technique can handle $\omega$-regular LTL specifications even though the underlying goal-conditioned agents have never seen such specifications during training time. ***We included experimental results of applying our algorithm to  $\omega$-regular LTL specifications in the supplementary material line 663, Sec. D which is referred to in the submitted paper. We will incorporate these important experimental results in the main body of the paper.***

**1. Summary of the Task Planning Algorithm.** Our technique generates policies for $\omega$-regular LTL specifications based on a goal-conditioned RL agent and a learned goal value function as follows:
* We first convert $\varphi$ to a Büchi automaton $\mathcal{B}$, which is subsequently converted to a graph representation $G_\mathcal{B}$ using the techqniue illustrated in Sec 3.1.
* We associate edges on $G_\mathcal{B}$ with weight $w$ equal to the capability of the goal-conditioned agent to transition between the goals on the source and target nodes, estimated by the learned $\mathcal{V}$ value function. See the formalization of $\mathcal{V}$ in lines 185-188.
* We decompose $G_\mathcal{B}$ into strongly connected components (SCCs) using Tarjan’s algorithm.
* To find an optimal path on $G_\mathcal{B}$ for task execution to satisfy the LTL $\varphi$, we follow these steps:
    * For each accepting state $s_a$ in a maximal SCC, we use Dijkstra's algorithm to find the shortest path from the initial state to $s_a$, denoted as $p$.
    * Next, we apply Dijkstra's algorithm to find the shortest cycle from $s_a$ back to $s_a$ in the maximal SCC, denoted as $q$.
    * The optimal path for the accepting state $s_a$ is $pq^\omega$ where $\omega \rightarrow \infty$ represents the number of times the shortest cycle is executed. The cost of the optimal path is calculated as $w(p) + \omega \cdot w(q)$ where $w(p)$ or $w(q)$ is the sum of the weights of the edges on $p$ or $q$. In the implementation, we use $\omega = 5$ to estimate the path cost.
    * Finally, we select the optimal path on $G_\mathcal{B}$ as the least-cost path from the initial state to any accepting state of $G_\mathcal{B}$.

**2. Examples.** Please see the demonstrations in Fig. 8 of the attached PDF file where Fig (b), (c), (d), (e), (f), (k), (l) are trajectories produced by our trained goal-conditioned agents instructed by the corresponding $\omega$-regular LTL properties in the ZoneEnv and Ant 16-room environments respectively. We conducted 1000 evaluations for each of these $\omega$-regular LTL properties on randomly sampled environments to determine the task success rate. A task run is deemed successful if the loop from the accepting state on the optimal path chosen by our task planning algorithm can be consecutively executed 5 times within 2000 timesteps during our evaluation. Our success rate surpasses 90% for all these properties. ***We included more thorough experimental results in Sec. D of the supplementary material.***

**3. Justification.** The objective of our task planning algorithm is to find a policy $\pi^* = \arg\max_{\pi} \mathbb{E} \tau \sim \pi(\cdot \vert \cdot, \varphi) \left[ \mathbb{1}[\tau \models \varphi] \right]$, which generates the maximum number of LTL-satisfying runs for a given LTL property $\varphi$. Our formalization of goal-condition RL uses a sparse binary reward function (Equation 2) - a reward of 1 is provided only when the specified goal is successfully achieved by the end of a training episode. In this setting, when the discounted factor $\gamma \rightarrow 1$, the weight $w$ for each edge on $G_\mathcal{B}$, which is determined by the learned value function $\mathcal{V}$ (e.g. $w =-\log{\mathcal{V}(\cdot)}$), is inversely proportional to the (lower bound of the) probability of reaching the goal region represented by the target node from that represented by the source node of the edge. As such, graph search in the task planning algorithm seeks the optimal path as the one the agent is most likely to succeed. The main strength of our technique is its ability to adapt a goal-conditioned agent into one capable of achieving arbitrary LTL properties using atomic propositions from the goal space in a zero-shot manner.  We acknowledge that the use of a bounded $\omega = 5$ overapproximates the true optimal probability, which is a limitation (even though we can use arbitrarily large $\omega$ with no additional cost).    

Meta-review: The paper presents an approach to learning to achieve temporal logic goals in an environment. The key novelty is that the approach converts the LTL formula into Buchi automata and then leverages the structure of the automata to learn policies that generalize to other goals. 

All reviewers had initial concerns with the paper, but all the concerns were addressed in the rebuttal, mostly with content that was already present in the appendix; in particular some additional experiments. The only remaining concern is that some reviewers feel it is important that the paper better incorporate this content into the main body of the paper. The authors have provided a helpful list of changes to the paper that will address the reviewer concerns.
Decision: Accept (poster)