Skill Machines: Temporal Logic Composition in Reinforcement
Learning
Geraud Nangue Tasse1 , Devon Jarvis1 , Steven James1 , Benjamin Rosman1

Abstract—A major challenge in reinforcement learning is
specifying tasks in a manner that is both interpretable andverifiable. One common approach is to specify tasks throughreward machines—finite state machines that encode the task to
be solved. We introduce skill machines, a representation that canbe learned directly from these reward machines that encode thesolution 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 atabular and high-dimensional video game environment, wherean 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 demonstratethat the performance of skill machines can be improved withregular off-policy reinforcement learning algorithms when optimal
behaviours are desired.

I. I NTRODUCTION
Reinforcement learning (RL) is a promising framework fordeveloping truly general agents capable of acting autonomously
in the real world. Despite recent successes in the field,
ranging from video games [1] to robotics [2], there are several
shortcomings to existing approaches that hinder RL’s real-world
applicability. One issue is that of sample efficiency—while itis possible to collect millions of data points in a simulated
environment, it is simply not feasible to do so in the realworld. This inefficiency is exacerbated when a single agent
is required to solve multiple tasks (as we would expect of agenerally intelligent agent). Another issue arises when an agent
is required to solve a long horizon task in the presence of asparse learning signal. In this case, it is often near impossible
for the agent to solve the task, regardless of how much datait collects, since the sequence of actions to execute before alearning signal is received is too large [3]. However, this canbe mitigated by leveraging higher-order skills, which shorten
the planning horizon [4].
A desirable characteristic of generally intelligent agents istheir ability to reuse learned behaviours to solve new tasks[5], preferably without further learning. One approach toovercoming this challenge is to rely on composition, wherean agent first learns individual skills and then combines themto produce novel behaviours. There are several notions of
1 Schoolof Computer Science and Applied Mathematics,
University of the Witwatersrand, Johannesburg, South Africa
geraudnt@gmail.com, {devon.jarvis, steven.james,
benjamin.rosman1}@wits.ac.za

compositionality in the literature, such as temporal composition,
where skills are invoked one after the other [4], [6], andconcurrent composition, where skills are combined to produce
a new behaviour to be executed [7], [8], [9], [10].
Notably, recent work [11] has demonstrated how an agent
can learn skills that can be combined using Boolean operators,
such as negation and conjunction, to produce semanticallymeaningful behaviours without further learning. An important
benefit of this compositional approach is that it provides away to address another key issue with RL: tasks, as definedby reward functions, can be notoriously difficult to specify.
This may lead to undesired behaviours that are not easilyinterpretable and verifiable. Composition that enables simpler
task specifications and produces reliable behaviours thus
represents a major step towards safe AI [12].
Unfortunately, these compositions are strictly concurrent andcannot be chained to solve temporally-specified tasks. One
solution to this issue is reward machines—finite state machinesthat encode the tasks to solve [13]. While this obviates thesparse reward problem, the agent is still required to learn how
to solve a given task through environment interaction, and thesubsequent solution is monolithic, restricting its applicability
to new tasks and limiting the reliability of resulting behaviours.
In this work, we combine these two approaches to develop
an agent capable of zero-shot concurrent and temporal composition. We particularly focus on temporal logic composition,such as linear temporal logic (LTL) [14], allowing agents tosequentially chain and order their skills while ensuring certain
conditions are always or never met. We make the following
contributions: (a) we propose skill machines, a finite statemachine that can be autonomously learned by a compositional
agent, and which can be used to solve any task expressible
as a finite state machine without further learning; (b) weprove that these skill machines are satisficing—given a task
specification, an agent can successfully solve it while adhering
to any constraints; and (c) we demonstrate our approach inseveral environments, including a high-dimensional video gamedomain. Having learned a set of base skills in a reward-freesetting, our results indicate that our method is capable ofproducing near-optimal behaviour for a variety of long-horizon
tasks without further learning.
II. BACKGROUND
We model the agent’s interaction with the world as a Markov
Decision Process (MDP), given by (S, A, P, R, γ), where(i) S ⊆ Rn is the n-dimensional state space; (ii) A is theset 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[RMIN , RMAX ] that represents the task the agent needs to solve;and (v) γ ∈ [0, 1] is a discount factor.
The aim of the agent is to compute a Markov policy π fromS to A that optimally solves a given task. Instead of directly
learning a policy, an agent will often instead learn a valuefunction that represents the P
expected return following policy π∞from state s: V π (s) = Eπ [ t=0 γ t R(st , at )]. A more usefulform of value function is the action-value function Qπ (s, a),which represents the expected return obtained by executing
a from s, and then following π. The optimal action-valuefunction is given by Q∗ (s, a) = maxπ Qπ (s, a) for all states s
and actions a, and the optimal policy follows by acting greedily
with respect to Q∗ at each state.
A. Logical Composition in the Multitask SettingQ̄∗A∧B = Q̄∗A ∧ Q̄∗B := min{Q̄∗A , Q̄∗B }
Q̄∗¬A = ¬Q̄∗A := Q̄∗SU P + Q̄∗IN F − Q̄∗A ,where Q̄∗SU P and Q̄∗IN F are the goal-oriented value functions
for the maximum task (r = RMAX for all G) and minimum
task (r = RMIN for all G), respectively . Following recent work[15], we refer to these goal-oriented value functions as world
value functions (WVFs).
B. Reward Machines
One difficulty with the standard MDP formulation is thatthe agent is often required to solve a complex long-horizon
task using only a scalar reward signal as feedback from whichto learn. To overcome this, recent work [13] propose rewardmachines (RMs), which provide structured feedback to theagent in the form of a finite state machine. RMs encode areward function using a set of propositional symbols P that
represent abstract environment features as follows:

