Skill Machines: Temporal Logic Composition in Reinforcement Learning
Authors: Geraud Nangue Tasse
Devon Jarvis
Steven James
Benjamin Rosman
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Lifelong learning
Multi task learning
Transfer learning
Logical composition
Deep Reinforcement Learning

Abstract: A major challenge in reinforcement learning is specifying tasks in a manner that is both interpretable and verifiable. One common approach is to specify tasks through reward machines---finite state machines that encode the task to be solved. We introduce skill machines, a representation that can be learned directly from these reward machines that encode the solution to such tasks. We propose a framework where an agent first learns a set of base skills in a reward-free setting, and then combines these skills with the learned skill machine to produce composite behaviours specified by any regular language, such as linear temporal logics. This provides the agent with the ability to map from complex logical task specifications to near-optimal behaviours zero-shot. We demonstrate our approach in both a tabular and high-dimensional video game environment, where an agent is faced with several of these complex, long-horizon tasks. Our results indicate that the agent is capable of satisfying extremely complex task specifications, producing near optimal performance with no further learning. Finally, we demonstrate that the performance of skill machines can be improved with regular off-policy reinforcement learning algorithms when optimal behaviours are desired.

Under review as a conference paper at ICLR 2023
SKILL MACHINES: TEMPORAL LOGIC COMPOSITION IN REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
A major challenge in reinforcement learning is specifying tasks in manner that is both interpretable and verifiable. One common approach is to specify tasks through reward machines- finiteee-iiite state machines that encode the task to be solved. We introduce skill machines, a representation that can be learned directly from these reward machines that encode the solution to such tasks. We propose a framework where an agent first learns a set of base skills a reward-free setting, and then combines these skills with the learned skill machine to produce composite behaviours specified by any regular language and even linear temporal logics. This provides the agent with the ability map from complex logical task specifications to near-optimal behaviours zero-shot. We demonstrate our approach in both a tabular and high-dimensional video game environment, where agent is faced with several of these complex, long-horizon tasks. Our results indicate that the agent is capable of satisfying extremely complex task specifications, producing near optimal performance with no further learning. Finally, we demonstrate that the performance of skill machines can be improved with regular off- off-policy reinforcement learning algorithms when optimal behaviours are desired.
INTRODUCTION
Reinforcement learning (RL) is promising framework for developing truly general agents capable of acting autonomously in the real world. Despite recent successes in the field, ranging from video games (Badia et al. 2020) to robotics (Levine et al. 2016). there are several shortcomings to existing approaches that hinder RL's real-world applicability. One issue that of sample efficiency-wiin is possible to collect millions of data points in a simulated environment, it is simply not feasible to do so in the real world. This inefficiency exacerbated when single agent is required to solve multiple tasks (as would expect of a generally intelligent agent). One approach of generally intelligent agents to overcoming this challenge is their ability to reuse learned behaviours to solve new tasks (Tay) lor & Stone 2009). preferably without further learning. That is, rely composition, where agent first learns individual skills and then combines them to produce novel behaviours. There are several notions of compositionality in the literature, such temporal composition, where skills invoked one after the other ("pickup blue object then a box") ) (Sutton et al.
1999 Barreto et al. 2011)), and spatial composition, where skills are combined to produce new behaviour be executed (" pickup
a blue box ") (Todorov 2009
Saxe et al.
2017
Van Nickerk et al.
2019 Alver & Precup 2022
Notably, work by Nangue Tasse et al. 2020) has demonstrated how agent can learn skills that can be combined using Boolean operators, such as negation and conjunction, to produce semantically meaningful behaviours without further learning. An important, additional benefit of this compositional approach is that it provides way to address another key issue with RL: tasks, as defined by reward functions, can be notoriously difficult to specify. This may lead to undesired behaviours that are not casily interpretable and verifiable. Composition that enables simpler task specifications and produces reliable behaviours thus represents a major step towards safe AI (Cohen et al. 2021).
Unfortunately, these compositions are strictly spatial. Thus, another issue arises when agent is required to solve a long horizon task. In this case, it is often near impossible for the agent to solve the task, regardless of how much data it collects, since the sequence of actions to execute before learning signal is received is too large (Arjona-Medina order skills, which shorten the planning horizon (Sutton et al. 1999). One specific implementation
Medina et al. (2019). This can be mitigated by leveraging higher-

---

Under review as a conference paper at ICLR 2023
of this is reward machines finite state machines that encode the tasks to solve (Icarte et al. 2018). While reward machines obviate the sparse reward problem. used in isolation, they still require the agent to learn how to solve a given task through environment interaction, and the subsequent solution is monolithic, resulting in the afore mentioned problems with applicability to new tasks and reliability.
In this work, combine these two approaches to develop agent capable of zero-shot spatial and temporal composition. We particularly focus on temporal logic composition, such as linear temporal logic (LTL) (Pnueli 1977). allowing agents sequentially chain and order their skills while ensuring certain conditions are always or never met. We make the following contributions: (a) we propose skill machines, finite state machine that can be autonomously learned by compositional agent, and which can be used to solve any task expressible as finite state machine without further learning; (b) we prove task specification, an agent can successfully solve it while adhering to any constraints; and (c) we demonstrate our approach in several environments, in- cluding high-dimensional video game domain. Having learned a set of base skills in a reward-free set- ting (in the absence of task rewards from reward machine) our results indicate that method is ca- pable of producing near-optimal behaviour for a variety of long-horizon tasks without further learning.
that these skill machines are satisficing-ggive
To describe our approach to temporal composition, we use the Office Gridworld (Icarte et al.. 2018) as a running example. In the environment, illustrated by Figure La an agent (blue circle) can move to adjacent cells in any of the cardinal directions. It can also pick up coffee or mail at locations or X respectively, and it can deliver them to the office at location 1. Cells marked * indicate decorations that are broken if the agent collides with them, and cells marked A-D indicate the centres of the corner rooms. The reward machines that specify tasks in this environment are defined over 10 propositions:
{A, B, C, D, #, He, K, 4, (3 $*}. where the first 8 propositions are true when the agent is at their respective locations, X is true when the agent is at X and there is mail to be collected, and f + is true when the agent is at and there is someone in the office.
A
*
+
in Am*
A
*
U3
A
t
*
*
10 A -
A *
*
*
14
1ly I
0.568 +
A
*
*
0.50
-B3A *
start
(a) Office Gridworld
(b) Reward and Skill Machine
Figure 1: Illustration of (a) the office gridworld where the blue circle represents the agent and (b) the finite state machine representing both the reward and skill machine for the task "deliver coffee and mail to the office without breaking any decoration" where the black dots labeled t represent terminal states. The reward machine gives rewards (6,) to the agent for each FSM state and the skill machine gives the composed skills åq that maximises those rewards. For example at uo. 5, (uo) (R *) O.5(R
* and dg(w)) = 0.5(Q A -Qx) + 0.5(Q A -Qg)..
2 BACKGROUND
We model the agent's interaction with the world Markov Decision Process (MDP), given by (S, A, P, R, 7), where (i) C R" is the n-dimensional state space; (ii) A is the set of (possibly continuous) actions available to the agent; (iii) P(s'|s, a) is the dynamics of the world, representing the probability of the agent reaching state s' after executing action a in state s; (iv) R is a reward function bounded by RRUN, RMAX] that represents the task the agent needs solve; and (v) y E [0, 1] is a discount factor. The aim of the agent is to compute a Markov policy π from S to A that optimally solves given task. Instead of directly learning a policy, an agent will often
2

---

Under review as a conference paper at ICLR 2023
instead learn value function that represents the expected return following policy from state (=(s) = =E IE== 7 R(s, at]]. A more useful form of value function is the action-value function (T),,a), which represents the expected return obtained by executing a from and then following The optimal action-value function is given by (* a) = max Qa (s, a) for all states and actions a, and the optimal policy follows by acting greedily with respect Q" each state.
2.1 LOGICAL COMPOSITION IN THE MULTITASK SETTING
We are interested in the multitask setting, where an agent is required to reach set of goals in some goal space 9 C S. We assume that all tasks share the same state space, action space and dynamics, but differ in their reward functions. We model this setting by defining background MDP M A, P. R, 7) with its own state space, action space, transition dynamics and background reward function: R. Any individual task 7 is then specified by task-specific reward function R, that is non-zero only for states in G. The reward function for the resulting task MDP is then simply R+ Ry-
Nangue Tasse al. (2020) consider the case where (g. a) E {RMNN: RMAX} and develop framework that allows agents to apply the Boolean operations of conjunction (A), disjunction (V) and negation (-) over the space of tasks and value functions. This is achieved by first defining the
goal-oriented reward function which extends the task rewards (R + Rz) to penalise an agent for achieving goals different from the one it wished to achieve:
RMISS R(s,g, a) = R(s.a) + (s,a) otherwise,
g * 8; where g E 9 and s absorbing
(1)
RMISS is a large negative penalty that can be derived from the bounds of the reward function. Using Equation [ we can define the related goal-oriented value function as:
/ ra (()
()) g)) +7
> where (**,9)) B. 7' X'
If a new task can represented as the logical expression of previously learned tasks, Nangue Tasse et al. (2000) prove that the optimal policy can immediately be obtained by composing the learned goal-oriented value functions using the same expression. For example, the union (V), intersection (A), and negation (-) of two goal-reaching tasks A and B can be solved as follows (we omit the value functions' parameters for readability):
Q'AB== = Q' V Q7 =
Dine = 0'1 A Qn = min Q4.Que
Q' = -Q= (Qsur QiNF) - Q²,
where Q'UU and Qier are the goal-oriented value functions for the maximum task (R, RMAX for all 9) and minimum task (R, = RMIN for all 9), respectively. Following Nangue Tasse et al. (202). we will also refer to these goal-oriented value functions world value functions (WVFs).
2.2
REWARD MACHINES
One difficulty with the standard MDP formulation is that the agent is often required to solve complex long-horizon task using only scalar reward signal as feedback from which to learn. To overcome this, Icarte et al. (2018) propose reward machines (RMs), which provide structured feedback to the agent in the form of a finite state machine (FSM). RMs encode a reward function using a set of propositional symbols P that represent abstract environment features follows:
Definition (Reward Machine). Given a set of states S and actions A, a reward machine is tuple RSAA = (U, uo, F, 8u, 8p) where (i) U a finite set of states; (ii) un E U is an initial state; (ii) F is finite set of terminal states: (iv) 8,, U x SS x A x S) + U U F is the state cate--rranstion function; funnttinnn and (v) 5, U [S A x S IR] the state-reward function.
RMs consist of finite set of states U where transitions between RM states governed by 8.. and where each RM state emits a reward function according to 6,. To incorporate RMs into the RL framework, the agent must be able determine correspondence between abstract RM propositions
3

