Logical Specifications-guided Dynamic Task Sampling for Reinforcement Learning Agents

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 21:08:54

Abstract: Reinforcement Learning (RL) has made significant strides in enabling artificial agents to learn diverse behaviors. However, learning an effective policy often requires a large number of environment interactions. To mitigate sample complexity issues, recent approaches have used high-level task specifications, such as Linear Temporal Logic (LTLf ) formulas or Reward Machines (RM), to guide the learning progress of the agent. In this work, we propose a novel approach, called Logical Specifications-guided Dynamic Task Sampling (LSTS), that learns a set of RL policies to guide an agent from an initial state to a goal state based on a high-level task specification, while minimizing the number of environmental interactions. Unlike previous work, LSTS does not assume information about the environment dynamics or the Reward Machine, and dynamically samples promising tasks that lead to successful goal policies. We evaluate LSTS on a gridworld and show that it achieves improved time-to-threshold performance on complex sequential decision-making problems compared to state-of-the-art RM and Automaton-guided RL baselines, such as Q-Learning for Reward Machines and Compositional RL from logical Specifications (DIRL). Moreover, we demonstrate that our method outperforms RM and Automaton-guided RL baselines in terms of sample-efficiency, both in a partially observable robotic task and in a continuous control robotic manipulation task.

Main paper: 
 introduction: 
 Agents are now capable of learning optimal control behavior for a broad spectrum of tasks, ranging from Atari games (Gao and Wu 2021) to robotic manipulation tasks (Nguyen and La 2019) , thanks to recent advancements in Reinforcement Learning (RL). Despite the progress made in RL, learning an optimal task policy using model-free RL techniques still suffers from sample complexity issues because of sparse reward settings and unknown transition dynamics (Lattimore, Hutter, and Sunehag 2013) . These challenges further intensify in long-horizon settings, where the agent needs to perform a series of correct sequential decisions to achieve the goal. Additionally, certain tasks (such as -robot needs to make dinner only if it bought groceries in the afternoon) require the agent to encode and remember its episodic history (whether the groceries were bought) in order to solve the task effectively. To alleviate this issue in complicated tasks, several lines of work have ex-plored representing the goal using an intricately shaped reward function that guides the agent toward the goal (Grzes 2017) . However, generating such a reward function requires the human engineer to assign 'importance' weights to various aspects of the task, which is time consuming and assumes knowledge on which aspects of the task are important. Poorly engineered reward functions can lead to local optima, where the agent learns to satisfy only a subset of goals and ignores the rest.Recent research has investigated representing the goal using high-level specification languages, such as finite-trace Linear Temporal Logic (LTL f ) (De Giacomo and Vardi 2013), Reward Machines (RM) (Icarte et al. 2022) , SPEC-TRL (Jothimurugan, Alur, and Bastani 2019) that allow defining the goal of the task using a graphical representation of sub-tasks. The high-level objective is known before commencing the task, and the graphical representation allows the agent to achieve easier sub-goals initially, and build upon them to achieve complex goals. Encoding the task using a graphical structure allows us to tackle the problem in a Markovian manner by tracking the history as a part of the state space (Afzal et al. 2023) , thereby allowing the agent to keep track of its episodic history. For instance, if the task for a robot is to reach kitchen and then make dinner, the graphical structure of the task obtained from the high-level specification allows the agent to reason whether it has reached the kitchen before it can commence its policy for making dinner. RM approaches still require human guidance in defining the reward structure of the machine, which is dependent on knowing how much reward should be assigned for accomplishing each sub-goal. The process of designing the reward structure assumes that the human engineer is aware of how much should reward should the agent receive when it accomplishes the sub-goals in particular order. This assumption is infeasible in scenarios when the structure of the environment or the exact order in which the sub-goals must be achieved is unknown in advance. In contrast, our method does not require access to the reward structure.Another method, Compositional RL from Logical Specifications (DIRL) (Jothimurugan et al. 2021) mitigates the reward assignment issue by using Dijkstra's algorithm to determine which sub-tasks (edges) should be explored in the SPECTRL DAG graph (Jothimurugan, Alur, and Bastani 2019) in order to learn policies to reach nodes in the DAG that yield the highest success rate. DIRL requires the agent to learn RL policies for satisfying all outgoing edge propositions (each edge encodes a sub-task) from such nodes. However, this approach requires the agent to explore a sub-task for a manually specified number of interactions, which requires knowledge about the task complexity. DIRL ends up spending a lot of interactions learning unproductive policies as some sub-tasks can be unpromising, yet the agent has to spend the defined number of interactions learning a policy for the sub-task. Unlike DIRL, our approach is sample-efficient as it finds unpromising sub-tasks based on the learning progress of the sub-tasks, and discards them; saving costly interactions and converging to a successful 100 policy faster. This problem of minimizing the overall number of interactions while learning a set of successful policies is non-trivial as the problem equates to finding the shortest path in a graph whose true edge weights are unknown a priori (Szepesvári 2004 ). In our case, the edge weight denotes the total number of environmental interactions required by the agent to learn a successful policy for the sub-task encoded by the edge, in which the agent must induce a visit to a state where certain properties hold true. And, we can sample interactions for a sub-task only if we have a policy 110 to reach the edge's source node from the start node of the graph, making the learning process more sample-inefficient.To address the above challenges, we present Logical Specifications-guided Dynamic Task Sampling (LSTS). We begin with a high-level objective represented using SPEC-115 TRL specification formulas which can equivalently be represented using directed acyclic graphs (DAG) (Jothimurugan, Alur, and Bastani 2019) . The DAG structure encodes memory, helping the agent understand what events of interest have occurred in the past, and which events must occur 120 to reach the accepting states. Our key insight is to learn RL policies for sub-tasks defined using the edges of the DAG. Specifically, the agent transitions from the node q to p in the DAG when the propositional logic formula labeling the edge (q, p) evaluates to true. We use the set of propositional logic 125 formulas labeling the outgoing edges from a given node in DAG to define sub-tasks. The trajectory induced by a suc-cessful RL policy for the sub-task enables the agent's highlevel state in the DAG to transition from the source node to the destination node of the edge defining the sub-task. We employ an adaptive Teacher-Student learning strategy, where, (1) the Teacher agent uses its high-level policy along with exploration techniques to actively sample a sub-task for the Student agent to learn. The high-level policy considers the DAG representation and the Student agent's expected performance on all the sub-tasks, aiming to satisfy the highlevel objective in the fewest number of interactions, and (2) the Student agent interacts with the environment for a few steps (much fewer than the interactions required to learn a successful policy for the sub-task) while updating its lowlevel RL policy for the sampled sub-task. The Teacher observes the Student's performance on these interactions and updates its high-level policy. Steps (1) and (2) continue alternately until the Student agent learns a set of successful policies that guide the agent to reach a goal state.Running example: As an example, let us look at the environment shown in Fig. 1a . The goal for the agent is to collect any of the two Keys, followed by opening the Door and then reaching the Goal while avoiding the Lava at all times. The task's high-level objective (ϕ) is represented using the SPECTRL formula and its corresponding DAG representation G ϕ in Fig. 1b . The DAG does not contain information about the environment configuration, such as: the optimal number of interactions required to reach Door from Key 1 are much higher compared to the interactions required to reach Door from Key 2 , making the Key 1 to Door trajectory sub-optimal. Hence, it is crucial to prevent any additional interactions the agent spends in learning a policy for the sub-task defined by the edge q 1 ¬l∧d ---→ q 3 as the path q 0 ¬l∧k1 ----→ q 1 ¬l∧d ---→ q 3 ¬l∧g ---→ q 4 will always be suboptimal. In our proposed approach LSTS, the Student agent begins with the aim of learning two distinct RL policies: π 1 for the task of visiting Key 1 and π 2 for the task of visiting Key 2 , both avoiding Lava. The Teacher agent initially samples evenly from these two sub-tasks for the Student but later biases its sampling toward the sub-task on which the Student agent shows higher learning potential. Once the Student agent learns a successful policy for one of the sub-tasks (let's say the learned policy π * 1 corresponding to the sub-task defined by the transition q 0 ¬l∧k1 ----→ q 1 ), the Teacher does not sample that task anymore, identifies the next task(s) for the Student using the DAG representation, and appends them to the set of tasks it is currently sampling (in this case, the only next task is: q 1 ¬l∧d ---→ q 3 ). Since the Student agent only has access to the state distribution over q 0 , it follows the trajectory given by π * 1 to reach a state that lies in the set of states where the proposition ¬Lava∧Key 1 holds true before commencing its learning for the policy (π 3 ) for q 1 ¬l∧d ---→ q 3 . If the Student agent learns the policies π * 2 for satisfying the sub-task defined by q 0 ¬l∧k2 ----→ q 2 and π * 4 for q 2 ¬l∧d ---→ q 3 be-180 fore learning π 3 , it effectively has a set of policies to reach the node q 3 . Thus, the Teacher will now only sample the next task for the Student in the DAG representation q 3 ¬l∧g ---→ q 4 , as learning RL policies for paths that reach q 3 are effectively redundant. This process continues iteratively until the Student agent learns a set of policies that reach the goal node (q 4 ) from the start node (q 0 ). The learning curves in Fig. 1c empirically validate the running example. As evident from the learning curves, the Student agent learns policies for thepath q 0 ¬l∧k2 ----→ q 2 ¬l∧d ---→ q 3 ¬l∧g ---→ q 4 that produce trajec- 190tories to reach the goal node q 4 from the initial node q 0 , without excessively wasting interactions on the unpromising sub-task q 1 ¬l∧d ---→ q 3 . The dashed lines in Fig. 1c signify the interactions at which a task policy converged.The dynamic task sampling strategy promotes LSTS to 195 achieve sample-efficient learning on complex tasks by identifying unpromising tasks and discarding them, saving costly interactions. Our empirical results show that LSTS reduces environmental interactions by orders of magnitude compared to state-of-the-art Specifications-Guided RL Baseline 200 DIRL, Reward Machine-based baselines QRM (Icarte et al. 2018) , GSRS (Camacho et al. 2018) , and curriculum learning baseline TSCL (Matiisen et al. 2020) . We also evaluate LSTS ct , a modified algorithm that further improves sample efficiency by continuing exploration on a new sub-task once 205 a goal state for a sub-task is reached. We perform evaluation on two robotic navigation and manipulation tasks and demonstrate that LSTS reduces the number of interactions by orders-of-magnitude when compared to state-of-the-art automaton-guided RL baselines. 
related work: 
 Automaton-guided RL approaches utilize temporal logicbased language specifications to define tasks (Toro Icarte et al. 2018; Bozkurt et al. 2020; Xu and Topcu 2019; Alur et al. 2022) . Separating policies for task sub-goals aids in abward settings. Augmenting the reward function with Monte Carlo Tree Search helps mitigate this issue (Velasquez et al. 2021) . This approach requires the ability to plan-ahead in the environment, which is not always feasible. Automatonguided RL has been used to aid navigational exploration for robotic domains (Cai et al. 2023 ) and for multi-agent settings (Hammond et al. 2021) . Generating a curriculum given the high-level objective (Shukla et al. 2023 ) requires access to the Object-Oriented MDP (Diuk, Cohen, and Littman 2008) , which cannot be obtained if environment details are not known in advance. DIRL interleaves high-level planning with RL to learn a policy for each edge, which overcomes challenges arising from poor representations (Jothimurugan et al. 2021) . This approach becomes inefficient in terms of number of interactions, as it requires the agent to act for a predetermined number of interactions, even if learning the task does not show any promise. Unlike previous works, in this paper, we propose an logical specifications-guided dynamic task sampling approach that does not require access to the environment dynamics or the Reward Machine, and efficiently samples tasks that show promise toward the highlevel objective, saving interactions on unpromising tasks.Teacher-Student algorithms (Matiisen et al. 2020 ) have been previously studied in Curriculum Learning literature (Narvekar et al. 2020; Shukla et al. 2022 ) and in the Intrinsic Motivation literature (Oudeyer and Kaplan 2009) .The idea is to have the Teacher propose those tasks to Student on which the Student shows most promise. This strategy helps Student learn simpler tasks first, transferring its knowledge to complex tasks. The technique reduces the overall number of interactions necessary to learn a successful policy. These approaches tend to optimize a curriculum to learn a single policy, which does not scale well to temporally-extended tasks. Instead, we propose an Logical Specifications-guided Teacher-Student learning strategy that learns a policies for promising automaton transitions, promoting sample-efficient training compared to the baselines. 
theoretical framework: 
 Episodic MDP. An episodic labeled Markov Decision Process (MDP) M is a tuple (S, A, P, R, S 0 , γ, K, P, L), where S is the set of states, A is the set of actions, P (s ′ |s, a) denotes the transition probability of reaching state s ′ ∈ S from s ∈ S using action a ∈ A, R : S × A × S → R is the reward function, S 0 is the initial state distribution, γ ∈ [0, 1] is the discount factor, K is the maximum number of interactions in any episode, P is a set of predicates, and L : S → 2 P is a labeling function that maps a state s ∈ S to a subset of predicates that are true in that state. In every interaction, the agent observes the current state s and selects an action a according to its policy function π(a|s, θ) with parameters θ. The MDP transitions to a new state s ′ ∈ S with probability P (s ′ | s, a). The agent's goal is to learn an optimal policy π * that maximizes the discounted returnG 0 = K k=0 γ k R(s ′ k , a k , s k )until the end of the episode, which occurs after at-most K interactions.High level specification language: In our framework, we adopt the specification language SPECTRL to articu-late reinforcement learning tasks (Jothimurugan, Alur, and Bastani 2019) . A specification ϕ in SPECTRL is a logical formula applied to trajectories, determining whether a given trajectory ζ = (s 0 , s 1 , . . .) successfully accomplishes a desired task. Mathematically, ϕ can be depicted as a function ϕ : Z → B, where B = {TRUE, FALSE} and Z is the set of all trajectories.Formally, a specification is defined over a set of atomic predicates P 0 . Each p ∈ P 0 is associated with a function f p : S → B. The agent's MDP state s satisfies p (denoted by s |= p) when f p (s) = True (in other words, p ⊆ L(s)).The set of predicates P comprises conjunctions and dis- The syntax of SPECTRL specifications is given byϕ ::= achieve b | ϕ 1 ensuring b | ϕ 1 ; ϕ 2 | ϕ 1 or ϕ 2 ,where b ∈ P. Here, achieve and ensuring correspond to 'eventually' and 'always' operators in temporal logic. Each specification ϕ corresponds to a function f ϕ : Z → B, andζ ∈ Z satisfies ϕ (denoted ζ |= ϕ) if f ϕ (ζ) := TRUE.The SPECTRL semantics for a finite trajectory ζ of lengtht are: ζ |= achieve b if ∃ i ≤ t, s i |= b (or b ⊆ L(s)) (1) ζ |= ϕ ensuring b if ∃ i ≤ t, s i |= b (2) ζ |= ϕ 1 ; ϕ 2 if ∃ i < t, ζ 0:i |= ϕ 1 and ζ i+1:t |= ϕ 2 (3) ζ |= ϕ 1 or ϕ 2 if ζ |= ϕ 1 or ζ |= ϕ 2(4) Intuitively, the condition (1) signifies that the trajectory should eventually reach a state where the predicates b hold true. The condition (2) signifies that the trajectory should satisfy specification ϕ while always remaining in states where b holds true. The condition (3) signifies that the trajectory should sequentially satisfy ϕ 1 and then ϕ 2 . The condition (4) signifies that the trajectory should satisfy either ϕ 1 or ϕ 2 . A trajectory ζ satisfies ϕ if there is a t such that the prefix ζ 0:t satisfies ϕ.Furthermore, each SPECTRL specification ϕ is guaranteed to have an equivalent directed acyclic graph (DAG), called an abstract graph. An abstract graph G = (Q, E, q 0 , F, β, Z saf e , κ) is a directed acyclic graph (DAG) with nodes Q, (directed) edges E ⊆ Q×Q, initial node q 0 ∈ Q, final nodes F ⊆ Q, subgoal region map β : Q → 2 S such that for each q ∈ Q, β(q) is a subgoal region and safe trajectories Z saf e = e∈E Z e saf e where Z e saf e ⊆ Z f denotes the safe trajectories for edge e ∈ E. Intuitively, (Q, E) is a standard DAG, and q 0 and F define a graph reachability problem for (Q, E). Furthermore, β and Z saf e connect (Q, E) back to the original MDP M ; in particular, for an edge e = q → q ′ , Z e saf e is the set of trajectories in the MDP M that can be used to transition from β(q) to β(q ′ ) 1 . The function κ labels each edge e = q → q ′ with the predicates b e (labeled edge denoted as e := q be -→ q ′ ). The agent transitions from q to q ′ when the states s i , s i+j in the agent's trajectory ζ satisfy s i ⊆ β(q) and b e ⊆ L(s i+j ) and j ≥ 0.1 See DIRL (Jothimurugan et al. 2021) for more details Given a SPECTRL specification ϕ, we can construct an abstract graph G ϕ such that, for every trajectory ζ ∈ Z, we have ζ |= ϕ if and only if ζ |= G ϕ . Thus, we can solve the reinforcement learning problem for ϕ by solving the reachability problem for G ϕ . As described below, we leverage the structure of G ϕ in conjunction with reinforcement learning to do so. In summary, SPECTRL specifications provide a powerful and expressive means to define and evaluate reinforcement learning tasks. It allows users to specify complex conditions and requirements for successful task completion, enabling a nuanced approach to learning from specifications.Problem Formulation. Given an MDP M with unknown transition dynamics and a SPECTRL formula ϕ representing the high-level objective of the agent, let G ϕ be the DAG representing the language of ϕ. Let Paths(q, X) be the set of all paths in the DAG originating in q and terminating at a node in X ⊆ Q. The aim of this work is to learn a set of policies π * i , i = 0, . . . , n -1, with the following three properties: (i) Following π * 0 results in a trajectory in the MDP that induces a transition from q 0 to some state q 1 ∈ Q in the DAG, following π * 1 results in a trajectory in MDP that induces a transition from q 1 to some state q 2 ∈ Q in the DAG, and so on. (ii) The resulting path q 0 q 1 . . . q n in the DAG terminates at a final node, i.e., q n ∈ F , with probability greater than a given threshold, η ∈ (0, 1). (iii) The total number of environmental interactions spent in exploring and learning sub-task policies are minimized. 
methodology: 
 Sub-task definiton: Given the DAG G ϕ representing the language of ϕ, we define a set of sub-tasks based on the edges of the DAG. Intuitively, given any MDP state s ∈ S and a DAG node q ∈ Q, a sub-task defined by an edge from node q to p ∈ Q defines a reach-avoid objective for the agent represented by the SPECTRL formula, Task(q, p):=achieve(b (q,p) ) ensuring   r∈Sc(q),r̸ =p ¬b (q,r)   where b (q,p) is the propositional formula labeling the edge from q to p in the DAG and Sc(q) is the set of successors of node q in DAG. For example, in Fig. 1b , the propositional formula labeling the edge from q 0 to q 1 is b (q0,q1) = ¬l ∧ k 1 . When e = (q, p), we use Task(e) instead of Task(q, p) and b e instead of b (q,p) for notational convenience.Each sub-task Task(q, p) defines a problem to learn a policy π * (q,p) such that, given any MDP state s 0 ∈ S, following π * (q,p) results in a trajectory s 0 s 1 . . . s n in MDP that induces the path qq . . . qp in the DAG. That is, the agent's high-level DAG state remains at q until it transitions to p. While constructing the set of sub-tasks, we omit transitions that lead to a 'sink' state (from which final states are unreachable).Given the MDP M with unknown transition dynamics and the SPECTRL objective, ϕ, we first translate ϕ to its corresponding directed acyclic graphical (DAG) representation G ϕ = (Q, E, q 0 , F, β, Z saf e , κ). Next, we define the set of sub-tasks. For this, we consider the edges that lie on some path in the DAG from q 0 to some node in F . This is because any path that does not visit F leads to a sink state from which the objective cannot be satisfied. Such edges is identified using breadth-first-search (Moore 1959) .The algorithm for LSTS is described in Algo. 1. We begin by initializing the following (lines 2-4): (1) Set of: Active Tasks AT, Learned Tasks LT, Discarded Tasks DT; (2) A Dictionary Π that maps a sub-task Task(e) corresponding to edge e of DAG G ϕ to a RL policy π e ; (3) A Dictionary representing the Teacher Q-Values Q by mapping Task(e) to a numerical value associated with Task(e).Firstly, we convert G ϕ into an Adjacency Matrix X (line 6), and find the tasks corresponding to the set all the outgoing edges E q0 ⊆ E from the initial node q 0 (line 7). Satisfying the edge's predicates b (q0,q1) ∈ κ(E q0 ) represent a reachability sub-task M ′ where each goal state s ∈ S M ′ f of 400 M ′ satisfy the condition b (q0,q1) ⊆ L(s). The Student agent receives a positive reward for satisfying b (q0,q1) and a small negative reward at all other time steps. The state and action space, and the transition dynamics of M ′ are equivalent to M . To complete the sub-task, the Student agent must Teacher-Student learning: We set the Teacher Q-Values for all the sub-tasks corresponding to edges in AT (i.e., tasks corresponding to E q0 ) to zero (line 8). We formalize the Teacher's goal of choosing the most promising sub-task as a Partially Observable MDP (Kaelbling, Littman, and Cassandra 1998) , where the Teacher does not have access to the entire Student agent state but only to the Student agent's performance on a sub-task (e.g. success rate or average returns), and as an action, chooses a sub-task Task(e) ∈ AT the Student agent should train on next. In this POMDP setting, each Teacher action has an Q-Value associated with it. Intuitively, higher Q-Values correspond to tasks on which the Student agent is more successful, and the Teacher should sample such tasks at a higher frequency to satisfy ϕ (reach a goal node) in fewest overall interactions.(A) Given the Teacher Q-Values, we sample a sub-task Task(e) ∈ AT using the ϵ-greedy exploration strategy (line 10), and (B) The Student agent trains on task Task(e) using the RL policy Π[e] for 'x' interactions (line 11). In one Teacher timestep, the Student trains for x environmental interactions. Here, x << total number of environmental interactions required by the Student agent to learn a successful RL policy for Task(e), since the aim is to keep switching to a sub-task that shows highest promise. (C) The Teacher observes the Student agent's average return g t on these x interactions, and updates its Q-Value for Task(e) (line 12):Q[e] ← α(g t ) + (1 -α)Q[e](5) where α is the Teacher learning rate, g t is the average Student agent return on Task(e) at the Teacher timestep t. As the learning advances, g t increases as t increases, and hence we use a constant parameter α to tackle the non-stationary problem of a moving return distribution. Several other algorithms could be used for the Teacher strategy (e.g., UCB or Thomspson Sampling). Steps (A), (B), (C) continue successively until the policy for any Task(e) ∈AT task converges.Sub-task convergence criteria: We define Student agent's RL policy for Task(q, p) to be converged (line 13) if a trajectory ζ produced by the policy triggers the transition with probability Pr ζ∈Z [ζ satisfies Task(q, p)] ≥ η and ∆(g t , g t-1 ) < τ where η is the expected performance and τ is a small numerical value. Intuitively, a converged policy attains an average success rate ≥ η and has not improved further by maintaining constant average returns. Like all other RM and automaton-based approaches, we assume access to the labeling function L to examine if the trajectory ζ satisfies the formula b (q,p) by checking if the final environmental state s of the trajectory satisfies the condition b (q,p) ⊆ L(s). The sub-goal regions need not be disjoint, i.e., the same state s can satisfy propositions for multiple DAG nodes. Once a policy for the Task(q, p) converges, we append Task(q, p) to the set of Learned Tasks LT and remove it from the set of Active Tasks AT (line 14). In order to ensure that the learned sub-task does not get sampled any further, we set the Teacher Q-value for this sub-task to -∞ (line 15).Discarding unpromising sub-tasks: Once we have a successful policy for the Task(q, p) (the transition q b (q,p) ---→ p), we determine the sub-tasks that can be discarded (line 16). We find the sub-tasks corresponding to edges that: (1) lie before p in a path from q 0 to any q ∈ F , and, (2) do not lie in a path to q ∈ F that does not contain p. Intuitively, if we already have a set of policies that can generate a successful trajectory to reach the node p, we do not need to learn policies for sub-tasks that ultimately lead only to p (e.g., in Fig. 1 if we have successful policies for Task(q 0 , q 2 ) and Task(q 2 , q 3 ), we can discard Task(q 0 , q 1 ) and Task(q 1 , q 3 )). We add all such sub-tasks to the set of Discarded Tasks DT (line 17), and set the Teacher Q-values for all the discarded tasks to -∞ to prevent them from being sampled for the Student agent (line 18). As an extension, in the limit, an optimal policy can be found by not completely discarding such sub-tasks, but rather biasing away from them so that they would still be explored.Traversing in the DAG until ϕ satisfied: Subsequently, we determine the next set of tasks Tasks(E AT ) in the DAG to add to the AT set (line 19). This is calculated by identifying sub-tasks corresponding to all the outgoing edges from p.Since the edge e q,p corresponds to the transition q b (q,p) ---→ p, we have a successful policy that can produce a trajectory that reaches a state where b (q,p) hold true, and Tasks(E AT ) corresponds to X [p]\DT ('\' refers to set-minus) i.e., sub-tasks corresponding to all the outgoing edges from p if Convergence(Q, e, g, η) then 14:Π * ← Π * ∪ Π[e] ; LT ← LT ∪{Task(e)} ; AT ← AT \{Task(e)} 15: Q[e] = -∞ 16:Tasks(E DT ) ← Discarded Tasks(X , e) end if 26: end while 27: return Π * , Π that do not lie in the DT set.After identifying Tasks(E AT ), we set Teacher Q-values for all Task(e) ∈ Tasks(E AT ) to 0 so that the Teacher will sample these tasks (line 23). In our episodic setting, the 500 episode always starts from a state s ∼ S 0 where the propositions for q 0 hold true, and if the current sampled sub-task is Task(p, r), the agent follows a trajectory using learned policies from Π * to reach a state where the propositions for reaching DAG node p hold true (i.e., s ∈ β(p)). The agent 505 then attempts learning a separate policy for Task(p, r).The above steps (lines 9-26) go on iteratively until |Tasks(E AT )| = ∅. This indicates we have no further tasks to add to our sampling strategy, and we have reached a node q ∈ F . Thus, we break from the while loop (line 21) and 510 return the set of learned policies Π * , and edge-policy dictionary Π (line 27). From Π and Π * , we get an ordered list of policies Π * list = [π (q1,q2) , π (q2,q3) , . . . , π (q k-1 ,q k ) ] such that sequentially following π ∈ Π * list generates trajectories that satisfy the SPECTRL objective ϕ 2 .Guarantee: Given the ordered list of policies Π * list , we can generate a trajectory ζ in the task M with 2 Link to code to be provided after review Pr ζ∈Z [ζ satisfies ϕ] ≥ η (Details in Appendix B). 
experimental results: 
 We aim to answer the following questions: (Q1) Does LSTS yield sample efficient learning compared to state-of-the-art baselines? (Q2) After reaching a sub-task goal state, can we sample a new sub-task to continue training and improve sample efficiency? (Q3) Does LSTS yield sample efficient learning for complex robotic tasks with partially observable or continuous control settings? (Q4) How does LSTS scale to complex search-and-rescue scenarios?To answer (Q1), we evaluated LSTS on a Minigrid (Chevalier-Boisvert, Willems, and Pal 2018) inspired domain with the SPECTRL objective:ϕ grid f := (achieve(k 1 ) or achieve(k 2 ); achieve(d); achieve(g))ensuring(¬l) (6)where k 1 , k 2 , d, g, l represent the atomic propositions Key 1 , Key 2 , Door, Goal, Lava respectively. The environment and its ϕ are given in Fig. 1 . Essentially, the agent needs to collect any of the Keys before heading to the Door. After toggling the Door open, the agent needs to visit the grid with the Goal. At all times, the agent needs to avoid the Lava object. We assume an episodic setting where an episode ends if the agent touches the Lava object, reaches the Goal or exhausts the number of allocated interactions. This is a complex problem as the agent needs to perform a series of correct actions to satisfy ϕ grid f . The agent has access to three navigation actions: move forward, rotate left and rotate right. The agent can also perfom: pick-up action, which adds the Key to the agent's inventory if it is facing the Key, drop places the Key in the next grid if Key is present in the inventory, and, toggle that toggles the Door (closed ↔ open) only if the agent is holding the Key. In this experiment, we assume a fully-observable setting where the environmental state is a low-level image encoding of the state. For each cell in the grid, the low-level encoding returns an integer that describes the item occupying the grid, along with any additional information (e.g., the Door can be open or closed).For the Student RL agent, we use PPO (Schulman et al. 2017) , which works for discrete and continuous action spaces. We consider a standard actor-critic architecture with 2 convolutional layers followed by 2 fully connected layers. For LSTS, the reward function is sparse. The agent gets a reward of (1 -0.9 (interactions taken) (interactions allocated) ) if it achieves the goal in the sub-task, and a reward of 0 otherwise. For sub-tasks, interactions allocated = 100. The agent does not receive any negative rewards for hitting the Lava. Baselines: We compare our LSTS method with six baseline approaches: learning from scratch (LFS), Reward Machinebased (RM) baselines: GSRS (Camacho et al. 2018) , QRM (Icarte et al. 2018) ; and Compositional RL from Logical Specifications (DIRL) (Jothimurugan et al. 2021) . All the baselines are implemented using the RL algorithm (PPO), described above. GSRS assigns reward inversely proportional to the distance from the RM goal node. QRM employs a separate Q-function for each node in the RM, and DIRL uses Dijkstra's algorithm (edge cost is the average RL policy success rate) to guide the agent in choosing a path from the specification graph. For the fifth baseline, we modify DIRL such that instead of manually specifying a limit on the number of interactions, which needs to be fine-tuned to suit the task, we stop learning a sub-task once it has reached the convergence criteria defined in Section 4.We call this modified baseline as DIRL c . The sixth baseline (TSCL (Matiisen et al. 2020 )) follows a curriculum learning strategy where the Teacher samples most promising task without the use of any automaton to guide the learning progress of the agent. (More details in Appendix C)The results in Table 2 and Fig. 2 (averaged over 10 trials) show that LSTS reaches a successful policy quicker compared to all baselines. LSTS ct is a modified version of LSTS and is described in Sec. 5.1. The learning curves in Fig. 2 have an offset on the x-axis to account for the interactions in the initial sub-tasks before moving on to the final task in the specification, signifying strong transfer (Taylor and Stone 2009) . Our custom baseline, DIRL c is more sample-efficient than DIRL, and both outperform other baselines, which do not learn a meaningful policy.We performed an unpaired t-test (Kim 2015) to compare LSTS against the best performing baselines at the end of 10 7 training steps and we observed statistically significant results (95% confidence). Thus, LSTS not only achieves a better success rate, but also converges faster (statistical significance result details in Appendix D).Time-to-threshold metric is defined as the difference in number of interactions between two approaches to reach a desired performance (Narvekar et al. 2020) . From Fig. 2 , we see that the time-to-threshold between LSTS and the best-performing baseline DIRL c is 1.85 × 10 6 interactions for 95% success rate.LSTS ct (LSTS + Cont. Training) -Gridworld Domain In LSTS, while learning a policy for Task(q, p), we reinitialize the environment to a random initial environmental state s ∼ S 0 once the agent reaches a state where the propositions (b (q,p) ) hold true. To answer the question Q2, instead of resetting the environment after reaching such a state where b (q,p) hold true, we let the Teacher agent sample a task (let's say Task(p, r)) from the set X [p]\ DT, where X is the adjacency matrix for the graph, and DT is the set of Discarded 615 Tasks, as defined in Algo. 1. This helps the agent continue its training by attempting to learn a policy π (p,r) for Task(p, r) while simultaneously learning a separate policy π (q,p) for Task(q, p). If the agent fails to satisfy Task(p, r), we reset the environment to state s ∼ S 0 . Otherwise, the agent con-620 tinues its training until its trajectory satisfies the high-level objective ϕ. We call this approach LSTS ct (Detailed algo in Appendix A). Results in Table 2 and Fig. 2 demonstrate that this approach improves sample efficiency by reducing the number of interactions required to learn a successful pol-625 icy for the gridworld task, with a time-to-threshold metric of 3.7 × 10 5 interactions as compared to LSTS.To answer (Q3), we test LSTS and LSTS ct on two simulated robotic environments with high interaction cost. The task in 630 Fig. 3a has the following SPECTRL objective:ϕ navigation f := (achieve(Key 1 ) or achieve(Key 2 ); achieve(Goal)) ensuring(¬Lava) (7) In this task, the agent (a simulated TurtleBot) needs to collect any of the keys (yellow blocks) present in a [3m, 3m] continuous environment before reaching the goal position (gray block). At all times, the agent needs to avoid the lava 635 object (red wall) present in the center. The move forward (backward) action causes the robot to move forward (backward) by 0.1m and the robot rotates by π/8 radians with each rotate action. The pick-up and drop actions have effects similar to the gridworld domain. The robotic domain is 640 more complex as objects can be placed at continuous locations. The agent receives an ego-centric image view of the environment (top-right corner of Fig. 3a ), which makes the task partially observable in nature and more complex to get a successful policy. The RL agent is described in Sec. 5.1.The second environment (Fig. 3c ) consists of a simulated robotic arm pushing two objects to their target locations (Gallouédec et al. 2021) To demonstrate how LSTS performs when the plan length becomes deeper, we evaluated LSTS on a complex urban Search and Rescue domain with multi-goal objectives. In this domain, the agent acts in a grid setting where it needs to perform a series of sequential sub-tasks to accomplish the final goal of the task. The agent needs to open a door using a key, then collect a fire extinguisher to extinguish the fire, and then find and rescue stranded survivors. The order in which these individual sub-goals such as opening the door, rescuing the survivors, and extinguishing the fire are achieved does not matter. A fully-connected graph G phi generated using the above mentioned high-level states consists of 24 distinct DAG paths. This is a multi-goal task as the agent needs to find the key to open the door, then extinguish fire and rescue survivors to reach the goal state (details in Appendix F).The results in teractions to learn a set of successful policies for satisfying the high-level goal objective are higher compared to the door key experiment because of the additional complexity of task. We observe that LSTS is able to accommodate the task and 695 learn RL policies that satisfy the high-level goal objective. 
conclusion: 
 We proposed LSTS, a framework for dynamic task sampling for RL agents using the high-level SPECTRL objective coupled with the Teacher-Student learning strategy. 700 Through experiments, we demonstrated that LSTS accelerates learning, converging to a desired success rate quicker as compared to other curriculum learning and automatonguided RL baselines. LSTS ct further improves sample efficiency by continuing exploration on a new sub-task once a 705 goal state for a sub-task is reached. We also evaluate our approach on long-horizon complex robotic tasks where the state space is large and the actions are continuous. LSTS reduces training time without relying on human-guided dense reward function, accelerating learning when the high-level 710 objective is available.Limitations & Future Work: In certain cases, the SPECTRL objective can be novel and/or generating the labeling function can be infeasible. Our future plans involve expanding our framework to scenarios where obtaining a 715 precise SPECTRL specification is challenging. As an extension, we would like to explore biasing away from subtasks rather than completely discarding them once the target node is reached, so in the limit, optimal policies can be obtained. We would also like to explore complex robotic and 720 multi-agent scenarios with elaborate SPECTRL objectives.Autonomous Agents and Multiagent Systems, 2857-2859. Alur, R.; Bansal, S.; Bastani, O.; and Jothimurugan, K. 2022. A framework for transforming specifications in reinforcement learning. In Principles of Systems Design. Springer. Andrychowicz, M.; Wolski, F.; Ray, A.; Schneider, J.; Fong, 
: 
 tions, such as Linear Temporal Logic (LTL f ) formulas or Reward Machines (RM), to guide the learning progress of the agent. In this work, we propose a novel approach, called Logical Specifications-guided Dynamic Task Sampling (LSTS), that learns a set of RL policies to guide an agent from an 10 initial state to a goal state based on a high-level task specification, while minimizing the number of environmental interactions. Unlike previous work, LSTS does not assume information about the environment dynamics or the Reward Machine, and dynamically samples promising tasks that lead to successful goal policies. We evaluate LSTS on a gridworld and show that it achieves improved time-to-threshold performance on complex sequential decision-making problems compared to state-of-the-art RM and Automaton-guided RL baselines, such as Q-Learning for Reward Machines and Compositional RL from logical Specifications (DIRL). Moreover, we demonstrate that our method outperforms RM and Automaton-guided RL baselines in terms of sampleefficiency, both in a partially observable robotic task and in a continuous control robotic manipulation task. 
 
 Appendix: stracting knowledge that can be utilized in novel tasks(Icarte et al. 2018), without reliance on a dense reward function. Another technique is to shape the reward in proportion to the distance from the accepting node in the automaton(Camacho et al. 2018); however, this often leads to suboptimal re-220 


Decision: The paper is overall of a good quality, fairly novel, well written and relevant to ICAPS. Some issues were raised about literature positioning and the expressivity of SPECTRL, plus some additional ones which can be regarded as minor. The major ones appear to have been addressed satisfactorily in the author response, and it is reasonable to expect that, in case of acceptance, the authors will incorporate their response in the final version of the paper, as well as fixing the minor issues. Overall, the work meets the standards of an ICAPS paper.

Reviews: review: strength_weakness: strength_weakness: - Could have explained the rewards for the subtasks earlier
- Could more clearly outline how much this builds on DIRL. The introduction does a good job explaining the key limitation of DIRL, and that you address it, but it could be good to highlight if there are other key deviations beyond carefully selecting which subtasks to learn on.
questions: questions: Remark: None of the following are questions that the authors are required to respond to. They are largely for constructive criticism. I would appreciate a response to some of the more concrete points below, but definitely the authors do not need to respond to musings about alternative choices for learning progress. 

The Teacher-Student structure is quite interesting. Really, this is simply a bi-level structure, where the Teacher adjusts which subtask to learn based on Student progress, so that jointly they find a set of successful policies for the agent to reach a goal state. The terminology, in my opinion, somewhat conflicts with the way Student-Teacher is typically used, for example, in the distillation literature. This is relatively minor, and I am not saying this must be changed, just pointing it out.

It took quite some time to learn what the rewards were for the lower-level agent. Eventually, I say this one sentence: “The Student agent receives a positive reward for satisfying b(q0 ,q1 ) and a small negative reward at all other time steps. ” So the subtasks are all cost-to-goal problems. This should be stated earlier. Or, you could also consider asking if this is necessary. Why not allow the rewards to be more general?

Nonetheless, this important detail came late and led me to be confused about certain choice. For example, I had the following question, which was clarified later once I saw that there are cost-to-goal subtasks.
“epsilon-greedy for task selection is not particularly focused on learning progress. What if one task is actually quite difficult to accomplish, but has high rewards initially? Then the gt would be high, but the agent has not made that much progress.”
I see how this is not an issue now with cost-to-goal problems. But thus it is more important to state this focus on cost-to-goal subtasks more clearly upfront so the reader is not left filling in guessed details. 

It would also be nice to talk more about alternative measures of learning progress. Returns are a reasonable choice. But, did you consider others? Again, not required here, since the primary goal for this paper I believe is to introduce this formalism, where other choices for Q[e] can be considered in follow-up work.

This formalism is new to me and I had a few motivational questions. What settings can we expect the designer to be able to specify subtasks effectively in this language? Can the agent be sure it is always feasible to achieve the subtasks? What if the designer provided a specification where it is not possible?

“We add all such sub-tasks to the set of 480 Discarded Tasks DT (line 17), and set the Teacher Q-values 
for all the discarded tasks to −∞ to prevent them from being sampled for the Student agent (line 18).”
This does not seem right, since epsilon-greedy would still select this task. Presumably, you do not need to set the value to negative infinity, since it is simply not considered when the teacher takes actions.
strength_weakness: strength_weakness: - Minor weakness: lack of discussion of limitations of the approach (see comment 1)
questions: questions: 1) A prerequisite for using LSTS is to first formalize the learning problem with SPECTRL formulas. What if my planning problem is so complex that it is difficult for humans to formalize? It would be beneficial if the authors could discuss any potential limitations of their approach. Specifically, are there scenarios where LSTS is not applicable due to the complexity of formalizing the problem? Such a discussion would provide a clearer understanding of the method's applicability and limitations. 

2) In section 5.1, line 585, the text references "Table 2 and Fig. 2". It seems this might be an error, and it should refer to "Table 1"?

3) In the supplementary material, the source code is labeled as "Automaton-Guided Dynamic Task Sampling for Reinforcement Learning Agents (AGTS)” instead of LSTS. Could the authors clarify the reason for this ? Is the source code for a different method or an earlier version of LSTS? Is AGTS a published method?

Remark upon rebuttal: I would like to thank the authors, I appreciate that you include the discussion in the camera ready version. My rating remains the same.
strength_weakness: strength_weakness: - The novelty of this paper is incremental. The paper needs more discussion on closely related existing works. 
- The ability of the proposed method depends partly on the expressive capability of the Spectrl specification language. Specifically, the Spectrl language can only be used to express disjunction, always, eventually, and sequentially (phi 1 then phi 2). This limits the versatility of the proposed method for more advanced features. 
- The Spectrl specification language itself is not timed. Therefore, it is unable to specify goals such as “the robot should reach goal 1 in 10 seconds”. There exist more advanced specification languages such as STL and MTL that can express timing constraints but are not considered in the paper. 
- There are three evaluation cases in total, while two of them are highly similar (sections 5.1 and 5.2). It is not clear what other more complex scenarios can be achieved using the Spectrl language and the proposed training framework.
questions: questions: •	The paper needs more discussion on closely related existing works. For example, Shukla, Y., Gao, W., Sarathy, V., Velasquez, A., Wright, R., & Sinapov, J. (2023). LgTS: Dynamic Task Sampling using LLM-generated sub-goals for Reinforcement Learning Agents. arXiv preprint arXiv:2310.09454. 
•	In the experiment scenario where the order of sub-tasks does not matter (section 5.3 and table 2), how does the performance of the proposed method compare to DIRL? 
•	Can the proposed method be extended to multi-agent scenarios? Specifically, how can the Spectrl language be utilized to decompose and specify corporative goals among agents? 
•	In line 585, did you mean “Table 1 and Fig. 2”?