We are interested in the multitask setting, where an agent
is required to reach a set of goals in some goal space
G ⊆ S. We assume that all tasks share the same state Definition 1 (Reward Machine). Given a set of propositional
space, action space and dynamics, but differ in their reward symbols P, states S and actions A, a reward machine is afunctions. We model this setting by defining a background tuple RPSA = ⟨U, u0 , F, δu , δr ⟩ where (i) U is a finite set of
MDP M0 = ⟨S0 , A0 , P0 , R0 ⟩ with its own state space, action states; (ii) u0 ∈ U is an initial state; (iii) F is a finite set
space, transition dynamics and background reward function. of terminal states; (iv) δu : U × 2P → U ∪ F is the stateAny individual task τ is then specified by a task-specific reward transition function; and (v) δr : U → [S × A × S → R] is thefunction Rτ that is non-zero only for states in G. The reward state-reward function.
function for the resulting MDP is then simply R0 + Rτ .
RMs consist of a finite set of states U , each of which
Recent work [11] consider the case where Rτ ∈represents
a set of propositions that are true at a given{RMIN , RMAX } and develop a framework that allows agents toenvironment
state. Transitions between RM states are governed
apply the Boolean operations of conjunction (∧), disjunction (∨)
by
δ
,
and
the
RM emits a reward function according to δr . Auand negation (¬) over the space of tasks and value functions.
particularinstantiationof an RM that is used in practice is aThis is achieved by first defining the goal-oriented reward
simplerewardmachine(SRM), which restricts the form of thefunction R̄ which extends the task rewards r to penalise anstate-reward
functiontobe δr : U × 2P → R [13]. In otheragent for achieving goals different from the one it wished towords, when a transition between u, u′ ∈ U is made, the SRM
achieve:emits a single scalar instead of a function (as in the case of(R̄MIN
if g ̸= s and s is absorbing
RMs).
R̄(s, g, a) :=(1)
To incorporate RMs into the RL framework, the agent must
R(s, a) otherwise,
be able to determine which abstract propositions are true atwhere R̄MIN is a large negative penalty that can be derived any given state. To achieve this, the agent is equipped withfrom the bounds of the reward function.
a labelling function L : S × A × S → 2P that assigns truth
Using Equation 1, we can define the related goal-oriented values to the propositions based on the agent’s interaction withvalue function as:
its environment. The agent can then learn a policy in a newZdecision process where the reward function in the originalQ̄(s, g, a) = R̄(s, g, a) + γV̄ π̄ (s′ , g)P(s,a) (ds′ ),(2) MDP is replaced with the RM, which is defined by the tupleS⟨S, A, P, γ, P, L, U, u0 , F, δu , δr ⟩. The agent’s aim is now to


P
∞
t
where V̄ π̄ (s, g) = Eπ̄learn a policy over the joint MDP and RM state space π :t=0 γ R̄(st , g, at ) .
If a new task can be represented as the logical expression S × U → A, which can be achieved with standard algorithms
of previously learned tasks, then the optimal policy can such as Q-learning [13].
immediately be obtained by composing the learned goalIII. L EVERAGING S KILL C OMPOSITION FOR T EMPORAL
oriented value functions using the same expression [11]. For
L OGIC TASKS
example, the union (∨), intersection (∧), and negation (¬) oftwo goal-reaching tasks A and B can be solved as follows (weTo describe our approach to temporal composition, we
omit the value functions’ parameters for readability):
use the Office Gridworld [13] as a running example. In theenvironment, illustrated by Figure 1a, an agent (blue circle)
Q̄∗A∨B = Q̄∗A ∨ Q̄∗B := max{Q̄∗A , Q̄∗B }can move to adjacent cells in any of the cardinal directions.

It can also pick up coffee or mail at locations K or B
respectively, and it can deliver them to the office at location
x. Cells marked ✽ indicate decorations that are broken if theagent collides with them, and cells marked A–D indicate thecentres of the corner rooms. The reward machines that specify
tasks in this environment are defined over 10 propositions:
P = {A, B, C, D, ✽, K, B, x, B+ , x+ }, where the first 8
propositions are true when the agent is at their respective
locations, B+ is true when the agent is at B and there is
mail to be collected, and x+ is true when the agent is at x andthere is someone in the office.
A. Task Space
We now define the set of tasks to be considered. We first
introduce the concept of constraints C ⊆ P, which are theset of propositions that an agent should avoid setting to trueand corresponds to the global operator G in a linear temporal
logic (LTL) specification. An example of a constraint might
be that the agent should complete a task, but avoid breaking
any decorations while doing so. We can now define the notionof base (primitive) tasks, which will later be composed.
Definition 2 (Task Primitive). Let M = ⟨S0 , A0 , P0 , R0 ⟩ bea background MDP. We define a set of task primitives in thisdomain as MG = {⟨S, A, P, R, γ⟩} with absorbing goal space
G = 2P and labelling function L, whereS := (S0 × 2C ) ∪ 2P , A := A0 × Aτ ;(L(s0 , a0 , s′0 ) if aτ = 1
P (⟨s0 , c⟩, ⟨a0 , aτ ⟩) :=,⟨s′0 , c′ ⟩otherwise(Rτ ∈ {RMIN , RMAX } if aτ = 1
R(⟨s0 , c⟩, ⟨a0 , aτ ⟩) :=R0 (s0 , a0 )otherwise.
where C is the set of constraints, Aτ = {0, 1} represents
whether or not to terminate a task, s′0 ∼ P0 (·|s0 , a0 ) andc′ = c ∪ (c ∩ L(s0 , a0 , s′0 )).

Definition 3 (Task space). The set of all tasks M is all linear
preferences over task primitives:
|MG |
n
X
M = ⟨S, A, P, Rw , γ⟩ : Rw (s, a) =wi Ri (s, a)
i=1
|MG |

where

X

wi = 1 and w ∈ R|MG |oi=1This definition of task space provides a general notionof tasks that are still grounded in achieving goals. It also
subsumes most definitions considered in the composition
literature, including Boolean algebra tasks [11] and linear
preference tasks [16]. Hence, we will restrict our attention
to reward machines whose rewards per state originate from thedefined task space (instead of arbitrary real-valued functions
that are not grounded in achieving goals in an environment). We
denote such reward machines as RMSA = ⟨U, u0 , F, δu , δM ⟩where δM maps from RM states to task rewards.
B. Skill Machines
The goal space of a primitive task is defined by a set ofBoolean propositions. We can leverage prior work to solve
each individual task using a set of base primitive skills [11].
We therefore only need concern ourselves with how to solve
any task expressed as a linear combination of the primitive
tasks. Fortunately, Theorem 1 below demonstrates that a linear
combination of base skills does just this (proofs of all theorems
are presented in the Appendix).
Theorem 1. Let RMG be a vector of rewards for each primitivetask, and Q̄∗G be the corresponding vector of optimal WVFs.
Then, for a task m ∈ M with reward function Rw = w · RMG ,we haveQ̄∗m = w · Q̄∗G .

Proof.

"∞#X
The above defines the tasks’ state space to be the product of∗tQ̄m (s, g, a) = Eπ̄∗γ w · R̄MG (st , g, at )the environment state and the set of constraints, incorporating
t=0"∞#
the set of propositions that are currently true. The action spaceXt
is augmented with a terminating action following previous= w · Eπ̄∗γ R̄MG (st , g, at ) ; since theworks [6], [11], which indicates that the agent wishes tot=0
achieve the goal it is currently at, and is similar to an option’s
policies are independent of task [11][Lem 2].
termination condition [4]. The transition dynamics update the= w · Q̄∗G
environment state and constraints set to true when a regularaction is taken, and use the labelling function to return the setof propositions achieved when the agent decides to terminate.
We now have agents capable of solving any logical andFinally, the agent receives the regular environment reward
linear composition of tasks by learning a finite set of basewhen taking an action, but a task-specific goal reward when it
skills Q̄∗G for task primitives MG . We refer to this basis set
terminates. We will assume that the environment and taskof skills as skill primitives. Given this compositional ability
specific rewards are such that the optimal policies for allover skills, and reward machines that expose the structure oftasks are guaranteed to attain desired reachable goal states—atasks, agents can solve temporally extended tasks with little orcommon example is to have a reward of 1 at desired goal states
no further learning. To achieve this, we define a skill machine
and no rewards everywhere else.
(SM) as a representation of logical and temporal knowledge
Equipped with this definition, we can now define the set ofover skills.
all tasks under consideration:

0.5(a) Office Gridworld(b) Skill machine

Fig. 1: Illustration of (a) the office gridworld where the blue circle represents the agent and (b) the 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.

Definition 4 (Skill Machine). Given a set of propositional with a wG and wU such thatsymbols P with constraints C ⊆ P, their corresponding skill
π ∗ (s, u, a) ∈ arg max δQ (s, u, a),primitives Q̄∗G and task space M, states S and actions A, aaskill machine is a tuple Q̄∗MSA = ⟨U, u0 , F, δu , δQ , wU , wG ⟩ where δ is given by w and w as per Definition 4.
Q
GU
where (i) U , u0 , F , δu are defined as for reward machines;
1(ii) wU : U × U → R is a preference function over state Proof. Let wU (u, ·) = Nδu where Nδu is the number oftransitions; (iii) wG : S × G → R is a preference function possible RM transitions from u. Also let wG (s, u, ·) beover goals; and (v) δQ : S × U × A → [S × A → R] is the 1 for the set of propositions g ∈ 2C that are satisfied
when following π ∗ (s, u), and zero everywhere else. Thenstate-skill function defined by:π ∗ (s, u) ∈ arg maxa δQ (s, u) since wU (u, u′ )Q̄∗u,u′ (s, g, a) is
X X′∗
optimal using Theorem 1 and optimal policies are assumed toδQ (s, u, a) 7→
wG (s, u, g)wU (u, u )Q̄u,u′ (s, g, a),reach task goals.
g∈G u′ ∈U
where Q̄∗u,u′ is the WVF obtained by composing the skill
primitives Q̄∗G according to the Boolean expression for thetransition δu = u′ .
For a given state s in the environment and state u in the skill
machine, the skill machine uses its preference over transitions
wU and goals wG to compute a skill Q(s, a) := δQ (s, u, a)that an agent can use to take an action a. The environment
then transitions to the next state s′ ← P (s, a) and the skill
machine transitions to u′ ← δu (u, L(s, a, s′ )). wU represents
cases where there is not necessarily a single desirable transition
to follow given the current SM state. This is illustrated by the
SM in Figure 1b, where mail and coffee are equally desirable
at the initial state. Similarly, wG represents cases where there
may be a single desirable task, but its goals are not necessarilyequally desirable given the environment state—for example
when the agent needs to first pick up coffee but there are twocoffee locations. Interestingly, there always exists a choice forwU and wG that is optimal with respect to the corresponding
reward machine, as shown in Theorem 2.
∗

Theorem 2. Let π (s, u) be the optimal policy for the crossproduct MDP between a reward machine and a task space M,
with C = P. Then there exists a corresponding skill machine

Theorem 2 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 machineby planning over simple reward machines.
C. From Reward Machines to Skill Machines
In the previous section, we introduced skill machines andshowed that they can be used to represent the logical andtemporal composition of skills needed to solve reward machines.
We now show how for simple RMs their approximate SM canbe obtained zero-shot without further learning. To achieve this,
we first plan over the reward machine (using value iteration,for example) to obtain Q-values for each transition. We thenselect 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 satisfiable from any environment
state, this still covers many tasks of interest. In particular, thisholds for any RM with non-zero rewards of RMAX at accepting
transitions,1 as shown in Theorem 3.
Theorem 3. Let RMSA = ⟨U, u0 , F, δu , δM ⟩ be a satisfiable
simple reward machine with non-zero rewards RMAX only for1 Accepting transitions are transitions at which the high level task—described,
for example, by linear temporal logics—is satisfied.

(a) Reward machine(b) Value iterated RM(c) Skill machine

Fig. 2: The reward machine, value iterated RM and skill machine for the task “Deliver coffee to the office without breaking any
decoration”. This task is specified using LTL as (F (K ∧ X(F x))) ∧ (G ¬✽)), where F = F inally, X = neXt, G = Globally
are LTL operators. The corresponding RM is obtained by converting the LTL into a finite state machine and then giving a
reward of 1 for accepting transitions and 0 otherwise. The black dots labeled t represent terminal states.
accepting transitions, and for which all valid transitions (u, u′ )are achievable from any state s ∈ S. Define the skill machine
Q̄∗MSA = ⟨U, u0 , F, δu , δQ , wU , wG ⟩ with(
1 if u′ = arg maxu′′ Q∗ (u, u′′ ),′wU (u, u ) :=0 otherwise(P
1 if g = arg maxg′ maxa u′ wU Q̄∗u,u′ 2 ,wG (s, u, g) :=0 otherwise
where Q∗ is the optimal transition-value function for RPSA .
Then following the policy π ∗ (s, u) ∈ arg maxa δQ (s, u, a) willreach an accepting transition.

Algorithm 1: Few-shot Q-learning using skill machines
Input : γ, α, P, L, U, u0 , F, δu , δQ
Initialise : Q(s, u, a)foreach episode do
Observe initial state s ∈ S and get initial u ← u0
while episode is not done do/* Using the composed skill δQ
in the behaviour policy*/a←arg max (max{γQ(s, u, a), (1 − γ)δQ (s, u, a)})a∈A

if Bernoulli(1-ϵ) = 1 else a random action
Take action a and observe next state s′
Get reward r ← δr (u)(s, a, s′ ) and the next RM
state u′ ← δu (u, L(s, a, s′ ))αQ(s,− r if s′ is terminalor u′ ∈ F else
h u, a) ←i′′ ′r + γ maxQ(s , u , a )
a′
′
s←s

Proof. This follows from the optimality of π ∗ (s, u) and Q∗ ,since each transition of the RM is satisfiable from any
environment state.
Theorem 3 is critical as it provides soundness guarantees,
ensuring that the policy derived from the skill machine will
always satisfy the task requirements when it is possible
to do so. Finally, in cases where the composed skill δQobtained from the approximate SM is not sufficiently optimal,
we can use any off-policy algorithm to learn a new skill
Qnew few-shot. This is achieved by using the maximising
Q-values max{βQnew , (1 − β)δQ } in the behaviour 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δQ is greedy with respect to both goals and RM transitions.
Algorithm 1 illustrates this process with Q-learning whereβ = γ, which guarantees convergence since δQ will neverdominate the optimal Q-values in the max.
IV. E XPERIMENTS

Task

Description

1

Deliver coffee to the office without breaking any
decoration
Patrol rooms A, B, C, and D without breaking any
decoration
Deliver coffee and mail to the office without
breaking any decoration
Deliver mail to the office until there is no mail left,then deliver coffee to office while there are people
in the office, then patrol rooms A-B-C-D-A, andnever break a decoration

2
3
4

TABLE I: Tasks in the Office Gridworld.

A. Zero-shot temporal logics
We consider the Office Gridworld domain [13] depicted in
Figure 1a. This environment is used as a multitask domain,

consisting of the four tasks described in Table I. We begin bytraining the agent on all 10 base tasks of the Office Gridworld

(a) Room A(b) Room B(c) Room C(d) Room D(e) Decoration ✽(f) Coffee K(g) Mail B(h) Office x(i) Mails present B+(j) People present x+

Fig. 3: The policies (arrows) and value functions (heat map)of the base primitive tasks in the Office Gridworld. These are
obtained by maximising over the goals of the learned WVFs.
All errors in the figures are due to training the WVFs for200000 time steps, hence not to convergence.

(Figure 3) and then evaluating how long it takes it to learn a
policy that can solve all four tasks. The agent iterates throughthe tasks, changing from one to the next after each episode.
In all of our experiments, we compare the performance ofskill machines with that of state-of-the-art RM-based learning
approaches like counterfactual RMs (CRM)—where the Qfunctions are updated with respect to all possible RM transitions
from a given environment state—and hierarchical RMs (HRM)—
where an agent learns options per RM state that are groundedin the environment states [13]. Note that CRM and HRM aretheoretically capable of solving the multi-task problem setup
because they can use experience from solving one task to update
the policies for solving other tasks. However, skill machines
can additionally share both experience between tasks whenlearning the skill primitives, as well as use the composition ofthese primitives to generalise to more difficult tasks without
further learning.
We run 80 independent trials and report the average reward
per step across the four tasks in Table I. In addition to learning
all four tasks, we also experiment with Tasks 3 and 4 inisolation. For these experiments, 80 independent trials are run
and the average reward per step computed. In the single task
domains, the difference between CRM, HRM, skill machines
and Q-learning should be less pronounced, since CRM, HRM
and skill machines now cannot leverage prior knowledge. Thus,
the comparison between multi-task and single-task learning inthis setting will evaluate the benefit of the compositionality
afforded by skill machines.
The results of these three experiments are shown in Figure
4. Regular Q-learning struggles to learn Task 3 and completely
fails to learn the hardest task (Task 4). Additionally, noticethat while QL and CRM can theoretically learn the tasks
optimally given infinite time, only HRM and SM are able tolearn hard long horizon tasks in practice. It is important tonote that we train all algorithms for the same amount of time
during these experiments and previous work [11] has shownthat learning the WVFs takes longer than learning task-specificskills. In addition, the skill machines are being used to zero-shot
generalise to the office tasks using skill primitives. Thus using
the skill machines in isolation (labelled SM and shown in blue
on Figure 4) may provide sub-optimal performance comparedto the task-specific agents, since the skill machines have notbeen 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 dueto the amortised nature of learning the WVF will achieve its
final rewards from the first epoch.
B. Few-shot Temporal Logics
It is possible to pair the skill machines with a learningalgorithm such as Q-learning to achieve few-shot generalisation.
From the results shown in Figure 4, it is apparent that skill
machines paired with Q-learning (labelled QL-SM and shownin orange on Figure 4) achieves the best performance for boththe single-task and multi-task setting. While it is not clear
from the rewards that adding Q-learning provides significant
improvements to the skill machine, their trajectories showthat Q-learning does indeed improve on the skill machinepolicies when they are not optimal (Figure 5). Additionally,skill machines with Q-learning always begin with a significantly



602XUV4/602XUV&50&5056
+50+5056
4/
4/56








7RWDO5HZDUG

7RWDO5HZDUG

7RWDO5HZDUG

602XUV4/602XUV&50&5056
+50+5056
4/
4/56



















(SLVRGHV




H

(a) Task 3602XUV4/602XUV&50&5056
+50+5056
4/
4/56

















(SLVRGHV




H



(b) Task 4









(SLVRGHV




H

(c) Multiple tasks (1-4)

Fig. 4: Average returns during training in the Office Gridworld.

C. Moving Targets Domain

Fig. 6: Moving Targets domain

Task

Description

1
2

Pick up any object. Repeat this forever.
Pick up blue then purple objects, then objects thatare neither blue nor purple. Repeat this forever.
Pick up blue objects or squares, but never blue
squares. Repeat this forever.
Pick up non-square blue objects, then non-bluesquares in that order. Repeat this forever.

3
4

TABLE II: Tasks in the Moving Targets domain. Objects
respawn in random positions when picked.

We now demonstrate our temporal logic composition approach in a canonical object collection domain with highdimensional pixel observations [11] (Figure 6). 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 [16]. There are 3 object
colours—beige, blue, purple—and 2 object shapes—squares,
circles. To learn the WVF for a given task primitive, we use
goal oriented Q-learning [11] where the agent keeps track ofreached goals and uses deep Q-learning [17] to update the
WVF with respect to all seen goals at every time step.
We first train the agent on three base task primitives: pick up
blue objects, pick up purple objects, and pick up squares. We
then use the learned skill primitives to solve multiple temporal
logic tasks. Figure 7 shows the average returns of the optimal
policies and SM policies for the four tasks described in Table IIwith a maximum of 50 steps per episode. Our results show thateven 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 forvery challenging tasks like Tasks 3 and 4 (where the agent mustsatisfy difficult temporal constraints), the compounding effectof the sub-optimal policies sometimes leads to failures. In suchcases, learning new skills few-shot by leveraging the SM would
guarantee convergence to optimal policies as demonstrated in
Section IV-B.

40

Average Returns

higher reward and converge on their final performance fasterthan all benchmarks—except the zero-shot one which is (near)
optimal in all cases. The speed of learning is due to thecompositionality 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 specificQ-learner. In sum, skill machines provide fast compositionof skills and achieve optimal performance compared to all
benchmarks when paired with a learning algorithm.

OptimalComposedRandom

30
20
10
0
Blue

PurpleSquare

1
Tasks

2

3

4

Fig. 7: Average returns over 100 runs for tasks in Table II.

(a) Task 1 zero-shot(b) Task 2 zero-shot(c) Task 3 zero-shot(d) Task 1 few-shot(e) Task 2 few-shot(f) Task 3 few-shot

Fig. 5: Agent trajectories using the skill machine without further learning (top) and with further learning (bottom).

V. R ELATED W ORK

standard reward signal for an RL agent [26], [27]. Some recent
works [28] show how to perform reward shaping given LTL
One family of approaches to concurrent composition lever- specifications, while others [29] develop a formal language thatages forms of regularisation to achieve semantically meaningful encodes tasks as sequences, conjunctions and disjunctions of
disjunction [7], [9] or conjunction [18], [19]. Weighted compo- subtasks. This is then used to obtain a shaped reward function
sition has also been demonstrated; for example, previous work that can be used for learning. All of these approaches focus on[20] learn weights to compose existing policies multiplicatively how an agent can improve learning given such specifications or
to solve new tasks. Approaches that leverage the successor structure, but we show how an explicitly compositional agent
feature (SF) framework [21] are capable of solving tasks defined can immediately solve such tasks using WVFs without further
by linear preferences over features [16]. Recent work [10] learning.
shows that an SF basis can be learned that is sufficient to
VI. C ONCLUSION
span the space of tasks under consideration, and one canalso determine which policies should be stored in limited
We proposed skill machines—finite state machines that canmemory so as to maximise performance on future tasks [22]. be learned from reward machines—that allow agents to solve
In contrast to these approaches, our framework allows for both extremely complex tasks involving temporal and concurrent
concurrent composition (with operators such as negation that composition. We demonstrated how skills can be learned andother approaches do not support) and temporal composition encoded in a specific form of goal-oriented value function that,such as LTL.
when combined with the learned skill machines, are sufficient
A popular way of achieving temporal composition is through for solving subsequent tasks without further learning. Our
the options framework [4], [23]. Here, high-level skills are approach guarantees that the resulting policy adheres to thefirst discovered and then executed sequentially to solve a task logical task specification, which provides assurances of safety[24], [25]. One can leverage the SF and options framework and verifiability to the agent’s decision making, importantand learn how to linearly combine skills, chaining them characteristics that are necessary if we are to ever deploy
sequentially to solve temporal tasks [6]. However, these options- RL agents in the real world. While the resulting behaviour
based approaches offer a relatively simple form of temporal is provably satisficing, empirical results demonstrate that thecomposition. By contrast, we are able to solve tasks expressed agent’s performance is near optimal; further fine-tuning canthrough regular languages zero-shot, while providing soundness be performed should optimality be required, which greatly
guarantees.
improves the sample efficiency. We see this approach as aWork has also centred on approaches to defining tasks step towards truly generally intelligent agents, capable ofusing human-readable logic operators. For example, one can immediately solving human-specifiable tasks in the real world
specify tasks using LTL, which is then used to generate a with no further learning.

R EFERENCES[1] A. P. Badia, B. Piot, S. Kapturowski, P. Sprechmann, A. Vitvitskyi,
Z. D. Guo, and C. Blundell, “Agent57: Outperforming the Atari humanbenchmark,” in International Conference on Machine Learning, 2020,
pp. 507–517.
[2] S. Levine, C. Finn, T. Darrell, and P. Abbeel, “End-to-end training ofdeep visuomotor policies,” The Journal of Machine Learning Research,
vol. 17, no. 1, pp. 1334–1373, 2016.
[3] J. Arjona-Medina, M. Gillhofer, M. Widrich, T. Unterthiner, J. Brandstetter, and S. Hochreiter, “Rudder: Return decomposition for delayed
rewards,” Advances in Neural Information Processing Systems, vol. 32,
2019.
[4] R. Sutton, D. Precup, and S. Singh, “Between MDPs and semi-MDPs: A
framework for temporal abstraction in reinforcement learning,” Artificial
Intelligence, vol. 112, no. 1-2, pp. 181–211, 1999.
[5] M. Taylor and P. Stone, “Transfer learning for reinforcement learning
domains: a survey,” Journal of Machine Learning Research, vol. 10, pp.
1633–1685, 2009.
[6] A. Barreto, D. Borsa, S. Hou, G. Comanici, E. Aygün, P. Hamel,
D. Toyama, S. Mourad, D. Silver, D. Precup et al., “The option
keyboard: Combining skills in reinforcement learning,” Advances in
Neural Information Processing Systems, vol. 32, 2019.
[7] E. Todorov, “Compositionality of optimal control laws,” in Advances in
Neural Information Processing Systems, 2009, pp. 1856–1864.
[8] A. Saxe, A. Earle, and B. Rosman, “Hierarchy through composition withmultitask LMDPs,” International Conference on Machine Learning, pp.
3017–3026, 2017.
[9] B. Van Niekerk, S. James, A. Earle, and B. Rosman, “Composing valuefunctions in reinforcement learning,” in International Conference on
Machine Learning, 2019, pp. 6401–6409.
[10] S. Alver and D. Precup, “Constructing a good behavior basis fortransfer using generalized policy updates,” in International Conference
on Learning Representations, 2022.
[11] G. Nangue Tasse, S. James, and B. Rosman, “A Boolean task algebra
for reinforcement learning,” Advances in Neural Information Processing
Systems, vol. 33, pp. 9497–9507, 2020.
[12] V. Cohen, G. Nangue Tasse, N. Gopalan, S. James, M. Gombolay, andB. Rosman, “Learning to follow language instructions with compositional
policies,” in AAAI Fall Symposium Series, 2021.
[13] R. T. Icarte, T. Klassen, R. Valenzano, and S. McIlraith, “Using
reward machines for high-level task specification and decomposition
in reinforcement learning,” in International Conference on Machine
Learning, 2018, pp. 2107–2116.
[14] A. Pnueli, “The temporal logic of programs,” in 18th Annual Symposium
on Foundations of Computer Science. IEEE, 1977, pp. 46–57.
[15] G. Nangue Tasse, S. James, and B. Rosman, “World value functions:
Knowledge representation for multitask reinforcement learning,” inThe 5th Multi-disciplinary Conference on Reinforcement Learning and
Decision Making (RLDM), 2022.
[16] A. Barreto, S. Hou, D. Borsa, D. Silver, and D. Precup, “Fast reinforcement learning with generalized policy updates,” Proceedings of the
National Academy of Sciences, vol. 117, no. 48, pp. 30 079–30 087, 2020.
[17] V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare,A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski et al., “Human-level
control through deep reinforcement learning,” Nature, vol. 518, no. 7540,
p. 529, 2015.
[18] T. Haarnoja, V. Pong, A. Zhou, M. Dalal, P. Abbeel, and S. Levine,“Composable deep reinforcement learning for robotic manipulation,” in2018 IEEE International Conference on Robotics and Automation, 2018,
pp. 6244–6251.
[19] J. Hunt, A. Barreto, T. Lillicrap, and N. Heess, “Composing entropic
policies using divergence correction,” in International Conference on
Machine Learning, 2019, pp. 2911–2920.
[20] X. B. Peng, M. Chang, G. Zhang, P. Abbeel, and S. Levine, “MCP:
Learning composable hierarchical control with multiplicative compositional policies,” in Advances in Neural Information Processing Systems,
2019, pp. 3686–3697.
[21] A. Barreto, W. Dabney, R. Munos, J. J. Hunt, T. Schaul, H. P. vanHasselt, and D. Silver, “Successor features for transfer in reinforcement
learning,” in Advances in Neural Information Processing Systems, 2017,
pp. 4055–4065.
[22] M. Nemecek and R. Parr, “Policy caches with successor features,” inInternational Conference on Machine Learning, 2021, pp. 8025–8033.

[23] P. Bacon, J. Harb, and D. Precup, “The option-critic architecture,” inThirty-First AAAI Conference on Artificial Intelligence, 2017.
[24] G. Konidaris and A. Barto, “Skill discovery in continuous reinforcement
learning domains using skill chaining,” Advances in Neural Information
Processing Systems, vol. 22, 2009.
[25] A. Bagaria and G. Konidaris, “Option discovery using deep skill chaining,”
in International Conference on Learning Representations, 2019.
[26] X. Li, C.-I. Vasile, and C. Belta, “Reinforcement learning with temporal
logic rewards,” in 2017 IEEE/RSJ International Conference on Intelligent
Robots and Systems, 2017, pp. 3834–3839.
[27] M. Littman, U. Topcu, J. Fu, C. Isbell, M. Wen, and J. MacGlashan,“Environment-independent task specifications via GLTL,” arXiv preprint
arXiv:1704.04341, 2017.
[28] A. Camacho, R. T. Icarte, T. Klassen, R. Valenzano, and S. McIlraith,“LTL and beyond: Formal languages for reward function specification in
reinforcement learning.” in International Joint Conferences on Artificial
Intelligence, vol. 19, 2019, pp. 6065–6073.
[29] K. Jothimurugan, R. Alur, and O. Bastani, “A composable specification language for reinforcement learning tasks,” Advances in Neural
Information Processing Systems, vol. 32, 2019.