---

Under review as a conference paper at ICLR 2023
(P (A=,A,,,C,,,
for example) and states in the environment. To achieve this, the agent is equipped with a labelling function L: S x A x S + 2n that assigns truth values to the propositions based on the agent's s interaction with its environment. Thus, 2n C S x A x S depicts an equivalence class from S x A x S. A particular instantiation of an RM that is used in practice- for RM-is simple reward machine (SRM denoted
x
example when converting an L.TL. specification similarly as ApA)) which restricts the form of the state-reward function to be 6, U + [2 + R] (Icarte al. 2018). In other words, the SRM state-reward function emits function which maps the simpler equivalence class of states to scalar reward.
The agent's 's aim then to learn a policy : S x + over the joint background MDP and RM (MDPRM), which is defined by the tuple T = PS. P. U,U, uo, F,, F, 6z). However, the rewards from the reward machine are not necessarily Markov with respect to the environment, [eaarte et al. (2018) shows that product MDPRM (Definition 2 beloo) guarantees that the rewards are Markov such that the policy can be learned with standard algorithms like Q-learning(Icarte et al.) 2018). This is because the product MDPRM uses the cross-procd cross-product to consolidate how actions in the environment result in simultaneous transitions in the environment and state machine. Thus, product MDPRMs take the form of standard, learnable MDPs.
Definition 2 (Product MDPRM), Ler T = (S, p,y, P, U,U, up, F, F, 5,) be an MDPRM. The product MDPRM is then defined by the tuple MT = (ST, A, PT. RT, 7) where ST == 8 x FUUF). ((s, u), a, (s', u²)) = 6, (1) 5's),
Pr((s, = (6)
iFEEU
()) otherwise ss ~ a(-)s,a) and u' = Sulu, (s,
LEVERAGING SKILL COMPOSITION FOR TEMPORAL LOGIC TASKS
Since we are interested in temporal logic tasks, we will restrict our attention to RMs whose rewards per node are specified by linear preferences over Boolean expressions (instead of arbitrary real-valued functions that are not grounded in achieving goals in an environment):
Definition (Tasks). Let M = AS P, R, 7) be a background MDP. A task is a product MDPRM MT = (ST, PT, RT,7) over M and a reward machine with reward function
(1) E (n Σ wpRp(s,a, Rp(s,a,s)) Σ
Wp and w R
} where
PE221
PE228
RMAX
Ep
Rp(8,,,5) =
RAIN
if if a, 8¹) $ p
R(s,a) a)
otherwise.
We will assume that the rewards ls a, 5') are such that the policies that maximises them are guaranteed to reach states where the corresponding propositions p are true-a common example is to have R(s, a) RMIN = 0 and RMAX = 1. This definition of RMs provides a general notion of tasks that are still grounded in achieving goals. Figure Tb illustrates an example of an RM in the office gridworld for solving the task "deliver coffee and mail to the office without breaking any decoration".
3.1 FROM ENVIRONMENT TO PRIMITIVES
In order to solve temporal logic tasks zero-shot, we propose to first learn a set of primitive skills which can later be composed to maxise the rewards per RM node without further learning. To achieve this, we first introduce the concept of constraints C C P. which are the set of propositions that an agent should avoid setting to true and corresponds to the global operator G in linear temporal logic (L.TL) specification. An example of a constraint might be that the agent should complete a task, but avoid breaking any decorations while doing so (C -== (*} and in the LTL we say G -)). We can now define the notions of task primitives and skill primitives such as "Pick up coffee" (F in LTL) or "don't 't break any decoration" (-(F*) = G - in LTL).
Definition& 4 (Primitives). Let M (8, A, P, be a background MDP. We define a task primitive in this domain as Mp = Ag, Pg. Ry, 7). p E 22", with absorbing goal space G = 2 and labelling function I., where
4

