Skill Machines: Temporal Logic Skill Composition in Reinforcement Learning
Authors: Geraud Nangue Tasse
Devon Jarvis
Steven James
Benjamin Rosman
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement Learning
Multi task
Temporal logic
LTL
Composition
Zero-shot
Transfer learning
Primary area: reinforcement learning

Abstract: It is desirable for an agent to be able to solve a rich variety of problems that can be specified through language in the same environment. A popular approach towards obtaining such agents is to reuse skills learned in prior tasks to generalise compositionally to new ones. However, this is a challenging problem due to the curse of dimensionality induced by the combinatorially large number of ways high-level goals can be combined both logically and temporally in language. To address this problem, we propose a framework where an agent first learns a sufficient set of skill primitives to achieve all high-level goals in its environment. The agent can then flexibly compose them both logically and temporally to provably achieve temporal logic specifications in any regular language, such as regular fragments of linear temporal logic. This provides the agent with the ability to map from complex temporal logic task specifications to near-optimal behaviours zero-shot. We demonstrate this experimentally in a tabular setting, as well as in a high-dimensional video game and continuous control environment. Finally, we also demonstrate that the performance of skill machines can be improved with regular off-policy reinforcement learning algorithms when optimal behaviours are desired.

Published as a conference paper at ICLR 2024
SKILL MACHINES: TEMPORAL LOGIC SKILL COMPOSITION IN REINFORCEMENT LEARNING
Geraud Nangue Tasse, Devon Jarvis, Steven James & Benjamin Rosman School of Computer Science and Applied Mathematics
University of the Witwatersrand
Johannesburg. South Africa
(geraud.nanguettae nanguetassel, jevon,jarvis, steven.james, benjamin.rosmann @wits.ac.za
ABSTRACT
is desirable for an agent to be able to solve rich variety of problems that can be specified through language in the same environment. A popular approach towards obtaining such agents is to reuse skills learned in prior tasks to generalise compositionally to new ones. However, this a challenging problem due to the curse of dimensionality induced by the combinatorially large number of ways high-level goals can be combined both logically and temporally in language. To address this problem, propose a framework where an agent first learns a sufficient set of skill primitives to achieve all high-level goals in its environment. The agent can then flexibly compose them both logically and temporally provably achieve temporal logic specifications any regular language, such as regular fragments of linear temporal logic. This provides the agent with the ability to map from complex temporal logic task specifications to near-optimal behaviours zero-shot. We demonstrate this experimentally in a tabular setting, as well as in a high-dima sigh-dimensional video game and continuous control environment. Finally, we also demonstrate that the performance of skill machines can be improved with regular off-polic reinforcement learning algorithms when optimal behaviours are desired.
INTRODUCTION
While reinforcement learning (RL) has achieved recent success in several applications, ranging from video games (Badia et al., 2020) to robotics (Levine et al., 2016), there are several shortcomings that hinder RL's real-world applicability. One issue is that of sample efficiency-whii it is possible to collect millions of data points in a simulated environment, is simply not feasible to do so in the real world. This inefficiency is exacerbated when a single agent is required solve multiple tasks, we would expect of generally intelligent agent.
One approach overcoming this challenge is reuse learned behaviours solve new tasks (Taylor & Stone, 2009), preferably without further learning. Such an approach is often compositional- an agent first learns individual skills and then combines them produce novel behaviours. There are several notions of compositionality in the literature, such as spatial composition (Todorov, 2009; Van Niekerk et al., 2019), where skills are combined to produce new single behaviour be executed to achieve sets of high-level goals ("pick up an object that is both blue and box"), and temporal composition (Sutton et al., 1999; Jothimurugan et al., 2021), where sub-skills are invoked one after the other to achieve sequences of high-level goals (for example, "pickup a blue object and then box").
Spatial composition commonly achieved through a weighted combination of learned successor features (Barreto et al., 2018; 2019; Alver & Precup. 2022). Notably, work by Nangue Tasse et al. (2020; 2022b) has demonstrated spatial composition using Boolean operators, such as negation and conjunction, producing semantically meaningful behaviours without further learning. This ability can then be leveraged by agents to follow natural language instructions (Cohen et al., 2021; 2022).
One of the most common approaches to temporal composition is to leam options for achieving the sub- goals present in temporal logic tasks while learning a high-level policy over the options to actually solve the task, then reusing the learned options in new tasks (Araki et al., 2021; Iearte et al.,

---

Published as a conference paper at ICLR 2024
2022). However, other works like Vaezipoor et al. (2021) have proposed end-to-end neural network architectures for learning sub-skills from a training set that can generalise to similar new tasks.
Liu et al. (2022) observe that for all these prior works, some of the sub-skills (e.g.. options) learned from previous tasks can not be transferred satisfactorily to new tasks and provide a method to determine when this is the case. For example, if the agent has previously learned option for "getting blue objects" and another for "getting boxes", it can reuse them to "pickup a blue object and then box", but cannot reuse them "pickup a blue object that is not box, and then box that is not blue". We can observe that this problem is because all the compositions in prior works are either strictly temporal or strictly spatial. While the example shows that temporal composition alone is insufficient, notice that spatial composition is also not enough for solving long-horizon tasks, In these instances, is often near impossible for the agent to learn, owing to the large sequence of actions that must be executed before learning signal is received (Arjona-Meding et al., 2019).
Hence, this work aims to address the highlighted problem by combining the approaches above to develop an agent capable of both zero-shot spatial and temporal composition. We particularly focus on temporal logic composition, such as linear temporal logic (LTL) (Pnueli, 1977), allowing agents to sequentially chain and order their skills while ensuring certain conditions are always or never met. We make the following main contributions:
1. Skill machines: We propose skill machines (SM), which are finite state machines (FSM) that encode the solution to any task specified using any given regular language (such as regular fragments of LTL) as a series of Boolean compositions of skill sub-skills for achieving high-level goals in the environment. An SM is defined by translating the regular language task specification into an FSM, and defining the skill to use per FSM state as a Boolean composition of pretrained skill primitives.
2. Zero-shot and fhw-shot learning using skill machines:
By leveraging reward machines (RM) (Icarte et al., 201 (011a)-finine state machines that encode the reward structure of task-we show how an SM can be obtained directly from an L.T.. task specification, and prove that these SMs are vatisfciing-giver assumptions, an agent can successfully solve the task while adhering to any constraints. We further show how standard off- off-policy RL algorithms can be used improve the resulting behaviours when optimality is desired. This is achieved with no new assumption in RL.
task specification and regular reachability
3. Emperical and qualitative results: We demonstrate approach in several environments, including high-dimensional video game and a continuous control environment. Our results indicate that our method is capable of producing near-optimal to optimal behaviour for variety of long-horizon tasks without further learning, including empirical results that far surpass all the representative state-of-the-art baselines.
BACKGROUND
We model the agent's interaction with the world as a Markov Decision Process (MDP), given by (S.A. p. R, 7), where (i) S is the finite set of all states the agent can be in; (ii) A is the finite set of actions the agent can take in each state; (iii) p(s"1s [s, a) is the dynamics of the world; (iv) R: S x Ax S - IR is the reward function; (v) E [0, 1] is a discount factor. The agent's aim is to compute a Markov policy π from S to A that optimally solves a given task. Instead of directly learning a policy, an agent can instead learn value function that represents the expected return of executing an action a from a state and then following :: (= a) ET 1E R(s at, St+1)]. The optimal action-ver value function is given by Q" Q²(ss a) = max, Q" (s, a) for all states s and actions a, and the op- timal policy follows by acting greedily with respect to Q* at each state: Tt (s) E arg max, Q" (s.s a).
2.1
LTL AND REWARD MACHINES
One difficulty with the standard MDP formulation is that the agent is often required to solve complex long-horizon task using only a scalar reward signal as feedback from which to learn. To overcome this, common approach is to use reward machines (RM) (Icarte et al., 2018b), which provide structured feedback to the agent in the form of a finite state machine (FSM). Camacho et al. (2019) show that temporal logic tasks specified using regular languages, such regular fragments of
2

---

Published as a conference paper at ICLR 2024
LTL (like safe, co-safe, and finite trace LTL), can be converted to RMs with rewards of for accepting transitions and otherwise (Figure shows an example). Hence, without loss of generality, we will focus our attention on tasks specified using regular fragments of LTL as co-safe LTL (Kupferman & Vardi, 2001). These LTT. specificatios and RMs encode the task to be solved using of propositional symbols P that represent high-level environment features follows:
Definition 2.1 (LTL), An LTL expression is defined using the following recursive syntax: o :== P - fP V 4P2 40 A pp2 | X Gip 40 1/1042 9i Fi2z, where p E P- (not), V (or), A (and) are the usual Boolean operators; X (neXi), G (Globally or always), U (Untit), F (Finally or eventually) are the LTL temporal operators; and yp, P1, P2 are any valid LTL expression.
Definition 2.2 (RM). Given a set of environment states S and actions A, reward machine is tuple A = (24, uo, 8n, 5,) where (i) 2 is a finite set of states; (ii) un E L is the initial state; (iii) 6, 1 x 2 + 24 is the state-transition function; and (iv) ò, 2 2d {0, 13 is the state-reward function."
To incorporate RMs into the RL framework, the agent must be able to determine correspondence between abstract RM propositions and states in the environment. To achieve this, the agent is equipped with a labelling function L S - 2 that assigns truth values to each state the agent visits in its environment. The agent's aim now is to learn a policy ι :S x U + A that maximises the rewards from an RM while acting in environment (8. A, P, 7, P, L}. However, the rewards from the reward machine are not necessarily Markov with respect to the environment. Icarte et al. (2022) shows that product MDP (Definition 2.3 below) between the environment and reward machine guarantees that the rewards are Markov such that the policy can be learned with standard algorithms such as Q-learning. This is because the product MDP uses the cross- poossptroucctt to consolidate how actions in the environment result in simultaneous transitions in the environment and state machine. Thus, product MDPs take the form of standard, learnable MDPs. In the rest of this work, we will refer to these product MDPs as tasks. To ensure that the optimal policy is also the policy that maximises the probability of satisfying the temporal logic task specification, we will henceforth assume that the environment dynamics are deterministic.
Definition 2.3 (Tasks). Let (S, p, 7; P, L) represent the environment and (U RM representing the task rewards. Then a task is product MDP My (ST.A.Pr Rr. 2) between the environment and the RM, where ST = S x U. R u), a, (5', ud')) = (,, PT ((s, u), a) = (,', s p(-1s, a). u' 6,, and l' = T(s').
un dur d,) be an
2.2 LOGICAL SKILL COMPOSITION
Consider the multitask setting where for each task M, an agent is required to reach some terminal goal states in a goal space G C S. Nangue Tasse al. (2020; 2022a) develop framework for this setting that allows agents to apply the Boolean operations A, V and - over the space of tasks and value functions. This is achieved by first defining a goal-oriented reward function RM g, a) that extends the task rewards Ras (s, a) to penalise an agent for achieving goals different from the one it wished to achieve: Ra [, a) == RMIN if (g # s and is terminal) else RM (s, a); where RMIN is the lower bound of the reward function. Using ( g, a). the related goal-oriented value function can be defined as Q (s, g. = E "M E 7 RM (St, 9. 0t) )]- Despite the modification of the regular RL objective, an agent maximising over goals and actions: क (s) E arg max,, max, (s. a)..
always recover the regular optimal policy of the given task by
If new task can be represented the logical expression of previously learned tasks, and all tasks differ only in their rewards at goal states (that is, all tasks share the same state and action space, transition dynamics, discount factor, and non-terminal rewards), Nangue Tasse et al. (2022a) prove that the optimal policy can immediately be obtained by composing the learned goal-oriented value functions using the same expression. For example, the V, A, and of two goal-reaching tasks A and B can respectively be solved as follows (we omit the value functions' parameters for readability):
QA V Q/B- max QA: Q Q2 A Q3 min QQa Qa); Q² (QMAX + QMIN) Qai
where QMAX and QMINN are the goal-oriented value functions for the maximum task (R, = RMAX for all 9) and minimum task (R,- RMIN for all G), respectively. Following Nangue Tasse et al. (2022b), we will also refer to these goal-oriented value functions as world value functions (WVFs).
Accepting transitions are those at which the high-level task descriesc,, for examplc, by LTL-is satisfied. RRs are more general, but for clarity, we focus the subset that is obtained from regular languages.
3

---

Published as a conference paper at ICLR 2024
3
SKILL COMPOSITION FOR TEMPORAL LOGIC TASKS
Reward machine
Translate
start
Skill machine
Fication
start
(Fle X C A (C
Selving task zuro-shot
Reration
Value
Cordly Ba
CRA +0 E
compoattion
Environment
RL
Skill primitives
Consider a continuous environment containing a robot (red sphere) with 3 LiDAR sensors that it uses to sense when it has reached a red cylinder ). green button or blue region (the red, green, and blue sample trajectories obtained from them respectively). Then given any task specification over these objects, such as: "Navigate a button and then cylinder while never entering blue regions" with LTL specification (F( ((F O)) A (G -O), the agent first translates the LTL task specification into an RM, then plans which spatial skill to use at each temporal node using value iteration and composes its skill primitives to obtain said spatial skills (culminating in a skill machine), and finally uses them to solve the task without further learning. The RM is obtained by converting the LTL expression into an FSM using Spot (Duret-Lutz et al., 2016), then giving reward of for accepting transitions and 0 otherwise. The nodes labeled t in the RM and SM represent terminal states (sink/absorbing states where no transition leaves the state).
Figure I: Illustration of our framework:
The agent first learns skill primitives to reach these 3 objects
To describe our approach, we use the Safety Gym Domain (Ray et al., 2019) shown in Figure I as running example. Here, the agent moves by choosing a direction and force (AA = IR²2) and observes a real vector containing various sensory information like joint velocities and distance to the objects in its surrounding (S R The LTL tasks in this environment are defined over 3 propositions: P
where each proposition true when the agent e metre near its respective location.
Now consider an agent that has learned how to "Go to the cylinder" (F "Go to a button" (F ), and "Go blue region" (F ). Say the agent is now required to solve the task with LTL specification (F(O A (E O)) A (G
Using prior LTL transfer works (Vaezipoor et al., 2021; Jothimurugan et al., 2021: Liu et al., 2022), the agent would have learned options for solving the first tasks, but then would be unable to transfer those skills to immediately solve this new task. This is because the new task requires the agent to first reach button that is not in blue region (eventually satisfy while not entering a blue region along the way (always satisfy
Similarly, it then must However, all options previously learned will enter a blue region if it is along the agent's path. Hence the agent will need to learn new options for where the option policies never enter along the way.
eventually satisfy A while never satisfying
achieving
and
In general, we can see that there are 22d possible Boolean expressions the agent may be required to eventually satisfy (spatial curse), and 22 possible Boolean expressions the agent may be required to always satisfy (temporal curse). This highlights the curses of dimensionality we aim to simultaneously address. In this section, we will introduce skill primitives as the proposed solution for addressing the aforementioned curses of dimensionality, We will then introduce skill machines as a state machine that can encode the solution to any temporal logic task by leveraging skill primitives.
3.1 FROM ENVIRONMENT TO PRIMITIVES
We desire agent capable of learning sufficient set of skills that be used solve new tasks, specified through LTL, with little or no additional learning. To achieve this, we introduce the notion of primitives which aims address the spatial and temporal curses of dimensionality as follows:
4

---

Published as a conference paper at ICLR 2024
Spatial curse of dimensionality: To address this, can learn WVFs (the composable value functions described in Section 2.2) for eventually achieving each proposition, then compose them to eventually achieve the Boolean expression over the propositions. For example, we can learn WVFs for tasks F F and F However, the product MDP for LTL specified tasks have different states and dynamics (see Definition 2.3). Hence, they do not satisfy the assumptions for zero-shot logical composition (Section 2.2). To address this problem, we define task primitives below. These are product MDPs for achieving each proposition when the agent decides to terminate, and share the same state space and dynamics. We then define skill primitives as their corresponding WVFs.
Temporal curse of dimensionality: To address this, we introduce the concept of constraints C (p p E P} which we use to augment the state space of task primitives". In a given environment, constraint is proposition that an agent may be required to always keep True or always keep False in some FSM state of a temporal logic task. Equivalently, it is a proposition which may never change across the trajectory of the agent in the FSM state. When contradicted it may transition the agent into a failure FSM state (an FSM sink state from which it can never solve the task). For example, require the agent to solve a task F A ( constraint when learning a primitive (e.g achieving )) the agent keeps track (in its pross-pprdduct state) of whether or not it has reached blue region in trajectory that did not start in blue region. That is, in an episode where the agent does not start in a blue region but later goes through a blue region and terminates at a button, the agent will achieve the goal g to, } E 2PuC, We henceforth assume the general case C C- {0 p E }) for our theory, then later consider different choices for C' in our experiments.
some tasks like (F A ((F B)) A (G
while never setting to True (G -)) By setting the O proposition
We now formally define the notions of task primitives and skill primitives such as "Go button": Definition 3.1 (Primitives). Let (S. P. P. L) represent the environment the agent is in, and C be the set of constraints. We define a task primitive here as an MDP M, = (Sg, PG; Rp: 7) with absorbing states 9 2PUC that corresponds to achieving a proposition p E PUC C, where Sg = (S x 2 Ug: Ag = A x Ar, where A, = (0, 1} is an action that terminates the task;
PC po((s, c), (a, a+) = Ul af =1
Rp((s, c) (a, = {
if a, = 1 and p E Uc otherwise
(() otherwise
where s' ~ p(1|s, a). 1= L(s), 1' = [(s'), and d' c (i (
A skill primitive is defined (7, .),9, (a, a,)), the WVF for the task primitive Mp.
The above defines the state space of primitives to be the product of the environment states and the set of constraints, incorporating the set of propositions that are currently true. The action space is aug- mented with terminating action following Barreto et al. (2019) and Nangue Tasse et al. (2020), which indicates that the agent wishes to achieve the goal it currently at, and is similar an option's ''s termi- nation condition (Sutton et al., 1999). The transition dynamics update the environment state and the set of violated constraints e when any other action is taken. Here, the labeling function used to return the set of propositions / and l' achieved in and s' respectively. Any constraint present exclusively in I or is added to c, since it has not been kept always True or always False. Finally, the agent receives reward of 1 when it terminates in state where the proposition p is true, and O otherwise. Figure A7 shows examples of the resulting optimal policies when the set of constraints is empty and non-empty.
Since all task primitives Mg {Mp P E PUC} share the same state space, action space, dynamics, and rewards at non-terminal states, the corresponding skill primitives 2i == {Q Ip E P CC can be composed achieve any Boolean expression over P U C (Nangue Tasse al., 2022a). We next introduce skill machines which leverages skill primitives to encode the solution to temporal logic tasks.
3.2 SKILL MACHINES
We now have agents capable of solving any logical composition of task primitives Mg by learning only their corresponding skill primitives 2¹ and using the zero-shot composition operators (Section 2.2). Given this compositional ability over skills, and reward machines that expose the reward structure
'The notation represents when a literal (a proposition p E P or negation -p) is being used as a constraint. Similarly, we will use P or respectively when the literals in set P or Boolean expression a constraints.
5

---

Published as a conference paper at ICLR 2024
of tasks, agents can solve temporally extended tasks with little no further learning. To achieve this, we define a skill machine (SM) as a representation of logical and temporal knowledge over skills. Definition 3.2 (Skill Machine). Let (8,A, p,7, L) represent the environment the agent is in. and 2g be the corresponding skill primitives with constraints C. Given a reward machine Rs (U, ug. Su, 6,), skill machine is a tuple 2S,A = (L, uo ,q) where bq U + SSg x Ag + IR) is the state-skill function defined by:
óa(u)((s, c) (a, 0j) = max Q²,, geg
and Q: is the composition of skill primitives Lg according to a Boolean expression Ou E 22
For given state S in the environment, the set of constraints violated S C, and state in the skill machine, the skill machine computes a skill 6 (u) e), (a, 0/) that an agent can use to take an action a. The environment then transitions to the next state s' with true propositions l'-where (s', + Po((s, c), (a, 0)) and l' + L(s')-and the skill machine transitions to u' + 6,, This process is illustrated in Figure A8 for the skill machine shown in Figure Remarkably, because the Boolean compositions of skill primitives are optimal, there always exists a choice of skill machine that is optimal with respect to the corresponding reward machine, as shown in Theorem 3.3, which demonstrates that SMs can be used to solve tasks without having to relearn action level policies:
Theorem 3.3. Let πt (s, u) be the optimal policy for a task MT specified by an RM RS..A Then there exists a corresponding skill machine 2sA such that (s, u) E arg max (Q(1) c)2 (a,0))
3.3 FROM REWARD MACHINES TO SKILL MACHINES
In the previous section, we introduced skill machines and showed that they can be used to represent the logical and temporal composition of skills needed solve tasks specified by reward machines. However, we only proved their existence- given task, how can we acquire an SM that solves it?
Zero-shot via planning over the RM: the reward machine (using value iteration, for example) to produce action-values for each transition. We then select skills for each SM state greedily by applying Boolean composition to skill primitives according to the Boolean expressions defining: (i) the transition with the highest value (propositions to eventually satisfy); and (ii) the transitions with zero value (constrains to always satisfy). This process is illustrated by Figure A9. Since the skills per SM state are selected greedily, the policy generated by this SM is recursively optimal (Hutsebaut- Bttssebbut-Buussee et al., 2022) -that is, it is locally optimal (optimal for each sub-task) but may not be globally optimal (optimal for the overall task). Interestingly, we show in Theorem 3.4 that this policy is also satisficing (reaches an accepting state)
To obtain the SM that solves a given RM, we first plan over
(that
if we assume global reachability- all FSM transitions (that is all Boolean expressions E 2²") are achievable from any environment state. This is a more relaxed version of the assumption "any state is reachable from any other state" that is required to prove optimality in most RL algorithms, since an agent cannot learn an optimal policy if there are states it can never reach.
Theorem 3.4. Let RSA = (U, uo Ous 6,) be a satisfiable RM where all the Boolean expressions defining its transitions are in negation normal form (NNF) (Robinson & Voronkov, 2001) ) and are achievable from any state s E S. Define the corresponding SM 2
(U, ug 6u. gQ) with (s) c) (a, 0)) + maxges (oppnaec) ((s, c).g, g. (a, 0)) where op == argmas. Q" (u,o), o), ac = ( Q" (u. 0)= = 0}, and Q" σ) is the optimal Q-function for R...A Then, π T(, u) arg max.maa..... REA (Qs c). (a, 0)) is satisficing.
Theorem 3.4 is critical as provides soundness guarantees, ensuring that the policy derived from the skill machine will always satisfy the task requirements.
Few-shot via RL in the environment: Finally, in cases where the composed skill 0g (u)((s, e), (a, 0))
obtained from the approximate SM is not sufficiently optimal, we can use any off-policy RL. algorithm to learn the task-specific skill QT(s, u, a) few-shot. This is achieved by using the maximising Q- values max (I } in the exploration policy during learning. Here, the discount factor ? determines how much of the composed policy to use. Consider Q-learning, for example: during the e-greedy exploration, we
t arg max max("Qr, (1 7)6q} } to select greedy actions. This improves the initial performance of the agent where 7QT < (1 - -7)0g. and guarantees convergence in the limit of infinite exploration, in vanilla Q-learning. Appendix A.2 illustrates this process.

---

Published as a conference paper at ICLR 2024
4 EXPERIMENTS
We evaluate our approach in three domains, including a high-dimensional, continuous control task. In particular, we consider the Office Gridworld (Figure A2a), the Moving Targets domain (Figure Al) and the Safety Gym domain (Figure 1). We briefly describe the domains and training procedure here, and provide more detail and hyperparameter settings in the appendix.
Office Gridworld (Icarte et al., 2022): Tasks specified over 10 propositions P
+. ,+}} and constraint C (*). We learn the skill primitives 2g (visualised by Figure A3) using goal-oriented Q-learning (Nangue Tasse et al., 2020), where the agent keeps track of reached goals and uses Q-lcarning (Watkins, 1989) to update the WVF with respect to all previously seen goals at every time step.
{A, B, *,
Moving Targets Domain (Nangue Tasse et al., 2020): This is a canonical object collection domain with high dimensional pixel observations (84 x 84 3 RGB images). The agent here needs to pick up objects of various shapes and colours; collected objects respawn at random empty positions similarly previous object collection domains (Barreto al., 2020). There are object colours- ()), and 2 object shapes- (E)), circles (C). The tasks here are defined over blue ,. purple -nd
x O and 5 constraints C = P. We learn the corresponding skill primi- tives with gral-oriented Q-learning but using deep Q-learning (Mnih et al., 2015) to update the WVFss
5 propositions P I
Safety Gym Domain (Ray et al., 2019): A continuous state and action space (S = R A = IR3) domain where an agent, represented by a point mass, must navigate to various regions defined by propositions (P= (0. o. corresponding to its LiDAR sensors for the red cylinder the green buttons . and the blue regions We learn the four skill primitives corresponding to each predicate
(with constraints C = }), using goal-oriented Q-learning and TD3 (Fujimoto et al., 2018).
4.1
ZERO-SHOT AND FEW-SHOT TEMPORAL LOGICS
Task
Description - LTL
Deliver coffee to the office without breaking decorations (F A X
A AG -*)
Patrol rooms A, B, C, and D without breaking any decoration
(F (A X (F (B A X (F (C A X (FD)))))) A -X)
3 Deliver coffee and mail to the office without breaking any decoration
((F A X (F [ A (F))))) V (F (E3 A A (F ( X (Fi)
(G-*)
Deliver mail to the office until there is mail left, then deliver coffee office while there are people in the office, then patrol rooms A-B-C-D-
and never break a decoration
(F (1 X EU M
A X A X (F A X (-ÚU
A
FF
(G *)
Table 1: Tasks in the Office Gridworld. The RMs are generated from the LTL expressions.
We use the Office Gridworld as multitask domain, and evaluate how long it takes an agent to learn a policy that can solve the four tasks described in Table 1. The tasks are sampled uniformly at random for each episode. In all of our experiments, we compare the performance of SMs without further learning and SMs paired with Q-learning (QL-SM) with that of regular Q-learning (QL) and the following state-of-the-ar RM-based baselines (Icarte et al., 2022): (i) Counterfactual RMs (CRM): This augments Q-learning by updating the action-value function at each state (Q(s, u, a)) not just with respect to the current RM transition, but also with respect to all possible RM transitions from the current environment state. This is representative of approaches that leverage the compositional struc- ture of RMs to learn optimal policies efficiently. (ii) Hierarchical RMs (HRM): The agent here uses Q-learning to learn options to achieve each RM state-transition, and an option policy to select which options to use at each RM state that are grounded in the environmen states. This is representative of option-basee based approaches that learn deerarchiallly-optin (QL-RS, CRM-RS, HRM-RS): The agent here uses the values obtained from value iteration over the RMs for reward shaping, on top of the regular QL, CRM, HRM algorithms. This is representative of approaches that leverage planning over the RM to speed up learning.
policies. (iii) Reward-shaped variants
7

---

Published as a conference paper at ICLR 2024
12:0
030
330
300
Tota
290
450
100
230
190
14
04
25
60
25
20
105
65
34 45
20
10
85
22
25
24
45
26
165
(a) Task
(b) Task
(c) Task 4
(d) Multiple tasks (1-4)
Figure 2: Average returns over 60 independent runs during training in the Office Gridworid. The shaded regions represent I standard deviation. For each training run, we evaluate the agent e-greedily (c (c= 0.1) after every 1000 step and report the average total rewards obtained over each 40 consecutive evaluation. The black dotted line indicate the point at which the baselines have trained for the same number of time steps as the skill primitives pretraining.
In addition to learning all four tasks at once, we also experiment with Tasks 1, and 4 in isolation. In these single-task domains, the difference between the baselines and our approach should be more pronounced, since QL, CRM and HRM now cannot leverage the shared experience across multiple tasks. Thus, the comparison between multi-task and single-task learning in this setting will evaluate the benefit the compositionality afforded by SMs, given that the 11 skill primitives used by the SMs here are pretrained only once for 1 10y time steps and used for all four experiments. For fairness towards the baselines, we run each of the four experiments for 4 x 10t time steps.
The results of these four experiments are shown in Figure 2. Regular Q-learing struggles to learn Task 3 and completely fails to learn the hardest task (Task 4). Additionally, notice that while QL and CRM can theoretically learn the tasks optimally given infinite time, only HRM, SM, and QL-SM are able to learn hard long horizon tasks in practice (like task 4). This is because of the temporal composition of skills leveraged in HRM, SM, and QL-SM. In addition, the skill machines are being used to zero-shot generalise to the office tasks using skill primitives. Thus using the skill machines alone (SM in Figure 2) may provide sub-optimal performance compared to the saekispecific agents, since the SMs have not been trained to optimality and are not specialised to the domain. Even under these conditions, we observe that SMs perform near-optimally in terms of final performance, and due to the amortised nature of learning the WVF will achieve its final rewards from the first epoch.
Finally, it is apparent from the results shown in Figure 2 that SMs paired with Q-learning (QL-SM) achieve the best performance when the zero-shot performance is not already optimal (see Appendix A4 for the trajectories of the agent with and without few-shot learning). Additionally, SMs with Q-learning always begin with significantly higher reward and converge their final performance faster than all baselines. The speed of learning is due to the compositionality of the skill primitives with SMs, and the high final performance is due the generality of the learned primitives being paired with the domain-specific Q-learner. In sum, skill machines provide fast composition of skills and achieve optimal performance compared to all benchmarks when paired with learning algorithm.
4.2 ZERO-SHOT TRANSFER WITH FUNCTION APPROXIMATION
We now demonstrate our temporal logic composition approach in the Moving Targets domain where function approximation is required. Figure 3 shows the average returns of the optimal policies and SM policies for the four tasks described in Table 2 with a maximum of 50 steps per episode. Our results show that even when using function approximation with sub-optimal skill primitives, the zero-shot policies obtained from skill machines are very close to optimal on average. We also observe that for very challenging tasks like Tasks 3 and (where the agent must satisfy difficult temporal constraints), the compounding effect of the sub-optimal policies sometimes leads to failures. Finally, we provide a qualitative demonstration of our method's applicability to continuous control tasks using Safety Gym, a benchmark domain used for developing safe RL methods (Ray et al., 2019). We define set of increasingly complex tasks and visualise the resulting trajectories after composing the agent's '' learned primitive skills. Figure illustrates the trajectory that satisfies the task requiring the agent to navigate to a blue region, then to a red cylinder, and finally to another red cylinder while avoiding blue regions. See Appendix A.5 for all task specifications and trajectory visualisations.
8

---

Published as a conference paper at ICLR 2024
Task
Description - LTL
Optimal
Pick up any object. Repeat this forever.
40
Composed
F (O V []) Pick up blue then purple objects, then ob-
Average Returns
Random
2
30
jects that are neither blue nor purple. Re-
peat this forever.
F
X
20
(F [)) A
Pick up blue objects or squares, but never blue squares. Repeat this forever.
10
(F( V Ed) A (G
A EJ)
4 Pick non-square blue objects, then non-
blue squares that order. Repeat this for-
1 Tasks
2
3
4
ever F((-OA A X
Table 2: Tasks in the Moving Targets domain. To repeat forever, the terminal states of the RMs gener- ated from LTL are removed, and transitions them are looped back to the start state.
Figure Average returns over 100 runs for tasks in Table 2. The agent and object posi- tions are randomised and objects respawn in random positions when collected.
RELATED WORK
Regularisation has previously been used to achieve semantically meaningful disjunction (Todorov, 2009; Van Nickerk et al., 2019) or conjunction (Haarnoja et al., 2018; Hunt et al., 2019). Weighted composition has also been demonstrated; for example, Peng et (2019) learn weights to compose existing policies multiplicatively to solve new tasks. Approaches built on successor features (SF) are capable of solving tasks defined by linear preferences over features (Barreto al., 2020)., while Alver & Precup (2022) show that SF basis can be learned that is sufficient to span the space of tasks under consideration. By contrast, our framework allows for both spatial composition (including operators such negation that others do not support) and temporal composition such LTL.
popular way of achieving temporal composition is through the options framework (Sutton et al., 1999). Here, high-level skills are first discovered and then executed sequentially to solve task (Konidaris Barto, 2009). Barreto et al. (2019) leverage the SF and options framework and learn how to linearly combine skills, chaining them sequentially to solve temporal tasks. However, these approaches offer a relatively simple form of temporal composition. By contrast, we are able to solve tasks expressed through regular languages zero-shot, while providing soundness guarantees.
Approaches to defining tasks using human-readable logic operators also exist. Li et al. (2017) and Littman (2017) specify tasks using LTL, which is then used generate reward signal for an RL agent. Camacho et al. (2019) perform reward shaping given LTL specifications, while Jothimurugan al. (2019) develop formal language that encodes tasks as sequences, conjunctions and disjunctions of subtasks. This is then used to obtain shaped reward function that can be used for learning. These approaches focus on how to improve learning given such specifications, but we show how an explicitly compositional agent can immediately solve such tasks using WVFs without further learning.
CONCLUSION
We proposed skill machines-fing state machines that can be learned from reward machines that allow agents to solve extremely complex tasks involving temporal and spatial composition. We demon- strated how skills can be learned and encoded in specific form of goal-oriented value function that, when combined with the learned skill machines, are sufficient for solving subsequent tasks without further learning- Our approach guarantees that the resulting policy adheres the logical task specifi- cation, which provides assurances of safety and verifiability to the agent's decision making, important characteristics that are necessary if we are ever deploy RL agents the real world. While the resulting behaviour is provably satisficing, empirical results demonstrate that the agent's 's performance near optimal; further nunittnnng can be performed should optimality be required, which greatly im- proves the sample efficiency. We see this approach as a step towards truly generally intelligent agents, capable of immediately solving human -aena---eeiiiablee tasks the real world with further learning.

---

Published as a conference paper at ICLR 2024
ACKNOW
Computations were performed using the High Performance Computing Infrastructure provided by the Mathematical Sciences Support unit at the University of the Witwatersrand. G.N.T. is supported by an IBM PhD Fellowship. D.J. is a Google PhD Fellow and Commonwealth Scholar. B.R. is CIFAR Azrieli Global Scholar the Learning in Machines & Brains program.
REFERENCES
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Safa Alver and Doina Precup. Constructing good behavior basis for transfer using generalized policy updates. In International Conference on Learning Representations, 2022.
Brandon Araki, Xiao Li, Kiran Vodrahalli, Jonathan DeCastro, Micah Fry, and Daniela Rus. The logical options framework. In International Conference on Machine Learning, pp. 307-317.
PMLR, 2021.
Jose Arjona-Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brandstetter, and Sepp Hochreiter. Rudder: Return decomposition for delayed rewards. Advances in Neural Information Processing Systems, 32, 2019.
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the Atari human benchmark. In International Conference on Machine Learning, pp. 507-517, 2020.
Andre Barreto, Diana Borsa, John Quan, Tom Schaul, David Silver, Matteo Hessel, Daniel Mankowitz, Augustin Zidek, and Remi Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In International Conference on Machine Learning, pp. 501- 510. PMLR, 2018
André Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygün, Philippe Hamel, Daniel Toyama, Shibl Mourad, David Silver, Doina Precup, et The option keyboard: Combining skills in reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117 (48):30079-30087, 2020.
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A Mcllraith. Lt and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI, volume 19, pp. 6065-6073. 2019.
Vanya Cohen, Geraud Nangue Tasse, Nakul Gopalan, Steven James, Matthew Gombolay, and Benjamin Rosman. Learning to follow language instructions with compositional policies. In AAAI Fall Symposium Series, 2021.
Vanya Cohen, Geraud Nangue Tasse, Nakul Gopalan, Steven James, Ray Mooney, and Benjamin Rosman. End-to-end learning to follow language instructions with compositional policies. In Workshop Language and Robotics at CoRL 2022, 2022.
Alexandre Duret-Lutz, Alexandre Lewkowicz, Amaury Fauchille, Thibaud Michaud, Etienne Renault, and Laurent Xu. Spot 2.0 framework for Itl and w-automata manipulation. In International Symposium on Automated Technology for Verification and Analysis, pp. 122-129. Springer, 2016.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pp. 1587-1596. PMLR, 2018.
Tuomas Haarnoja, Vitchyr Pong, Aurick Zhou, Murtaza Dalal, Pieter Abbeel, and Sergey Levine. Composable deep reinforcement learning for robotic manipulation. In 2018 IEEE International Conference Robotics and Automation, pp. 6244 6251, 2018.
10

---

Published as a conference paper at ICLR 2024
Jonathan Hunt, Andre Barreto, Timothy Lillicrap, and Nicolas Heess. Composing entropic policies using divergence correction. In Interaational Conference on Machine Learning, pp. 2911-2920, 2019.
Matthias Hutsebaut-Buysse Kevin Mets, and Steven Latré. Hierarchical reinforcement learning: A survey and open research challenges. Machine Learning and Knowledge Extraction, 4(1):172-221, 2022.
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith, Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning, pp. 2107-2116 16, 201
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning, pp. 2107-2116. PMLR, 2018b.
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 2022.
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. Advances Neural Information Processing Systems, 32, 2019.
Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforce- ment learning from logical specifications. Advances in Neural Information Processing Systems, 34: 10026-10039, 2021.
George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. Advances in Neural Information Processing Systems, 22, 2009.
Orna Kupferman and Moshe Y Vardi. Model checking of safety properties. Formal methods in system design, 19:291-311 -144, 2001.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-137,, 2016.
Xiao Li, Cristian-loan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3834-3839 2017.
Michael Littman, Ufuk Topcu, Jie Fu, Charles Isbell, Min Wen, and James MacGlashan. Environment- independent task specifications via GLTL. arXiv preprint 1rXiv:1704.044 2017.
Jason Xinyu Liu, Ankit Shah, Eric Rosen, George Konidaris, and Stefanie Tellex. Skill transfer for temporally exxeende task specifications. arXiv preprint (txXix:22260000996 2022.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Marc Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Geraud Nangue Tasse, Steven James, and Benjamin Rosman. A Boolean task algebra for reinforce- ment learning. Advances in Neural Information Processing Systems, 33:9497- 9507, 2020.
Geraud Nangue Tasse, Steven James, and Benjamin Rosman. Generalisation in lifelong reinforcement learning through logical composition. In International Conference on Learning Representations, 2022a.
Geraud Nangue Tasse, Steven James, and Benjamin Rosman. World value functions: Knowledge representation for multitask reinforcement learning. The Sth Multi-disciplinary Conference on Reinforcement Learning and Decision Making (RLDM), 2022b.
Xue Bin Peng, Michael Chang, Grace Zhang, Pieter Abbeel, and Sergey Levine. MCP: Learning composable hierarchical control with multiplicative compositional policies. Advances in Neural Information Processing Systemx, pp. 3686-3697, 2019.

---

Published as a conference paper at ICLR 2024
Amir Pnueli. The temporal logic of programs. In 18th Annual Symposium Foundations of Computer Science, pp. 46-57. IEEE, 1977.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement tearning.(2019) OpenAI, 2019.
Alan JA Robinson and Andrei Voronkov. Handbook of automated reasoning, volume 1. Elsevier, 2001.
Richard Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2)1811-111, 1999.
Matthew. Taylor and Peter Stone. Transfer learning for reinforcement learning domains: a survey. Journal of Machine Learning Research, 10:1633-1685, 2009.
Emanuel Todorov. Compositionality of optimal control laws. In Advances in Neural Information Processing Systems, pp. 11856-1864 2009.
Pashootan Vaezipoor, Andrew C Li, Rodrigo A Toro Icarte, and Sheila A Mcilraith. Lilaccion: Generalizing instructions for multi-task rl. International Conference on Machine Learning, pp. 10497-10508. PMLR, 2021.
Benjamin Van Niekerk, Steven James, Adam Earle, and Benjamin Rosman. Composing value functions in reinforcement learning. In International Conference on Machine Learning, pp. 6401-6409, 2019.
C. Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
A APPENDIX
A.1 PROOFS OF THEORETICAL RESULTS
Theorem A.1. Let (s, u) be the optimal policy for a task My specified by an RM RS Then there exists corresponding skill machine 2s.AA such that
π T"(s, u) E arg max (1, ())
aeA
Proof. Define the skill per SM state Q" to be the Boolean composition of skill primitives that satisfy the set of propositions g E 2PUC where g is the set of propositions satisfied and constraints violated when following π (s, u). Then x (s, u) E arg max (s) c), (a, 0)) since Q; is optimal using Nangue Tasse et al. (2022b) and optimal policies maximise the probability reaching goals (since the rewards are non-zero only at the desirable goal states, where they are 1).
Theorem A.2. Let RSA (U1 un, du; 5e) be a satisfable RM where all the Boolean expressions o defining its transitions are in negation normal form (NNF) (Robinson & Voronkov, 2001) and are achievable from any state & E S. Define the corresponding SM 2 (M, ug: 8uz 82) with dQ (u)(((s( c) (a, 0}) + maxgeg Q QippArcc) ((, c),g, g, (a, 0)) where op argmar, Q"(u,o) de + V(ā (u. = 0}. and Q" Qu(u, о) the optimal Q-function for RSA- Then, < u) arg max (Q( c). (a, 0)) is satisficing.
Proof. This follows from the optimality of Boolean skill composition and the optimality of value iteration, since each transition of the RM is satisfiable from any environment state.
12

---

Published as a conference paper at ICLR 2024
A.2 FULL PSEUDO-CODES OF FRAMEWORK
Algorithm 1: Q-learning for skill primitives
Input :S,A,,, C, RMAX- = 1, RMIN =0 Initialise: QMAX (s8, c) 9, (a, (z)) and QarIN((s, c), 9, (a, a,)), goal buffer G (0)
foreach episode do
Observe initial state E S and true propositions E 2", sample E 2 and E G
while episode is not done do
arg max QMAX ((8, c) g, (a, (r)) (a.a,)
if Bernoulli(1 -
(0, a,)
sample (a, a-) E A 1)
otherwise
Execute a and observe next state s' and true propositions l'
Get true constraints d' k- cu if (a, 1) then G < G U Ut'
foreach E {Q (QMax: QMINN do if (a, * 1) then <- 0 if (a, = and Q QмAX) then <- RMAX
10
if (a,, and Q QMIN) then RMIN
12
foreach g' G do
< RMIN if (a, and g' + U) elser
14
if (s' is terminal or a, = 1) then
Q((s,)), ())a,)) f
15
16
else
Q((s,c) I' (a, a,) -t [ m ((( (d' (d))
17
18
8 + s' and c t
if (a, 1) then terminate episode
2g +- 0
21 foreach p E PUC
(p .), (a, a,) Quax((ssch
else QMsNn((,,)).00 (a,a)))
23
2g + 2g [[pp)
24 return 2g
Algorithm 2:
Skill machine from reward machine
Input Qg. (14, wo, 8n, ) Initialise RM value function Q(u, o),, value iteration error A Let B(u) the set of Boolean expressions defining the RM transitions d (u, :)
/* Value iteration
while A > do
- 0
for E 4 do
for a E B(u) do
v' + (u, σ) + max ((6,(u,)),
A = max A (Q - 0'}
Q(u,a)+ t
/* Skill machine's s skill function
10 for E U do
11 Op, Te t argmaaa o'), V(ō Q(u, = 0}
12 QopA-ac composition of 2g as per the Boolean expression dp -
d (a,0)) t maxgeg Qo c). ().
14 return (11 uo, da 62)
13

---

Published as a conference paper at ICLR 2024
Algorithm 3: Zero-shot and Few-shot Q-learning with skill machines
Input
:S.A,P, (M,, un, ou, oQ); 7, Initialise: Q(..u.0) 0. foreach episode do
Observe initial state s E S and propositions E 2", RM state +- uo and constraints e +- while episode is not done do
if zero-shot then - arg.mmm max c)), (),
else
/ Fewshot by using do in the behaviour policy
*/
+
arg max (max u, a), (0000)0)))))(()))))))))))))))))) (a, if Bernoulli(1 -))
sample E A
otherwise
Take action and observe the next state s' and true propositions /'
Get reward r <- 5, (+) 8'), true constraints c <- cu = nc). and the next RM state u' (u,
if u o u' then e +- 0 if s' u' is terminal then Q(s, uuuaa a)
12
13
else
Q(s,u,a a) & max Q(s ((s', + 8 and u w
15
A.3 DETAILS OF EXPERIMENTAL SETTINGS
In this section we elaborate further on the hyper- parereaaameterss for the various experiments in Section 4. also describe the pretraining of WVFs for all the experimental settings which corresponds to learning the task primitives for each domain. The same hyper-parameters are used for all algorithms in a particular experiment. This is to ensure that we evaluate the relative performance fairly and for the Office World, Moving Targets and SafeAl Gym
consistently. The full list of domain experiments are shown Tables A 1-A33 respectively.
Hyper- papee-paremeter
Value
Timesteps
le
Training exploration (c)
0.5
Per-episode evaluation exploration (e)
0.1
Discount Factor (7)
0.9
Table A1: Table of parameearssesers used for Q-learning in the Office World experiments.
To use skill machines we require pre-trained WVFs. As mentioned above, all WVFs are trained using the same hyper-parameters any other training. Additionally, for all experiments the WVFs are pre-trained on the base task primitives for the domain. For example, in the Office World domain, the WVFs are trained on the [P C base task primitives corresponding to achieving each predicate, p {A, B, C, D. *
# (reaching states the predicate is set True),
with constraints C } All other primitives in this domain can be obtained zero-shot through value function composition. Similarly, for the moving targets domain (Figure A1), the WVFs are pre-trained on the primitives corresponding to obtaining objects by shape or colour in the environment separately, P P= (C, X, OJ, with constraints C C= P. From here the value functions for finding objects of particular colours or any more complex primitives can be composed zero-shot. Finally, for the SafeAI Gym environment the base skill primitives correspond to going to a cylinder
button and blue region
O):
trained with constraints C
14

---

Published as a conference paper at ICLR 2024
Hyper-parameter
Value
Timesteps
1
Neural Network architecture
CNN + MLP
CNN architecture
Defaults of Mnih et al. (2015)
MLP hidden layers
1024 x 1024 x 1024
Start exploration (e)
1
End exploration (e)
0.1
Exploration decay duration (6)
5e
Discount Factor (7)
0.99
Others
Defaults of Mnih et al. (2015)
Table A2: Table of hyper- parametesss used for Deep Q-learning in the Moving Targets experiments.
eyper-parameter
Value
Timesteps
1e
Neural Network architecture
MLP
MLP hidden layers
2024 2024 x 2024
Max episodes length
100
Target noise
0.2
Action noise
0.2
Discount Factor (r)
0.99
Others
Defaults of Achiam (2018)
Table A3: Table of parameerrsmeters used for the TD3 in the SafeAI Gym experiments.
Figure A1: Moving Targets domain
A.4 OFFICE GRIDWORLD ADDITIONAL EXPERIMENTS AND FIGURES
We illustrate the environment and an example temporal logic task in it in Figure A2. In this environ- ment, an agent (blue circle) can move to adjacent cells in any of the cardinal directions (IA) = 4) and observe its (x, y) position (SS) = 120). Cells marked de X and & respectively represent the coffee, mail, and office locations. Those marked * indicate decorations that are broken if the agent collides with them, and A-D indicate the corner rooms. The reward machines that specify tasks in this envi- ronment defined over 10 propositions: P {A, B, C, D. * de [x i. ba propositions are true when the agent at their respective locations, pa is true when the agent is at [x]
}. where the first
and there is mail to be collected, and + is true when the agent is $ and there is someone in the office.
15

---

Published as a conference paper at ICLR 2024
( A +0.00
4 1 9g
9p--9.--0 48
(M:0) 01 (e
fog -0,0)
A
+0.10
OW.
18-- -
(- - A-8,
(HESA -0,0)
Og
44-
46g
-DEA
(a) Office Gridworld
(b) Reward Machine
(c) Skill Machine
Figure A2: Illustration of (a) the office gridworld where the blue circle repre- sents the agent; (b) the reward machine for the task "deliver coffee and mail the office without breaking any decoration", given by the LIL specification ((F A (F ( (
A (F (x+())))) A (G-*); (c) the
skill machine obtained from the reward machine which can then be used to achieve the task specification zero-shot the red trajectory in (a). The nodes labeled t represent terminal states.
(a) Room A
(b) Room B
(c) Room C
(d) Room D
(e) Decoration #
(I) Coffee
(g) Mail XX
(h) Office
(i) Mails present
x
(i People present
(k) Decoration constraint *
Figure A3: The policies (arrows) and value functions (heat map) of the primitive tasks in the Office Gridworld. These are obtained by maximising over the goals of the learned WVFs.
Figure A3 shows the skill primitives learned for each proposition in the environment, and Figure A4 shows the trajectories of our zero-shot agent (SM) and few-shot agent (QL-SM) for various tasks. Finally, run 2 experiments demonstrate the performance of our zero-shot and few-shot approach when the global reachability assumption does not hold.
When the reachability assumption is not satisfied in some initial states: In the first experiment (Figure A5), the agent needs to solve task I of Table I ((F( de ^ X +))) A (G ))), but we modify the environment such that one of the coffee locations is absorbing (a sink environment state). This breaks the global reachability assumption since the agent can no longer reach the office location after reaches the absorbing coffee location. As result, observe that the zero-shot agent (SM) is even sub-optimal than before
16

---

Published as a conference paper at ICLR 2024
because it cannot satisfy the task when it starts locations that closer to the absorbing coffee location. However, we can observe that the few-shot agent (QL-SM) is still able to learn the optimal policy, starting with the same performance as the zero-shot agent. Note that the hierarchical agent (HRM) also converges to the same performance as our zero-shot agent because it also tries to reach the nearest coffee location.
2. When the reachability assumption is not satisfied in all initial states: In the second experi- ment (Figure A6), the agent needs to solve the task with LTL specification (F )( the environment is still modified such that one of the coffee locations is absorbing. Here, the Boolean expression
)-
not satisfiable since there is no state where both propositions and ) are true. Hence, this can be seen the worst-case scenario for approach (without outright making the task unsatisfiable), since A the Boolean expression greedily selected in the starting RM state. As result, our zero-shot agent completely fails to solve this task. Even in this case, we can observe that the few-shot agent is still able to learn the optimal policy.
B
B
*
#
(a) Task zcro-shot (SM)
(b) Task few-shot (QL-SM)
*
B
*
*
*
*
Task zero-shot (SM)
(d) Task few-shot (QL-SM)
A
B
A
*
*
*
*
(c) Task 3 zero-shot (SM)
Task few-shot (QL-SM)
Figure A4: Agent trajectories for various tasks in the Office Gridworld (Table 1) using the skill machine without further learning (left) and with further learning (right).
17

---

Published as a conference paper at ICLR 2024
start
start
start
(#,00 0
( -xt
0.81)
A-# .0)
A-88, 0.9)
A +
(- A - 0)
U1
(#,00)
# 0.9)
($,0)
Mt
A- -.,1) 1)
m
(a) Reward machine
(b) Value iterated RM
(c) Skill machine
1750
Reward
3250
SM (Curd)
QU-sh IDuns
790
*
SV
BR
*
320
230
Steps
(d) Average Returns
(c) Zero-shot (SM)
(f) Few-shot (QL-SM)
when the global reachability assumption does hold. Here, the Office Gridworld is modified such that the position of the lower right coffee (the red cell) is made absorbing (the agent can not leave that state after reaching
Figure A5: Results for the task with LTL specification (F A (F (F)))) A -*)
it). We show: (a) the reward machine for the task, (b) the value iterated reward machine (using
0.9), (c) the resulting skill machine, (d) the resulting average returns compared to the baselines,
(e) sample trajectories of the zero-shot agent, and (f) sample trajectory of the few-shot agent.
start
start
start
0)
(- 0.9)
0.9)
( 1>
( 1)
(-$.0)
( 0.9)
U1
(a) Reward machine
(b) Value iterated RM
(c) Skill machine
1202
5M (Ount
*
B
B
Total Reward
802
OU.S rours)
CRH
CRMs4S
002
Steps
1es
(d) Average Returns
(e) Zero-shot (SM)
(f) Few-shot (QL-SM)
where the global reachability assumption not satisfied. Here, the Office Gridworld modified such that the position the lower right coffee (the red cell) is made absorbing. We show (a) the RM for the task, (b) the value iterated RM (using 7 = 0.9), (c) the resulting SM, (d) the resulting average returns compared to the baselines, (c) sample trajectories of the zero-shot agent, and (f) sample trajectory of the few-shot agent.
Figure A6: Results for the task with LTL specification (F A
18

---

Published as a conference paper at ICLR 2024
A.5 FUNCTION APPROXIMATION WITH CONTINUOUS ACTIONS AND STATES
We demonstrate our temporal logic composition approach in a Safety Gym domain (Ray et al., 2019) which has continuous state space (S IR and continuous action space (A = R²). The agent here point mass that needs navigate to various regions defined by 3 propositions (P and the blue
O))
corresponding to its lidar sensors for the red cylinder (0), the green buttons regions (O). The agent, 4 buttons and 2 blue regions randomly placed on the plane. The cylinder randomly placed on one of the buttons. We first learn the 4 base skill primitives corresponding to
each predicate (with constraints C IO), with goal-oriented Q-learning Nangue Tasse al. (2020) but using Twin Delayed DDPG (Fujimoto et al., 2018) to update the WVFs. Figure A10 shows the trajectories of the SM policies for the six tasks described in Table A4. Our results shows that skill primitives can be leveraged to achieve zero-shot temporal logics even in continuous domains.
-M
(c) M
M
M-
(d) M
A-M
^-M
g
g
Figure A7: Effect of constraints on primitives (C H). We show compositions of task primitives (for example M ~ where the agent needs to achieve (g), and reward obtained when following: (a-c) Optimal policies; and (d) non-optimal policy.
trajectories, goal reached
start
(a) Skill machine
(b) c = 0.
0.
Qu.
(c)
c=
1= A
Qo.
(d) 0, episode terminates
Q
Figure A8: Execution of a skill machine the Safety Gym domain. (a) An example skill machine;
(b) A snapshot of the environment the initial state. In this state, constraint has been reached (c = 0), no proposition is true (1 0), the SM is at state u un, and the composed skill outputted (which the agent
by the SM is Q
in the environment); (c)
The trajectory of the agent until it achieves
-A-OA - In the current environment state, constraint has been reached (c (c=00 0). the agent is at a green button (1 = {0)), the SM transitions to u1, and the composed skill outputted by the SM is Q
-QQ (which
the agent uses to act in the environment); (d) The trajectory of the agent until the agent achieves In the current environment state, no constraint has been reached (c 0), the agent at the red cylinder and green button (I )),, the SM transitions to the terminal state t, and the episode terminates.
19

---

Published as a conference paper at ICLR 2024
start
start
start
Fo 0)
(-a 0.0.11
Ho Q
(oA
(.A.9.0..)
A
A -0000000000
C
0.9)
Mr
(a) Reward machine
(b) Value iterated RM
(c) Skill machine
Figure A9: The reward machine, value iterated reward machine (using = 0.9) and skill machine for the task with LTL specification to achieve op A -c
AG -O). The agent composes its skill primitives
at ug and op -c
at U1
Task
Description
LTL
Navigate to a button and then to a cylinder. - (F(o A X O))
Navigate to button and then cylinder while never entering blue regions
(F X (F O)) A (G
3 Navigate to button, then to cylinder without entering blue regions, then to button inside blue region, and finally to a cylinder again.
F ((F
A (F((
O) A (
Navigate to a button and then to a cylinder in a blue region. - (F A (
O)))
Navigate to cylinder, then to button in blue region, and finally cylinder again.
(FCC ( ((O
A X ()))
Navigate to a blue region, then to a button with a cylinder, and finally to a cylinder while
avoiding blue regions. - (F( A X(F(( ( A (G
Table A4: Tasks in the Safety Gym domains. The RMs generated from the LTL expressions.
(a) Task
(b) Task
(c) Task 3
(d) Task
(e) Task
(i) Task
Figure A A10: Visualisations of the trajectories obtained by following the zero-shot composed policies from the skill machine for tasks Table A4.
20


Reviews:
[{"review_id": "1opaO6tCk8", "reviewer": "Reviewer_uyfa", "summary": "This paper introduces the skill machines formalism. This is a variant of the reward machine formalisms where the agent learns Q-functions to satisfy individual task propositions, and then plans a temporal sequence of proposition states to be achieved through value iteration over the skill machine. Once the optimal path through the reward machine is found, the authors propose to use logical Q-function approximation from prior work to initialize the global semi-markov decision process Q-function. The initial policy can serve as a good zero-shot approximation to a satisficing policy. While the Q-function can also be optimized through exploration to generate a hierarchically optimal solution for the overall problem. \n\nThe key assumption in this problem is that all reward machine transitions are possible from all given reward machine states. Such as assumption is usually satsified when the domain involved proposition encoded as occupying certain regions of the state-space. It is definitely true if the propositions cover non-overlapping regions, but I am less certain if the assumption holds when there are overlapping regions as well. Nevertheless, the authors do clearly state the requisite assumption for the validity of their proposed approach.", "questions": "Please refer to the weakness section", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality, and significance**: The paper makes a significant contribution by providing an approach to compose skills both through proposition logic and temporal operators. This is quite a unique capability, and many works have proposed partial solutions for the same. The ideas, and evaluations presented in this work are quite compelling, and are theoretically sound. There are some claims that need to be examined in a greater detail as listed in the weakness and limitations sections, but nonetheless the paper is a significant advance.\n\n**Evaluations**: The authors decision to push the complexity of the task specification must be commended. This evaluation explicitly tests for upward generalization capabilities. This can and should be strengthened by randomly sampling LTL goals from predefined distributions over specifications with a rejection sampling approach for unsatisfiable specifications, however, I am convinced regarding the validity of the approach from the theoretical arguments presented in the paper, and the scrupulous evaluations over varying complexity formulas.\n\n**Comparison to prior LTL-based transfer approaches**: The comparison with prior approaches and the explanations of the key differences in capabilities is much appreciated.", "weaknesses": "**Environment validity:** The assumption of task satisfiability, and proposition transition reachability are quire strong. It is unclear what the test for whether an environment satisfies the assumptions required by the approach. The authors can ameliorate this by either providing domains where these assumptions always hold (environments where propositions encode visiting specific regions, and there being no overlap between propositions is one such environment), and they can also specifically search for a violating environment specification pair, and demonstrate what their approach outputs in that case. This information will be valuable to practitioners who would like to utilize skill machines.\n\n**Relative expressivity of RMs vs LTL**: I believe that only a fragment of LTL can be translated into a reward machines, and there exist reward machines that cannot be expressed through an LTL formula. I would suggest the authors to appropriately restrict the LTL formula class they allow as input to the model to a fragment of LTL that is known to be expressible as a reward machine. (I believe the obligations segment)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qcIOVR7BiW", "reviewer": "Reviewer_vdA3", "summary": "This paper points out that a large number of combinations of high-level goals can lead to the curse of dimensionality. To address this issue, this paper presents skill machines, which flexibly compose a set of skill primitives both logically and temporally to obtain near-optimal behaviors. This paper demonstrates that skill machines can map complex temporal logic task specifications to near-optimal behaviors, which are sufficient for solving subsequent tasks without further learning.", "questions": "1. How are different tasks specifically set in each benchmark? Why does the agent achieve zero-shot performance?\n\n2. The policy generated by Skill Machine (SM) may be locally optimal, so Theorem 3.4 assumes global reachability and the policy is satisficing. There may be enough combinations of skills to approach this assumption, but it will limit the agent's exploration ability. And what is the approximate performance gap when certain states are unreachable?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The motivation for this paper is quite sound. The agent begins by converting the LTL task specification into a reward machine (RM) and proceeds to determine the suitable spatial skill for each temporal node through value iteration. It also composes its skill primitives into spatial skills, effectively forming a skill machine. Finally, the agent applies these skills to solve the task without requiring additional learning.", "weaknesses": "One weakness of the paper lies in its relatively complex non-end-to-end training process. More precisely, it necessitates reinforcement learning training for acquiring skill primitives and additional value iteration for the selection of appropriate spatial skills. Another potential limitation is its applicability, which may be more suited to navigation scenarios. It requires different linear temporal logic (LTL) task specifications tailored to specific application scenarios, potentially leading to challenges in generalization across various scenarios. What’s more, the descriptions of definitions 3.1 and 3.2 are not clear enough and lack some corresponding explanations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BrYRvfiKxT", "reviewer": "Reviewer_pDWg", "summary": "The paper introduces skill machines, which are finite state machines derived from reward machines, enabling agents to tackle complex tasks involving temporal and spatial composition. These skills are encoded in a specialized goal-oriented value function. By combining these learned skills with the value functions, downstream tasks can be solved without additional learning. Importantly, this method guarantees that the resulting policy aligns with the logical task specification. The behavior generated is provably satisficing, with empirical evidence indicating performance close to optimality. The paper suggests that further fine-tuning can enhance sample efficiency if optimal performance is required.", "questions": "* In Sec 2.2, $\\pi^\\ast(s) \\in arg max_a max_g \\bar{Q^\\ast}(s, g, a)$.  I would appreciate clarification regarding the reward function associated with the policy $\\pi^\\ast$. Does this imply that the policy is considered successful whenever it reaches any goal $g$ within the goal space?\n\n* In Definition 3.1, what is the purpose of tracking $c$ as a history of safety violation to constraints in $\\mathcal{C}$?\n\n* In the work by Nangue Tasse et al. (2020), the reward function for a skill specifies that if the agent enters a terminal state corresponding to a different task, it should incur the most substantial penalty possible. I am curious why this aspect is omitted in Definition 3.1.\n\n* At state $u$ in a skill machine, it computes a skill $\\delta Q(u)(\\langle s, c\\rangle,\\langle a, 0 \\rangle) \\mapsto max_g \n\\bar{Q}^\\ast_u (\\langle s, c \\rangle, g, \\langle a, 0 \\rangle)$ that an agent can\nuse to take an action $a$.  Is it necessary for this skill to enumerate the entire goal space? At every state within the skill machine, you have already derived a Boolean combination of primitive Q functions concerning specific goals. For instance, in $u_0$ from Fig. 1, the relevant goals include the green button and the blue region. Could we potentially use the green button directly as the goal for Q_button and the blue region as the goal for Q_blue, thereby bypassing the need to exhaustively enumerate all possible goals?\n\n* Relatedly, in the scenario where the goal space is continuous, how does the algorithm determine the optimal value for $g$?\n\n* As per Definition 3.1, each skill is associated with a sub-goal. However, in the context of few-shot learning, what constitutes the goal for a newly acquired skill?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper showcases the development of an agent with the ability to flexibly compose skills both logically and temporally to provably achieve specifications in the regular fragment of linear temporal logic (LTL). This approach empowers the agent to sequence and order goal-reaching skills to satisfy temporal logic specifications. Zero-shot generalization is important in this context is important due to the vastness of the task space associated with LTL objectives,  rendering training across every conceivable scenario intractable.", "weaknesses": "The paper raises concerns about the optimality of the policy resulting from composition, as the task planning algorithm lacks consideration for the cost of sub-tasks within a skill machine. Consequently, the generated behavior can be suboptimal due to this oversight. Although the paper presents a method for few-shot learning to create new skills, it remains unclear why learning a new skill is preferred over recomposing existing ones, raising questions about the approach's efficiency. Furthermore, it does not seem a learned new skill in few-shot learning is consistent with Definition 3.1.\n\nAn empirical comparison between the paper's few-shot learning strategy and the Logical Options Framework (LQF) baseline is lacking. The LQF baseline employs a meta-policy for choosing options to achieve subgoals within the finite state automaton representation of an LTL property. This approach integrates value iteration over the product of the finite automaton and the environment, ensuring that options can be recombined to fulfill new tasks without necessitating the learning of entirely new options. \n\nFurthermore, the absence of a comparison with LTL2Action in the continuous safety gym environment raises questions. The paper concludes that the zero-shot agent's performance is nearly optimal. It is crucial to assess this claim by comparing the zero-shot agent's performance in terms of discounted rewards with that of the LTL2Action agent in the safety gym environment.\n\nThere is room for improvement in the execution of the paper, particularly in the clarity of its formalization. Following the formalization proved to be challenging, and below, I have outlined my specific concerns regarding this aspect.\n\nBrandon Araki, Xiao Li, Kiran Vodrahalli, Jonathan A. DeCastro, Micah J. Fry, and Daniela Rus. The logical\noptions framework. CoRR, abs/2102.12571, 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BbNsbmFARo", "reviewer": "Reviewer_38Qb", "summary": "This work proposes skill machines to encode skill primitives of all high-level sub-tasks. Then zero-shot and few-shot learning is used to help train a policy which aims to satisfy specifications composing sub-tasks temporally and logically.", "questions": "1. In Sec 2.2, the authors say \"Consider the multitask setting, where all tasks share the same state and action space, transition\ndynamics and discount factor, but differ in reward function. The agent is required to reach a set of desired terminal states in some goal space G ⊆ S.\" Does this mean all subtasks can be represented as reaching a some goal states? If yes, this should be remarked more clearly.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Proposed a principled way to transfer learned task policies to related temporal logic specification.\n2. Conducted thorough experiments to validate the approach.", "weaknesses": "1. The definition of (linear) temporal logic is not provided.\n\n2. I would suggest the authors to briefly mention how to convert LTL to reward machines, e.g., through buchi automata, to make it more clear.\n\n3. This work only considers some simple temporal operations such as \"until\" and \"eventually\", but no continuous time interval. Extension to other temporal logic like signal temporal logic (STL) can be more interesting and useful practically -- also more challenging for sure.\n\n4. There are some related work to compare. For instance, I find the following two papers relevant to this paper, the authors are encouraged to compare with them.\n[1]. Luo, X. and Zavlanos, M.M., 2019, December. Transfer planning for temporal logic tasks. In 2019 IEEE 58th Conference on Decision and Control (CDC) (pp. 5306-5311). IEEE.\n[2]. León, B.G., Shanahan, M. and Belardinelli, F., Systematic Generalisation of Temporal Tasks through Deep Reinforcement Learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)