---

Under review as a conference paper at ICLR 2023
Sg (8 2 U2? where C is the set of constraints;
Ag = A x Ar, where A, = {0, ] represents whether or not to terminate a task;
[((,,,,55) i =1 (8'd)
Po((s,c), a.))
otherwise
where s' P(-|s, a) and cu if = and L(),a,8') Ep ifa, = 1 and as),a.8) 4p R(s,a) otherwise.
RMAX
(((ss,),, = RAIN
A skill primilive 27 is defined as the WVF for the task primitive Mp-
The above defines the state space of primitives 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 augmented with terminating action following Barreto et al. (019) and Nangue Tasse al. (2020), which indicates that the agent wishes to achieve the goal it is currently at, and is similar to an option's 's termination condition (Sutton al.) 1999). The transition dynamics update the environment state and constraints set to true when regular action is taken, and use the labelling function to return the set of propositions achieved when the agent decides to terminate. Finally, the agent receives the regular background reward when taking an action, but primitive-specific goal reward when it terminates.
Importantly, primitives are temporally atomic, that is, they correspond to tasks with single non-terminal RM state. They are, thus, the smallest unit of temporal logic. However, since the goal space of task primitives are defined by Boolean propositions, we can leverage prior work to solve any logical composition over them by composing their corresponding skill primitives (Nangue Tasse (ct al., 2020). We will denote the set of base task primitives to be MP and the corresponding base skill primitives Op. which can be composed to obtain any other primitive. For example: "Pick up coffee without breaking any decoration" ((F e -( *)) is another primitive by Definition 4 As we discuss in Section 3.2 this solves the primary problem with Reward Machines they suffer from the curse of dimensionality when all possible primitives must be relearned at all states in the FSM. Skill Machines in contrast leverage primitive composition within and across FSM states. Theorem below demonstrates that a linear combination of skill primitives maximise the task (in terms of Definition 3 rewards per RM node without further learning (proof's of all theorems are presented in the Appendix). This is also demonstrated experimentally in Figure Bin Appendix [A.5] Theorem 1. Let Rg be a vector of rewards for each task primitive, and Q2 be the corresponding vector of optimal WVFs. Then, for an MDP m AS, Pg, Rw 7) with linear preference reward function Rw w Rg, we have Q w Qg:
3.2 FROM TASKS TO SKILL MACHINES
We now have agents capable of solving any logical and linear composition of base task primitives Mp by only learning their corresponding base skill primitives 2.p. Given this compositional ability over skills, and reward machines that expose the structure of tasks, agents can solve temporally extended tasks with little no further learning. To achieve this, we define skill machine (SM) as representation of logical and temporal knowledge over skills.
Definition 5 (Skill Machine). Given task MT = (ST, PT, RT, PT,RT,TT RSA = (U, uo F, Su, 5r), a set of propositional symbols P with constraints C C P, and their cor- responding base skill primitives Dp. a skill machine is tuple D'A (U, Un, F, F,5u, εQ. Wu, wg) siterenncefunction erence function over goals; and (üi) ōQ
defined by reward machine
where (i) wy U X - R is a preference function over transitions; (ïi) Wg -Sg x G + R is pref- [Sg Ag R] is the state-skill function defined by: wol(s, c) u. wo (u, ul Qi ((s, c) (a,0)),
)Q(u)((s, (a. 0)) + Σ Σ
gES d'EU
where Qu is the WVF obtained by composing the skill primitives Øg according the Boolean expression for the transition 8,(1) (u)(8, a, n'.
For a given state s E in the environment, true constraints c E C, and state u in the skill ma- chine, the skill machine uses its preference over transitions wy and goals Wg compute a skill
5

---

Under review as a conference paper at ICLR 2023
Q(ss.)), (a, 6g then transitions to the next state where (s', c') t Po ((s, c), (a, 0)) and the skill machine transitions to u' <- (u, L(s, a, s')). Wy represents cases where there is not necessarily single desirable transition to follow given the current SM state. This is illustrated by the SM in Figure [b] where mail (Ez) and coffee (#) ) are equally desirable at the initial state. Similarly, Wg represents cases where there may be single desirable task, but its goals are not necessarily equally desirable given the environment state-for example when the agent needs first pick up coffee but there are two coffee locations. Remarkably, there always exists a choice for wo and we that is optimal with respect to the corresponding reward machine, as shown Theorem 2
0)) that an agent use to take action a. The environment
Theorem 2. Let nT" (s, u) be the optimal policy for task Mr, and let C = P. Then there exists cor- responding skill machine with a Wg and wy such that π (s, u) E arg max.EA (u) , (a, 0)),
where bg is given by Wg and WU as per Definition 5
Theorem shows that skill machines can be used to solve tasks without having to relearn action level policies. The next section shows how an agent can approximate a skill machine by planning over simple reward machines.
3.3 FROM SIMPLE REWARD MACHINES TO SKILL MACHINES
start
start
start
(- A + 0)
Up
(*,0) 0)
A A
(* 0,.0)
A Amnk
+,, 0.9)
A-*
(-0 1
(*,0))
# 0.9)
(*.0)
A
*
(4 A - 1)
(1 -3 1)
A -
(a) Simple reward machine
(b) Value iterated RM
(c) Skill machine
The SRM, value iterated RM and skill machine for the task "Deliver coffee to the office with- out breaking any decoration". This task specified using LTL as (P' ^ (F AG -+)), where F = F Finally, X = neXt, G = Globally are LTL operators. The corresponding RM is obtained by converting the LTL into finite state machine (Duret- et al.. 2016) and then giving a reward of 1 for accepting transitions and 0 otherwise. The black dots labeled / represent terminal states.
Figure 2:
In the previous section, we introduced skill machines and showed that they can be used represent the logical and temporal composition of skills needed to solve reward machines. We now show how for simple RMs (RMs returning scalar rewards as defined in Section 2.2 their approximate SM can be obtained zero-shot without further learning. To achieve this, we first plan over the reward machine (using value iteration, for example) obtain Q-values for each transition. We then select the skills for each SM state greedily. This process is illustrated in Figure 2 While this only holds for cases where the greedy skills are always satisfice-able from any environment state, this still covers many tasks of interest. In particular, this holds for any RM with non-zero rewards of RMAX only at accepting transitions! as shown in Theorem 3
Let AP (U, uo, F, 6,M) be a satisfice-able simple reward machine with non-zero rewards RMAX only for accepting transitions, and for which all valid transitions (u, u') are achievable from any state E S. Define the skill machine 2 (U, uo, F, dw, dQ, WU, wg) with
Theorem 3.
Wu u') =1 uf arg max Q" Qu( u.). O otherwise
n"
(c((ss)),uug)) = if arg max max
Σ x
wolu, u' Din ())),, 0
otherwise
where Q the optimal transition-value function for RY Then following the policy K (s, u) arg max 5Q (() c). (o. 0)), will reach an accepting transition.
AAccepting transitions are transitions at which the high level deserihed, for example, by linear temporal logics-in is satisficd.

---

Under review as a conference paper at ICLR 2023
Theorem is critical it provides soundness guarantees, ensuring that the policy derived from the skill machine will always satisfice the task requirements. Finally, in cases where the composed skill S0 obtained from the approximate SM is not sufficiently optimal, we can use any off- off-policy algorithm to learn a new skill QT few-shot. This is achieved by using the maximising Q-values max ( (1 (950) in the exploration policy during learning. Here, (0, 1) is a parameter that determines how much of the composed policy to use. It can also be seen as decreasing the potentially overestimated values of åq. since åg is greedy with respect to both goals and RM transitions. Consider Q-learning with 3 = % During the e-greedy exploration, we use a + arg m (aax (1-7)))11))g) to select greedy actions, hence improving the initial performance of the agent where gQT (1 - 7)0q. and guaranteeing convergence in the limit like regular Q-learning. Appendix A.2 illustrates this process.
4 EXPERIMENTS
We consider the Office Gridworld (Figure la and the Moving Targets (Figure domains:
(i) Office Gridworld learte et al. (2018): The tasks here are specified over 10 propositions
P [,, D.*,
and constraint C = { We learn the base skill primi- tives 2p (Figure 7 7in Appendix A.5 using goal oriented Q-learning Nangue Tasse al. 2020). where
X
the agent keeps track of reached goals and uses Q-learning (Watkins) 1989) to update the W VF with respect all seen goals at every time step. (ii) Moving Targets Domain Nangue Tasse al. (2020): This is canonical object collection domain with high dimensional pixel observations (84 x 84 x 3 RGB images). The agent here needs to pick up objects of various shapes and colors; picked objects respawn at random empty positions similarly to previous object collection domains (Barreto et al.. 2020). There are 3 object colours-beige beige (.) blue purple
and 2 object shapes squares (x)) circles (C). The tasks here are defined over 6 propositions and constraints P = C
We learn the corresponding base skill primitives with goal oriented Q-learning Nangue Tasse et al.
(2020) but using deep Q-learning (Mnih et al. 2015) to update the WVFs.
4.1
ZERO-SHOT TEMPORAL LOGICS
Task
Description LTL
Deliver coffee to the office without breaking decorations (F
X [ ()) A(G -*)
2
Patrol rooms A. B, C, and D without breaking any decoration
(F (A X (F (B X (F (C X (FD)))))) (G -*)
3
Deliver coffee and mail to the office without breaking any decoration
((F X (F (EZ ^ X (F))))) II (F (& A X (F (AX (F)))))) A (G
Deliver mail to the office until there is no mail left, then deliver coffee office while there are people in the office, then patrol rooms A-B-C-D-A, and never break a decoration
(F 1 A X (F
( A A EUU H
A A A (F A X -U (- X
A (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 we evaluate how long takes an agent to learn a policy that can solve the four tasks described in Table 3 The agent iterates through the tasks, changing from one the next after each episode. In all of our experiments, we compare the performance of skill machines with that of state-of-the art RMM-aaedd learning approaches like counterfactual RMs (CRM) where the f-functions are updated with respect to all possible RM transitions from a given environment state-and hierarchical RMs learns options per RM state that are grounded in the environment states (Icarte et al., 2018). In addition to learning all four tasks, we also experiment with Tasks 3 and in isolation. In these single task domains, the difference between CRM, HRM, skill machines and Q-learning should be less pronounced, since CRM, HRM and few-shot with skill machines 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 of the compositionality afforded by skill machines.
where agent
The results of these three experiments (each ran for 2 x 10y time steps) are shown in Figure 3 Regular Q-learning struggles to learn Task 3 and completely fails to learn the hardest task (Task 4).
7

---

Under review as a conference paper at ICLR 2023
Additionally, notice that while QL and CRM can theoretically learn the tasks optimally given infinite time, only HRM and SM are able to learn hard long horizon tasks in practice. is important to note that we train all algorithms for the same amount of time during these experiments and previous work (Nanuue Tasse et al. 2020) has shown that learning the WVFFs takes longer than learning task-specific skills. In addition, the skill machines skill primitives. Thus using the skill machines in isolation (labelled SM on Figure 3 may provide sub-optimal performance compared the task-specific agents, since the skill machines have been trained to optimality and are not specialised to the domain. Even under these conditions, we observe that skill machines perform near-optimally in terms of final performance, and due the amortised nature of learning the WVF will achieve its final rewards from the first epoch.
being used zero-shot generalise the office tasks using
120
100
Total Reward
Total Rewword
40
Rewer
(RM
CR8 RS
Totl
23
HRM
CRM RS
(RM RA
28
0.
1.
30
35
40
28
10
20 Episades
2.5
3/0
38
4.
60
5.
10
2:0
2.5
30
35
Episodes
Episodes
(a) Task 3
(h) Task
(c) Multiple tasks (1-4)
Figure 3: Average (over 80 independent trials) returns during training in the Office Gridworld.
4.2 FEW-SHOT TEMPORAL LOGICS
It is possible to pair the skill machines with a learning algorithm such as Q-learning achieve few- shot generalisation. From the results shown in Figure 3 it is apparent that skill machines paired with Q-learning (labelled QL-SM multi-task setting. While it is not clear from the rewards that adding Q-learning provides significant improvements to the skill machine, their trajectories show that O-learning does indeed improve the skill machine policies when they are not optimal (Appendix 9 Additionally, skill machines with Q-learning always begin with a significantly higher reward and converge their final performance faster than all benchmarks-excep the zero-shot one which is (near) optimal in all cases. The speed of learning is due the compositionality of the skill primitives with skill machines, and the high final performance is due to 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.
Figure 3 achieves the best performance for both the single-task and
4.3 FUNCTION APPROXIMATION
We now demonstrate our temporal logic com- position approach in Moving Targets domain where function approximation is required. Fig- ure 4 shows the average returns of the optimal policies and SM policies for the four tasks de- scribed in Table with 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 optimal on average. We also observe that for very challeng- ing tasks like Tasks and 4 (where the agent must satisfice difficult temporal constraints), the compounding effect the sub-optimal policies sometimes leads to failures. such cases, learning new skills sho- using tabular Q-learnin by leveraging the SM would guarantee convergence to op- timal policies as demonstrated Section 4.2 but that is not guaranteed using function approximation.
Oatimal Composed Random
Average Returns
30
Tasks
Figure 4: The Moving Targets domain (left) and the average returns over 100 runs for tasks Ta- (rihtt,,,, where B, P.S
8

---

Under review as a conference paper at ICLR 2023
Task
Description
LTL
Pick up any object. Repeat this forever. F (OVE) x)
Pick up blue then purple objects. then objects that are neither blue nor purple. Repeat this
forever. F A (F A ( v ( A
)))))
Pick up blue objects or squares, but never blue squares. Repeat this forever.
| (F( v [) A (G -( A Z
Pick up non-square blue objects, then non-blue squares in that order. Repeat this forever.
[F((-E) A
A X
Table 2: Tasks in the Moving Targets domain. To repeat forever, the terminal states of the RMs generated from LTL are removed, and transitions to them are looped back to the start state.
5 RELATED WORK
One family of approaches to spatial composition leverages forms of regularisation to achieve seman tically meaningful disjunction (Todorov] 2009 Van Niekerk al. (2019) or conjunction (Haarnoja et 2018: Hunt et al.) 2019). Weighted composition has also been demonstrated; for example, Peng et al. (019) learn weights to compose existing policies multiplicatively to solve new tasks. Approaches that leverage the successor feature (SF) framework (Barreto et al. 2017) are capable of solving tasks defined by linear preferences over features (Barreto et al.) (020). Alver & Precup (2022) show that an SF basis can be learned that is sufficient to span the space of tasks under consideration, while Nemecek & Parr (2021) determine which policies should be stored limited memory so as to maximise performance on future tasks. In contrast to these approaches, our framework allows for both spatial composition (including operators such as negation that other approaches do not support) and temporal composition such as LTL.
A popular way of achieving temporal composition is through the options framework (Sutoon et al. 1999: Bacon al. (017)) Here, high-level skills are first discovered and then executed sequentially to solve a task (Konidaris & Barto 2009; Bagaria & Konidaris 2019). Barreto et al. (2019) leverage the SF and options framework and learn how linearly combine skills, chaining them sequentially to solve temporal tasks. However, these options-based 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.
Work has also centred on approaches to defining tasks using human-readall logic operators. For example, [L et al. (2017) and Littman et al. (2017) specify tasks using LTL, which is then used to generate a standard reward signal for an RL agent. [Cmaacho et al. (2019) show how to perform reward shaping given LTL specifications, while Jothimurugan et 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 be used for learning. All of these approaches focus how an agent can improve learning given such specifications or structure, but we show how an explicitly compositional agent immediately solve such tasks using WVFs without further learning.
6 CONCLUSION
We proposed skill machines-finite state machines that can be learned from reward machines 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 to the logical task specifi- cation, which provides assurances of safety and verifiability to the agent's decision making, important characteristics that are necessary if are ever deploy RL agents in the real world. While the resulting behaviour is provably satisficing, empirical results demonstrate that the agent's performance is near optimal; further fine-tuning 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-specifiable tasks in the real world with further learning.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Safa Alver and Doina Precup. Constructing a good behavior basis for transfer using generalized policy updates. In International Conference on Learning Representations, 2022.
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.
P. Bacon, J. Harb, and D. Precup. The option-critic architecture. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
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.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In International Conference on Learning Representations, 2019.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning, In Advances in Neural Information Processing Systems, pp. 4055 4055-4065, 2017.
André Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygün, Philippe Hamel, Daniel Toyama, Shibl Mourad, David Silver, Doina Precup, et al. The option keyboard: Combining skills in reinforcement learning. Advances 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-30083 2020.
Alberto Camacho, Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. LTL and beyond: Formal languages for reward function specification in reinforcement learning. In International Joint Conferences on Artificial Intelligence, 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.
Alexandre Duret-Lutz, Alexandre Lewkowiez, Amaury Fauchille, Thibaud Michaud, Etienne Renault, and Laurent Xu. Spot 2.0-a 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 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 Roboties and Automation, pp. 6244 6251, 2018.
Jonathan Hunt, Andre Barreto, Timothy Lillicrap, and Nicolas Heess. Composing entropic policies using divergence correction. In International Conference on Machine Learning, pp. 2911 1-220, 2019.
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 Machine Learning, pp. 2107-2116, 2018.
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. Advances in Newral Information Processing Systems, 32, 2019.
George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. Advances in Neural Information Processing Systems, 22, 2009.
10

---

Under review as a conference paper at ICLR 2023
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 arXiv: 000.0044444444 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare 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. World value functions: Knowledge representation for multitask reinforcement learning. In The 5th Multi-disciplinury Conference on Reinforcement Learning and Decision Making (RIDM), 2022.
Mark Nemecek and Ron Parr. Policy caches with successor features. In International Conference on 2021.
Machine Learning, pp.
Xue Bin Peng, Michael Chang, Grace Zhang, Pieter Abbeel, and Sergey Levine. MCP: Learning composable hierarchical control with multiplicative compositional policies. In Advances in Neural Information Processing Systems, pp. 3686-3697, 2019.
Amir Pnueli. The temporal logic of programs. 18th Annual Symposium on Foundations of Computer Science, pp. 46-57. IEEE, 1977.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning.2001).. OpenAl, 2019.
Andrew Saxe, Adam Earle, and Benjamin Rosman. Hierarchy through composition with multitask LMDPs. International Conference on Machine Learning. pp. 3017-3026, 2017.
Richard Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2)181-211, 1999.
Matthew. Taylor and Peter Stone. Transfer learning for reinforcement learning domains: 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. 1856-1864, 2009.
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.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 PROOFS OF THEORETICAL RESULTS
Theorem 1. Let Rg be a vector of rewards for each task primitive, and Q2 be the corresponding vector of optimal WVFs. Then, for an MDP (Sg,AAg Pg. Rw; 7) with linear preference reward function Rw W Rgg, we have
Q - w Q
Proof.
(s,g,, = Ex
> w Rg
-w.Bl Eg
- (R
Σ
L==
since the world policies are independent of task Nangue Tasse et al. 2020 Lemma 2].
Q2
Theorem 2. Let n (s, u) be the optimal policy for task MT, and let C = P. Then there exists
corresponding skill machine with we and wu such that
n T" u) arg max (o (),
aeA
where dg is given by we and wu as per Definition!
No. where Ns, is the number of possible RM transitions from Also let Wg(s, -) be I for the set of propositions E 2 that are satisfied when following (s, u), and zero everywhere else. Then (', u) E arg max, Sq (u) c), (a,0) 0)) since Wo (u, u' d')Qi,.. c) (a, 0)) is optimal using Theorem and optimal policies are assumed to reach task goals.
Proof. Let wu(u,.)
Theorem Let RpA= (U, up Fu 8 be a satisfice-able simple reward machine with non-zero rewards RMAX only for accepting transitions, and for which all valid transitions (u, u') are achievable from any state E S. Define the skill machine 2sAAA (U, ua, F, du, dQ, WU, wg) with
wulu, ud) =1 if arg max Q' (u, v"), 0
otherwise
wo((s,,),,u,
ifg arg max max
E Ewrlu, u' Q')Quu (o, 0)); 0
otherwise
where Q" the optimal transition-value function for Rp Then following the policy x < u) arg m (Q( c). (a. 0)), will reach an accepting transition.
Proof. This follows from the optimality of x (s, u) and Q", since each transition of the RM is
satisfice-able from any environment state.
12

---

Under review as a conference paper at ICLR 2023
A.2 PSEUDO-CODE FOR FHW-SHOT Q-LEARNING USING SKILL MACHINES
Algorithm 1: Few-shot Q-learning using skill machines
Input Initialise: Q(..
a, I., U, uo; F, F,8u, 6Q
foreach episode do
Observe initial state E S, get initial u + uo, and c 0
while episode is not done do
/ Using the composed skill bq in the behaviour policy */
a 4-
arg max (max u, (000)))00))(6 e), (a, 0))}) if Bernoulli(1 -
aEA
a random action otherwise
Take action and observe next state and true constraints uu(Cn ((,a,,') Get reward r <- (1) a, s') and the next RM state u' Su Lis, a,),
(s,, a,a) e y if s' is terminal or u' F else r + y max Q(s', ul, a') s sts
A.3 FUNCTION APPROXIMATION WITH CONTINUOUS ACTIONS AND STATES
Task Description LTL
Navigate to a button and then to a cylinder. (F (B A X C))
Navigate to a button and then to a cylinder while never entering hazard regions
(F (B A X (F C))) A (G -H)
Navigate to a button, then to a cylinder without entering hazard regions, then to button
inside hazard region, and finally to cylinder again.
FF (B A (F ((C -H) A X (F ((B A H) A ((H))))))
Navigate to button and then to cylinder in hazard region. (F(BAX H))
Navigate to a cylinder. then to a button in a hazard region, and finally to a cylinder again.
(F (C A X (F ((B A H) A X (C))))
Navigate to a hazard, then to a cylinder, and finally to cylinder again while avoiding hazards. (F (H X (F (CAX (F (C H)))))
Table 3: Tasks in the Safety AI Gym domains. The RMs are generated from the LTL expressions.
We demonstrate our temporal logic composition approach in Safety AI Gym domain (Figure 5) RRy et al. 2019) which has continuous state space (S = R&0) and continuous action space (A R2) The agent here is point mass that needs to navigate to various regions defined by 3 propositions (P = (B. C, H)) corresponding to its 3 lidar sensors for the bultons (B) (grey spheres), the cylinder (C) (translucent cylinder), and the hazards (H) (blue regions). The button and hazard positions are fixed as shown in Figure(5) the cylinder randomly placed on one of the buttons, and the agent is randomly placed anywhere on the plane. We first learn the 3 base skill primitives corresponding to each predicate (with constraints C = Nangue Tasse et al. 2020) but using Twin Delayed DDPG (Fujimoto et al., 2018) to update the WVFs. Figure 6 shows the trajectories of the SM policies for the six tasks described in Table 3 Our results shows that skill primitives can leveraged to achieve zero-shot temporal logics even in continuous domains.
{ {H)), with goal oriented Q-learning
A.4 DETAILS OF EXPERIMENTAL SETTING
In this section we elaborate further on the hyper-paramene parameters for the various experiments Section We also describe the pretraining of WVFs for all of the experimental settings which corresponds to learning the base task primitives for each domain. The same hyper-pane aaper-parametes are used for all algorithms in particular experiment. This is ensure that evaluate the relative performance
13

---

Under review as a conference paper at ICLR 2023
Figure 5: Visualisation of the Safety Al Gym Domain.
(a) Task
(b) Task 2
(c) Task
(d) Task
(c) Task 5
(f Task 6
Figure 6: Visualisations of the trajectories obtained by following the zero-shot composed policies from the skill machine for tasks in Table
fairly and consistently, particularly since Nangue Tasse et al. (2020) note that learning WVFs can take longer than direct training tasks. However, training WVFs for longer would potentially bias the results in favour of their use. Thus, all algorithms are trained for the same amount of time which set such that they all converge. The full list papaeeparameters for the Office World, Moving Targets and SafeAI Gym domain experiments are shown in Tables respectively.
To use skill machines we require pre-trained WVFs. As mentioned above, all WVFs are trained using the same hyper-pane parameters any other training. Additionally, for all experiments the WVFs are pre- mre-trained on the base task primitives for the domain. For example, in the Office World domain, the WVFs trained the P base task primitive corresponding to achieving each predicate, P
14

---

Under review as a conference paper at ICLR 2023
Hyper-parameter
Value
Timesteps
2e"
Training exploration (e)
0.5
Per-episode evaluation exploration (c)
0.1
Discount Factor (7)
0.9
Table 4: Table of hyper-parametenn used for Q-learning in the Office World experiments.
Hyper-parameter
Value
Timesteps
le
Neural Network architecture
CNN N + MLP
CNN architecture
Defaults of Mnih et al. (2015)
MLP hidden layers
1024
1024 1024
Start exploration (c)
1
End exploration (c)
0.1
Exploration decay duration (e)
5e
Discount Factor (r)
0.99
Others
Defaults of Mnih et al. (2015)
Table 5: Table of hyper- paramm-ps used for Deep Q-learning in the Moving Targets experiments.
Hyper-parane Hlppe--parameter
Value 1
Timesteps
Neural Network architecture
MLP
MLP hidden layers
2024 x 2024 x 2024
Max episodes length
100
Target noise
0.2
Action noise
0.2
Discount Factor (7)
0.99
Others
Defaults of Achiam] (0018)
Table 6: Table of hyper-parameter used for the TD3 in the SafeAI Gym experiments.
++} (reaching states the predicate is set to True), with constraints C = (*). All other primitives in this domain be obtained zero-shot through value function composition. Similarly, for the moving targets domain, the WVFFs are pre-trained on the primitives corresponding obtaining objects by shape colour in the environment separately, P [ X O}, with constraints 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 button (B), cylinder (C'). and a hazard (H):
(,
= {B, C, H}. trained with constraints C {H}.
15

---

Under review as a conference paper at ICLR 2023
A.5 OFFICE WORLD ADDITIONAL FIGURES
(a) Room A
(h) Room B
(c) Room C
(d) Room D
(e) Decoration *
Coffee
(g) Mail
(h) Office
(i) Mails present 53
(i) People present
Figure 7: The policies (arrows) and value functions (heat map) the base primitive tasks in the Office Gridworld. These are obtained by maximising over the goals of the learned WVFs. All errors the figures are due training the WVFs for 200000 time steps, hence not convergence.
16

---

Under review as a conference paper at ICLR 2023
(a) [
(d) [
(c) (() A -*)
Figure 8: The policies (arrows) and value functions (heat map) for various preferences the primitives "get mail without breaking decorations" (D< A -)) and "get coffee without breaking decorations"
* in the Office GridWorld. These obtained by first doing the weighted sum of the composed WVFs (Q A - # A ^ according to the preferences, and then
maximising over the goals and actions. All errors in the figures are due to training the WVFs of the base primitives (Q" Q for 200000 time steps, hence not to convergence.
17

---

Under review as a conference paper at ICLR 2023
*
D
*
*
*
(a) Task zero-shot
(b) Task few-shot
A
*
B
B
*
*
*
*
Task zero-shot
(d) Task 2 few-shot
*
*
*
B
X
*
(c) Task zero-shot
(f) Task 3 few-shot
Figure Agent trajectories for various tasks the Office Gridworld (Table using the skill machine without further learning (left) and with further learning (right).
18


Reviews:
[{"review_id": "oylRN0CbwBf", "reviewer": "Reviewer_ronJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considered a multi-task reinforcement learning problem where all tasks share the same state space, action spaces, and the transition dynamics. A skill machine is proposed to solve complex task involving temporal and concurrent composition which can be learned from reward machine. The authors prove that an agent can solve it while adhering to any constraints. Through experiments, the authors demonstrate the efficiency of the proposed method in several environments. The result shows that the proposed method can provide a near-optimal behavior for a long horizon task without further learning. ", "summary_of_the_review": "The multitask reinforcement learning problem is important. But I have concern about the scalability of the proposed method to a more complex real problems. ", "strength_and_weaknesses": "Strength:\nThe proposed method takes use of the finite state machine to solve complex RL tasks. The proposed method guarantees that the resulting policy adheres to the logical task specification. The idea is promising given the fact that the algorithm can learn policies for multiple tasks at the same time. Sufficient experiments are presented to support the statement in this paper.\n\n\nWeakness: \nSince the proposed method is a finite state machine based, I expect the algorithm suffers from the curse of the dimensionality. The example of office gridworld is simple and small in terms of the goal, state, and action spaces. I would like to read a bit more about how to generalize the proposed method in the case when the spaces are much larger which is more likely to be true in real applications.\nThe number of goals is very limited in the experiments presented here. It will be great if the authors can present some examples that has larger goal space. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dv5yL9V9vTg", "reviewer": "Reviewer_UCg6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is a combination of two previous works. One is about logical (boolean) compositional mechanisms for multitask learning, and the other is about logical formalisms for temporal skills, both in the context of typical reinforcement learning problems. The idea is to lift the first (composing behaviors in a structured way from individual Q-functions basically) to the case of of temporally extended behaviors, in this case modeled as reward machines. The overall idea is to come up with so-called skill machines, which can represent both types of structure. The idea is evaluated on a couple of domains, where the goal is to show that many different (composed) skills can be learned (or zero-shot, computed/assembled) from a couple of basic (temporal) skills.", "summary_of_the_review": "A mixed evaluation, and one of these harder to review papers in my opinion. I clearly see the technical and conceptual positives in this paper, and I see the potential and the interesting outcomes of the paper. Yet, the description of some parts of the technical aspects is not yet clear enough for me to fully evaluate it. I do not want to kill a (potentially) good paper, hence I vote for a (weak) accept and await the discussion to see whether it can be improved still.", "strength_and_weaknesses": "The main strength of the paper is the proposed combination of methods. I think it makes a lot of sense, it is based on very recent work, and I see the potential. The paper appears polished, sketches related work, and the experiments show progress.\n\nA main weakness is the description of the method, the buildup of the story and the motivations/examples. This paper is in my top-k papers ever that are hard to review, hence any remark I make here could be the result of a misunderstanding on my side (disclaimer) but I do think it is mainly due to a poor description. I'm very knowledgeable of all the related work, and in particular the temporal/logical side of the matters, but I have a hard time understanding the method from its particular description in the text (and the appendices do not help much, since not much additional information is included).\n\nThe introduction section and Section 2 up to 2.2. are very clear in terms of setup, contributions and approach. Section 2.1. just gives the flavor of multi-task learning, compositions of Q-functions and so on, that are necessary for the rest of the paper. However, Section 2.2. is (in my opinion, and I re-checked the original papers on this topic) not understandable for the general (RL) reader, since it involves many things in only three small paragraphs, even though it implicitly assumes knowledge of how such machines work. For example, the \"joint MDP\" is used, but this relies on knowing more about temporal logic, the ability to compile into automata and the cross-product of machines with the MDP to create such a joint MDP. Later on in the paper, additional mentionings are made of for example \"product\" (page 4) and \"cross product\" (page 5) but never really explained. At this stage it would or could be an obvious thing to say that if we can see the problem as a joint MDP, and I mean the full product model, it again is a Markovian problem (which is the trick in many other papers in this area), hence the approach in Section 2.1. would already apply immediately (since the temporal dimension is compiled out essentially), and the combination will work. Ofcourse... you want to keep as much of the method on an abstract level (hence the reward machine) and you need more. In Section 3.1. the task space is first again formalized as a full product model and the compositional mechanism of Section 2.1. generalized to linear preferences over task primitives. I think this all makes sense, and is clear. The only thing that is not helping, is all the subtle differences of tasks, primitives, skills, goals, skill primitives and many other terms; in my opinion this could be made more clear throughout the paper too.\n\nSection 3.3 is where I think most of the confusion comes from. I think that the motivation and definition of skill machines needs much more explanation and formalization. I you look at the Figures 1 and 2, we see that they are essentially reward machines (in structure) but the difference lies in the \"preferences\" on the lower parts of the nodes, which give preferences over action choices (in the reward machines, thus not actually action choices, but the condition of going from one high-level node to another). But, even though I have some general understanding of how this would be done (based on earlier definitions in the paper) the text and formalization as given here, are incomplete to me. The motivations for the preferences (state transitions and goals) and how they can be found, and what they mean, does not become clear enough (also not from the proofs of the definitions). Also the additional description of additional learning steps (on page 6) to finetune approximate SMs, is not clear enough for me. \n\nSection 4 on the experiments has mixed quality, in my opinion. I think the experimental setup and selection of experiments is fine, and clearly is targeted at showing the composition of temporal skills and the reuse or zero-shot computation of new skills is clear. The last experiment with the moving domain, and the exact (motivation for) the particular setup in learning needs more description. But overall, the texts in this section are somehow describing a lot, yet at the same time not very clear and structured. When only looking at the graphs, I see the main message, but the texts do not help much. Overall, I see that what the authors want to show is in the results: for example, the composition of \"pick up blue objects or squares, but never blue squares\" and then repeating it, is a clear example of the composition of temporal skills, and it works.\n\nAdditional aspects:\n- Just before Section 2: \"high-dimensional video game\". This does seem relevant for the experiments at all, right? Same for the remarks about it in Section 4.3. itself.\n- Even though I think Section 2.1. contains enough information, I do wish more information would be given about the limitations, and also on the exact motivation for the third rule on negation (generally it looks like Fuzzy operaters by the way, but that is not relevant here).\n- Section 2.2. talks about general and simple RMs but it is sometimes unclear which one is the main one to go later on. Maybe be more clear about it here. This section could also use a big illustration of things. Also not clear whether the \"function\" or \"scalar\" difference is intuitive without illustrations.\n- It is not explained how to move through a (*) location without \"breaking any decoration\" (see Fig 1 left vs caption).\n- The formalization in Def 2. uses subscript 0 essentially for the background MPD even though in this context (with automata) it can be confused with the starting state.\n- The discussion of multi-task setups, CRM, HRM and the use of experience for multiple skills is something that is known in hierarchical RL as well, and options. This aspect could be discussed more in detail here, combined with the last part of Section 3 on additional learning phases in the SMs.\n- I think the first line of the conclusion is confusing (in the light of the remarks above too) in the sense that skills machines are \"finite state machines that can be learned...\". It is factually not true, since the automata themselves are not learned (but some parameters are computed or finetuned) and maybe this illustrates some of the confusion I have with parts of the paper still. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NywujcNDH7", "reviewer": "Reviewer_38dZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The submission introduces skill machines (SM), an approach to compositionally generalize over a space of tasks defined as reward machines (RM). In particular, this formulation enables compositional generalization both over concurrent goals (e.g., achieve a ^ b) and temporal goals (e.g., achieve a \"then\" b). The proposed approach uses planning over the RM leveraging the known RM transition function, and then chains pre-trained skills together to follow the plan. Theoretically, the authors show that SMs are sound, in that if a solution to the task exists in terms of the primitive skills, the SM will find it. Empirically, the method achieves zero-shot generalization, and improves with further training, on one set of grid world tasks and one set of image-based tasks.\n", "summary_of_the_review": "Overall, I think the motivation for this work is strong, but had a hard time finding the technical details needed to precisely understand what the technical contributions of the submission are. I strongly encourage the authors to provide as much detail as possible about their approach in a revised manuscript and to engage in the discussion so I can better understand their contributions. In the meantime, with the manuscript in its current state, I cannot recommend it for acceptance. I will use a low confidence score for my rating to indicate that I have a number of questions that, if clarified, might significantly alter my assessment of the work.\n\n############# Update after rebuttal ###############\n\nI am increasing my score from 3 (reject) to 5 (marginally below threshold) per the discussion with the authors, and increasing my confidence accordingly.", "strength_and_weaknesses": "########### Strengths ###########\n- The motivation for the work is excellent: using RL to train primitive skills that can serve as a basis for solving a multitude of tasks via composition, both concurrently and temporally, as specified by RMs\n\n########### Weaknesses ###########\n- I had a difficult time following the details of the approach and the corresponding theory behind it. Perhaps the authors could add more technical details to their manuscript?\n- I also had difficulty understanding the exact experimental setting used throughout Section 4\n- If my understanding was correct, then I am uncertain about the novelty of the contributions in this work. I hope the authors can clarify this during the discussion period.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KfJNLf_vWX", "reviewer": "Reviewer_MuPq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new RL framework wherein a set of base skills are learned in a reward-free setting followed by combination of these skills and learning skill machine to produce a complex behavior specified using languages such as linear temporal logic. This allows zero-shot mapping from high-level LTL specification to complex behavior. This is particularly helpful in solving long horizon task n the presence of a sparse learning signal. ", "summary_of_the_review": "Overall, the approach presented in the paper is interesting, but its explanation has some gaps, making the reviewer unable to appreciate it fully. Clarification to the doubts expressed in the review would be useful. \n\nThe reviewer has requested some minor revisions for technical accuracy and would encourage a careful review of some statements. Overall, the paper has enough merit to deserve a positive score and the reviewer has raised the rating. ", "strength_and_weaknesses": "Strengths:\n\n- The idea of learning individual skills separately from the task-specific policy is very interesting.\n\n- The combination of individual skills with reward machines can be very effective. \n\nWeaknesses: \n\n- There is a major assumption in the paper that needs to be more clearly stated. The considered multitask setting assumes that the underlying MDP can be designed such that the reward for any specific task is R0 + R_\\tau where R0 is default reward and R_\\tau is reward for a specific task tau. This is not necessarily true, and some work on IRL https://proceedings.neurips.cc/paper/2018/hash/74934548253bcab8490ebd74afed7031-Abstract.html have noticed this to recognize the value of learning temporal specifications as rewards (because this simple sum decomposition is not always feasible). This does not weaken the main contribution of the paper but it is important to recognize the significance of this assumption. \n\n- The tasks's state space is defined to be product of the environment state and the set of constraints incorporating the set of propositions that are currently true. The latter set can be exponential, and this seems to indicate an exponential blow-up in the state space with the growth in the size of the specifications.\n\n- The experiments seem to use mostly planning tasks. Using examples from Safe AI Gym would be useful to evaluate the full potenital of this method since it is being represented as a general RL approach and not just something limited to discrete planning. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject