Year: 2019

Abstract:
We propose a framework for defining a Boolean algebra over the space of tasks. This allows us to formulate new tasks in terms of the negation, disjunction and conjunction of a set of base tasks. We then show that by learning goal-oriented value functions and restricting the transition dynamics of the tasks, an agent can solve these new tasks with no further learning. We prove that by composing these value functions in specific ways, we immediately recover the optimal policies for all tasks expressible under the Boolean algebra. We verify our approach in two domains—including a high-dimensional video game environment requiring function approximation—where an agent first learns a set of base skills, and then composes them to solve a super-exponential number of new tasks.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has achieved recent success in a number of difficult, high-dimensional environments (Mnih et al., 2015; Levine et al., 2016; Lillicrap et al., 2016; Silver et al., 2017). However, these methods generally require millions of samples from the environment to learn optimal behaviours, limiting their real-world applicability. A major challenge is thus in designing sample-efficient agents that can transfer their existing knowledge to solve new tasks quickly. This is particularly important for agents in a multitask or lifelong setting, since learning to solve complex tasks from scratch is typically infeasible.
One approach to transfer is composition (Todorov, 2009), which allows an agent to leverage existing skills to build complex, novel behaviours. These newly-formed skills can then be used to solve or speed up learning in a new task. In this work, we focus on concurrent composition, where existing base skills are combined to produce new skills (Todorov, 2009; Saxe et al., 2017; Haarnoja et al., 2018; Van Niekerk et al., 2019; Hunt et al., 2019; Peng et al., 2019). This differs from other forms of composition, such as options (Sutton et al., 1999) and hierarchical RL (Bacon et al., 2017), where actions and skills are chained in a temporal sequence.
In this work, we define a Boolean algebra over the space of tasks and optimal value functions. This extends previous composition results to encompass all Boolean operators: conjunction, disjunction, and negation. We then prove that there exists a homomorphism between the task and value function algebras. Given a set of base tasks that have been previously solved by the agent, any new task written as a Boolean expression can immediately be solved without further learning, resulting in a zero-shot super-exponential explosion in the agent’s abilities.
We illustrate our approach in a simple domain, where an agent first learns to reach a number of rooms, after which it can then optimally solve any task expressible in the Boolean algebra. We then demonstrate composition in high-dimensional video game environments, where an agent first learns to collect different objects, and then compose these abilities to solve complex tasks immediately. Our results show that, even when function approximation is required, an agent can leverage its existing skills to solve new tasks without further learning.

heading: 2 PRELIMINARIES
text: We consider tasks modelled by Markov Decision Processes (MDPs). An MDP is defined by the tuple (S,A, ρ, r), where (i) S is the state space, (ii) A is the action space, (iii) ρ is a Markov transition
kernel (s, a) 7→ ρ(s,a) from S × A to S, and (iv) r is the real-valued reward function bounded by [rMIN, rMAX]. In this work, we focus on stochastic shortest path problems (Bertsekas & Tsitsiklis, 1991), which model tasks in which an agent must reach some goal. We therefore consider the class of undiscounted MDPs with an absorbing set G ⊆ S. The goal of the agent is to compute a Markov policy π from S to A that optimally solves a given task. A given policy π is characterised by a value function V π(s) = Eπ [ ∑∞ t=0 r(st, at)], specifying the expected return obtained under π starting from state s.1 The optimal policy π∗ is the policy that obtains the greatest expected return at each state: V π ∗ (s) = V ∗(s) = maxπ V
π(s) for all s in S. A related quantity is the Q-value function, Qπ(s, a), which defines the expected return obtained by executing a from s, and thereafter following π. Similarly, the optimal Q-value function is given by Q∗(s, a) = maxπ Qπ(s, a) for all s in S and a in A. Finally, we denote a proper policy to be a policy that is guaranteed to eventually reach the absorbing set G (James & Collins, 2006; Van Niekerk et al., 2019). We assume the value functions for improper policies—those that never reach absorbing states—are unbounded below.

heading: 3 BOOLEAN ALGEBRAS FOR TASKS AND VALUE FUNCTIONS
text: In this section, we develop the notion of a Boolean task algebra, allowing us to perform logical operations—conjunction (∧), disjunction (∨) and negation (¬)—over the space of tasks. We then show that, having solved a series of base tasks, an agent can use its knowledge to solve tasks expressible as a Boolean expression over those tasks, without any further learning.
We consider a family of related MDPsM restricted by the following assumptions: Assumption 1. For all tasks in a set of tasks M, (i) the tasks share the same state space, action space and transition dynamics, (ii) the transition dynamics are deterministic, (iii) reward functions between tasks differ only on the absorbing set G, and (iv) the set of possible terminal rewards consists of only two values. That is, for all (g, a) in G × A, we have that r(g, a) ∈ {r∅, rU} ⊂ R with r∅ ≤ rU . For all non-terminal states, we denote the reward rs,a to emphasise that it is constant across tasks. Assumption 2. For all tasks in a set of tasksM which adhere to Assumption 1, the set of possible terminal rewards consists of only two values. That is, for all (g, a) in G ×A, we have that r(g, a) ∈ {r∅, rU} ⊂ R with r∅ ≤ rU . For all non-terminal states, we denote the reward rs,a to emphasise that it is constant across tasks.
Assumption 1 is similar to that of Todorov (2007) and identical to Van Niekerk et al. (2019), and imply that each task can be uniquely specified by its reward function. Furthermore, we note that Assumption 2 is only necessary to formally define the Boolean algebra. Although we have placed restrictions on the reward functions, the above formulation still allows for a large number of tasks to be represented. Importantly, sparse rewards can be formulated under these restrictions.

heading: 3.1 A BOOLEAN ALGEBRA FOR TASKS
text: An abstract Boolean algebra is a set B equipped with operators ¬,∨,∧ that satisfy the Boolean axioms of (i) idempotence, (ii) commutativity, (iii) associativity, (iv) absorption, (v) distributivity, (vi) identity, and (vii) complements.2 Given the above definitions and the restrictions placed on the set of tasks we consider, we can now define a Boolean algebra over a set of tasks. Theorem 1. LetM be a set of tasks. DefineMU ,M∅ ∈M to be tasks with the respective reward functions
rMU : S ×A → R (s, a) 7→ { rU , if s ∈ G rs,a, otherwise.
rM∅ : S ×A → R (s, a) 7→ { r∅, if s ∈ G rs,a, otherwise.
1Since we consider undiscounted MDPs, we can ensure the value function is bounded by augmenting the state space with a virtual state ω such that ρ(s,a)(ω) = 1 for all (s, a) in G ×A, and r = 0 after reaching ω.
2We provide a description of these axioms in the Appendix.
Then M forms a Boolean algebra with universal bounds M∅ and MU when equipped with the following operators: ¬ : M→M
M 7→ (S,A, ρ, r¬M ), where r¬M : S ×A → R (s, a) 7→ ( rMU (s, a) + rM∅(s, a) ) − rM (s, a)
∨ : M×M→M (M1,M2) 7→ (S,A, ρ, rM1∨M2), where rM1∨M2 : S ×A → R (s, a) 7→ max{rM1(s, a), rM2(s, a)} ∧ : M×M→M
(M1,M2) 7→ (S,A, ρ, rM1∧M2), where rM1∧M2 : S ×A → R (s, a) 7→ min{rM1(s, a), rM2(s, a)}
Proof. See Appendix.
Theorem 1 allows us to compose existing tasks together to create new tasks in a principled way. Figure 1 illustrates the semantics for each of the Boolean operators in a simple environment.

heading: 3.2 EXTENDED VALUE FUNCTIONS
text: The reward and value functions described in Section 2 are insufficient to solve tasks specified by the Boolean algebra above. We therefore extend these to define goal-oriented versions of the reward and value function, given by the following two definitions: Definition 1. The extended reward function r̄ : S × G ×A → R is given by the mapping
(s, g, a) 7→ { N if g 6= s ∈ G r(s, a) otherwise,
(1)
where N ≤ min{rMIN, (rMIN − rMAX)D}, and D is the diameter of the MDP (Jaksch et al., 2010).3
To understand why standard value functions are insufficient, consider two tasks that have multiple different goals, but at least one common goal. Clearly, there is a meaningful conjunction between them—namely, achieving the common goal. Now consider an agent that learns standard value functions for both tasks, and which is then required to solve their conjunction without further learning. Note that this is impossible in general, since the regular value function for each task only represents the value of each state with respect to the nearest goal. That is, for all states where the nearest goal for each task is not the common goal, the agent has no information about that common goal. Conversely, by learning extended value functions, the agent is able to learn the value of achieving all goals, and not simply the nearest one.
Because we require that tasks share the same transition dynamics, we also require that the absorbing set of states is shared. Thus the extended reward function adds the extra constraint that, if the agent enters a terminal state for a different task, it should receive the largest penalty possible. In practice, we can simply set N to be the lowest finite value representable by the data type used for rewards. Definition 2. The extended Q-value function Q̄ : S × G ×A → R is given by the mapping
(s, g, a) 7→ r̄(s, g, a) + ∫ S V̄ π̄(s′, g)ρ(s,a)(ds ′), (2)
where V̄ π̄(s, g) = Eπ̄ [ ∑∞ t=0 r̄(st, g, at)]. The extended Q-value function is similar to universal value function approximators (UVFAs) (Schaul et al., 2015), but differs in that it uses the extended reward function definition. It is also similar to DG functions (Kaelbling, 1993), except here we use task-dependent reward functions, as opposed to measuring distance between states.
The standard reward functions and value functions can be recovered from their extended versions through the following lemma.
3The diameter is defined as D = maxs 6=s′∈S minπ E [T (s′|π, s)], where T is the number of timesteps required to first reach s′ from s under π.
Lemma 1. Let rM , r̄M , Q∗M , Q̄∗M be the reward function, extended reward function, optimal Qvalue function, and optimal extended Q-value function for a task M in M. Then for all (s, a) in S ×A, we have (i) rM (s, a) = max
g∈G r̄M (s, g, a), and (ii) Q∗M (s, a) = max g∈G Q̄∗M (s, g, a).

heading: Proof.
text: (i):
max g∈G r̄M (s, g, a) = { max{N, rM (s, a)}, if s ∈ G max g∈G rM (s, a), otherwise.
= rM (s, a) (N ≤ rMIN ≤ rM (s, a) by definition).
(ii): Each g in G can be thought of as defining an MDP Mg := (S,A, ρ, rMg ) with reward function rMg (s, a) := r̄M (s, g, a) and optimal Q-value function Q ∗ Mg
(s, a) = Q̄∗M (s, g, a). Then using (i) we have rM (s, a) = max
g∈G rMg (s, a) and from Van Niekerk et al. (2019, Corollary 1), we
have that Q∗M (s, a) = max g∈G Q∗Mg (s, a) = maxg∈G Q̄∗M (s, g, a).
In the same way, we can also recover the optimal policy from these extended value functions by first applying Lemma 1, and acting greedily with respect to the resulting value function. Lemma 2. Denote S− = S \ G as the non-terminal states ofM. Let M1,M2 ∈M, and let each g in G define MDPs M1,g and M2,g with reward functions rM1,g := r̄M1(s, g, a) and rM2,g := r̄M2(s, g, a) for all (s, a) in S ×A.

heading: Then for all g in G and s in S−,
text: π∗g(s) ∈ arg max a∈A Q∗M1,g (s, a) iff π ∗ g(s) ∈ arg max a∈A Q∗M2,g (s, a).
Proof. See Appendix.
Combining Lemmas 1 and 2, we can extract the greedy action from the extended value function by first maximising over goals, and then selecting the maximising action: π∗(s) ∈ arg maxa∈Amaxg∈G Q̄
∗(s, g, a). If we consider the extended value function to be a set of standard value functions (one for each goal), then this is equivalent to first performing generalised policy improvement (Barreto et al., 2017), and then selecting the greedy action.
Finally, much like the regular definition of value functions, the extended Q-value function can be written as the sum of rewards received by the agent until first encountering a terminal state.
Corollary 1. Denote G∗s:g,a as the sum of rewards starting from s and taking action a up until, but not including, g. Then let M ∈ M and Q̄∗M be the extended Q-value function. Then for all s ∈ S, g ∈ G, a ∈ A, there exists a G∗s:g,a ∈ R such that
Q̄∗M (s, g, a) = G ∗ s:g,a + r̄M (s ′, g, a′), where s′ ∈ G and a′ = arg max b∈A r̄M (s ′, g, b).
Proof. This follows directly from Lemma 2. Since all tasks M ∈M share the same optimal policy π∗g up to (but not including) the goal state g ∈ G, their return G π∗g T−1 = ∑T−1 t=0 rM (st, π ∗ g(st)) is the same up to (but not including) g.

heading: 3.3 A BOOLEAN ALGEBRA FOR VALUE FUNCTIONS
text: In the same manner we constructed a Boolean algebra over a set of tasks, we can also do so for a set of optimal extended Q-value functions for the corresponding tasks. Theorem 2. Let Q̄∗ be the set of optimal extended Q̄-value functions for tasks in M. Define Q̄∗∅, Q̄ ∗ U ∈ Q̄∗ to be the optimal Q̄-functions for the tasks M∅,MU ∈ M. Then Q̄∗ forms a Boolean algebra when equipped with the following operators:
¬ : Q̄∗ → Q̄∗
Q̄∗ 7→ ¬Q̄∗, where ¬Q̄∗ : S × G ×A → R (s, g, a) 7→ ( Q̄∗U (s, g, a) + Q̄ ∗ ∅(s, g, a) ) − Q̄∗(s, g, a)
∨ : Q̄∗ × Q̄∗ → Q̄∗
(Q̄∗1, Q̄ ∗ 2) 7→ Q̄∗1 ∨ Q̄∗2, where Q̄∗1 ∨ Q̄∗2 : S × G ×A → R
(s, g, a) 7→ max{Q̄∗1(s, g, a), Q̄∗2(s, g, a)}
∧ : Q̄∗ × Q̄∗ → Q̄∗
(Q̄∗1, Q̄ ∗ 2) 7→ Q̄∗1 ∧ Q̄∗2, where Q̄∗1 ∧ Q̄∗2 : S × G ×A → R
(s, g, a) 7→ min{Q̄∗1(s, g, a), Q̄∗2(s, g, a)}
Proof. See Appendix.

heading: 3.4 BETWEEN TASK AND VALUE FUNCTION ALGEBRAS
text: Having established a Boolean algebra over tasks and extended value function, we finally show that there exists an equivalence between the two. As a result, if we can write down a task under the Boolean algebra, we can immediately write down the optimal value function for the task. Theorem 3. Let F : M → Q̄∗ be any map fromM to Q̄∗ such that F(M) = Q̄∗M for all M in M. Then F is a homomorphism.
Proof. See Appendix.

heading: 4 ZERO-SHOT TRANSFER THROUGH COMPOSITION
text: We can use the theory developed in the previous sections to perform zero-shot transfer by first learning extended value functions for a set of base tasks, and then composing them to solve new tasks expressible under the Boolean algebra. To demonstrate this, we conduct a series of experiments in a Four Rooms domain (Sutton et al., 1999), where an agent must navigate in a grid world to a particular location. The agent can move in any of the four cardinal directions at each timestep, but colliding with a wall leaves the agent in the same location. The transition dynamics are deterministic, and rewards are −0.1 for all non-terminal states, and 1 at the goal.

heading: 4.1 LEARNING BASE TASKS
text: We use a modified version of Q-learning (Watkins, 1989) to learn extended Q-value functions described previously. Our algorithm differs in a number of ways from standard Q-learning: we keep track of the set of terminating states seen so far, and at each timestep we update the extended Q-value function with respect to both the current state and action, as well as all goals encountered so far. We also use the definition of the extended reward function, and so if the agent encounters a terminal state of a different task, it receives reward N . The full pseudocode is listed in the Appendix.
If we know the set of goals (and hence potential base tasks) upfront, then it is easy to select a minimal set of base tasks that can be composed to produce the largest number of composite tasks. We first assign a Boolean label to each goal in a table, and then use the columns of the table as base tasks. The goals for each base task are then those goals with value 1 according to the table. In this domain, the two base tasks we select are MT, which requires that the agent visit either of the top two rooms, and ML, which requires visiting the two left rooms. We illustrate this selection procedure in the Appendix.

heading: 4.2 BOOLEAN COMPOSITION
text: Having learned the optimal extended value functions for our base tasks, we can now leverage Theorems 1–3 to solve new tasks with no further learning. Figure 2 illustrates this composition, where an agent is able to immediately solve complex tasks such as exclusive-or. We illustrate a few composite tasks here, but note that in general, if we have K base tasks, then a Boolean algebra allows for 22 K
new tasks to be constructed. Thus having trained on only two tasks, our agent has enough information to solve a total of 16 composite tasks.
By learning extended value functions, an agent can subsequently solve a massive number of tasks; however, the upfront cost of learning is likely to be higher. We investigate the trade-off between the two approaches by investigating how the sample complexity scales with the number of tasks. We compare to Van Niekerk et al. (2019), who used regular value functions to demonstrate optimal disjunctive composition. We note that while the upfront learning cost is therefore lower, the number of tasks expressible using only disjunction is 2K−1, which is significantly less than the full Boolean algebra. We also test using an extended version of the Four Rooms domain, where additional goals are placed along the sides of all walls, resulting in a total of 40 goals. Empirical results are illustrated by Figure 3.
Our results show that while additional samples are needed to learn an extended value function, the agent is able to expand the tasks it can solve super-exponentially. Furthermore, the number of base tasks we need to solve is only logarithmic in the number of goal states. For an environment with K goals, we need to learn only blog2Kc+ 1 base tasks, as opposed to the disjunctive approach which requires K base tasks. Thus by sacrificing sample efficiency initially, we achieve an exponential increase in abilities compared to previous work (Van Niekerk et al., 2019).

heading: 5 COMPOSITION WITH FUNCTION APPROXIMATION
text: Finally, we demonstrate that our compositional approach can also be used to tackle high-dimensional domains where function approximation is required. We use the same video game environment as Van Niekerk et al. (2019), where an agent must navigate a 2D world and collect objects of different shapes and colours. The state space is an 84×84 RGB image, and the agent is able to move in any of the four cardinal directions. The agent also possesses a pick-up action, which allows it to collect an object when standing on top of it. There are two shapes (squares and circles) and three colours (blue, beige and purple) for a total of six unique objects. The position of the agent is randomised at the start of each episode.
We modify deep Q-learning (Mnih et al., 2015) to learn extended action-value functions.4 Our approach differs in that the network takes a goal state as additional input (again specified as an RGB image). Additionally, when a terminal state is encountered, it is added to the collection of goals seen so far, and when learning updates occur, these goals are sampled randomly from a replay buffer. We first learn to solve two base tasks: collecting blue objects, and collecting squares, which can then be composed to solve new tasks immediately.
We demonstrate composition characterised by (i) disjunction, (ii) conjunction and (iii) exclusiveor. This corresponds to tasks where the target items are: (i) blue or square, (ii) blue squares, and (iii) blue or squares, but not blue squares. Figure 4 illustrates sample trajectories, as well as the subsequent composed value functions, for the respective tasks.

heading: 6 RELATED WORK
text: The ability to compose value functions was first demonstrated using the linearly-solvable MDP framework (Todorov, 2007), where value functions could be composed to solve tasks similar to the disjunctive case (Todorov, 2009). Van Niekerk et al. (2019) show that the same kind of composition can be achieved using entropy-regularised RL (Fox et al., 2016), and extend the results to the standard RL setting, where agents can optimally solve the disjunctive case. Using entropy-regularised RL, Haarnoja et al. (2018) approximates the conjunction of tasks by averaging their reward functions, and demonstrates that by averaging the optimal value functions of the respective tasks, the agent can achieve performance close to optimal. Hunt et al. (2019) extends this result by composing value functions to solve the average reward task exactly, which approximates the true conjunctive case. More recently, Peng et al. (2019) introduce a few-shot learning approach to compose policies
4The hyperparameters and network architecture are listed in the Appendix
multiplicatively. Although lacking theoretical foundations, results show that an agent can learn a weighted composition of existing base skills to solve a new complex task. By contrast, we show that zero-shot optimal composition can be achieved for all Boolean operators.

heading: 7 CONCLUSION
text: We have shown how to compose tasks using the standard Boolean algebra operators. These composite tasks can be immediately solved by first learning goal-oriented value functions, and then composing them in a similar manner. Finally, we note that there is much room for improvement in learning the extended value functions for the base tasks. In our experiments, we learned each extended value function from scratch, but it is likely that having learned one for the first task, we could use it to initialise the extended value function for the second task to improve convergence times. One area for improvement lies in efficiently learning the extended value functions, as well as developing better algorithms for solving tasks with sparse rewards. For example, it is likely that approaches such as hindsight experience replay (Andrychowicz et al., 2017) could reduce the number of samples required to learn extended value functions, while Mirowski et al. (2017) provides a method for learning complex tasks with sparse rewards using auxiliary tasks. We leave incorporating these approaches to future work. Our proposed approach is a step towards both interpretable RL— since both the tasks and optimal value functions can be specified using Boolean operators—and the ultimate goal of lifelong learning agents, which are able to solve combinatorially many tasks in a sample-efficient manner.

heading: A APPENDIX

heading: A.1 BOOLEAN ALGEBRA DEFINITION
text: Definition 3. A Boolean algebra is a set B equipped with the binary operators ∨ (disjunction) and ∧ (conjunction), and the unary operator ¬ (negation), which satisfies the following Boolean algebra axioms for a, b, c in B:
(i) Idempotence: a ∧ a = a ∨ a = a. (ii) Commutativity: a ∧ b = b ∧ a and a ∨ b = b ∨ a.
(iii) Associativity: a ∧ (b ∧ c) = (a ∧ b) ∧ c and a ∧ (b ∨ c) = (a ∨ b) ∨ c. (iv) Absorption: a ∧ (a ∨ b) = a ∨ (a ∧ b) = a. (v) Distributivity: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) and a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).
(vi) Identity: there exists 0,1 in B such that 0 ∧ a = 0 0 ∨ a = a 1 ∧ a = a 1 ∨ a = 1
(vii) Complements: for every a in B, there exists an element a′ in B such that a ∧ a′ = 0 and a ∨ a′ = 1.

heading: A.2 PROOF FOR THEOREM 1
text: Theorem 1. LetM be a set of tasks. DefineMU ,M∅ ∈M to be tasks with the respective reward functions
rMU : S ×A → R (s, a) 7→ { rU , if s ∈ G rs,a, otherwise.
rM∅ : S ×A → R (s, a) 7→ { r∅, if s ∈ G rs,a, otherwise.
Then M forms a Boolean algebra with universal bounds M∅ and MU when equipped with the following operators:
¬ : M→M M 7→ (S,A, ρ, r¬M ), where r¬M : S ×A → R
(s, a) 7→ ( rMU (s, a) + rM∅(s, a) ) − rM (s, a)
∨ : M×M→M (M1,M2) 7→ (S,A, ρ, rM1∨M2), where rM1∨M2 : S ×A → R
(s, a) 7→ max{rM1(s, a), rM2(s, a)}
∧ : M×M→M (M1,M2) 7→ (S,A, ρ, rM1∧M2), where rM1∧M2 : S ×A → R
(s, a) 7→ min{rM1(s, a), rM2(s, a)}
Proof. Let M1,M2 ∈M. We show that ¬,∨,∧ satisfy the Boolean properties (i) – (vii).
(i)–(v): These easily follow from the fact that the min and max functions satisfy the idempotent, commutative, associative, absorption and distributive laws.
(vi): Let rMU∧M1 and rM1 be the reward functions forMU ∧M1 and M1 respectively. Then for all (s, a) in S ×A,
rMU∧M1(s, a) = { min{rU , rM1(s, a)}, if s ∈ G min{rs,a, rs,a}, otherwise.
= { rM1(s, a), if s ∈ G rs,a, otherwise.
(rM1(s, a) ∈ {r∅, rU} for s ∈ G)
= rM1(s, a).
ThusMU ∧M1 = M1. SimilarlyMU ∨M1 =MU ,M∅∧M1 =M∅, andM∅∨M1 = M1 . HenceM∅ andMU are the universal bounds ofM.
(vii): Let rM1∧¬M1 be the reward function for M1 ∧ ¬M1. Then for all (s, a) in S ×A,
rM1∧¬M1(s, a) = { min{rM1(s, a), (rU + r∅)− rM1(s, a)}, if s ∈ G min{rs,a, (rs,a + rs,a)− rs,a}, otherwise.
=  r∅, if s ∈ G and rM1(s, a) = rU r∅, if s ∈ G and rM1(s, a) = r∅ rs,a, otherwise.
= rM∅(s, a).
Thus M1 ∧ ¬M1 =M∅, and similarly M1 ∨ ¬M1 =MU .

heading: A.3 PROOF FOR LEMMA 2
text: Lemma 2. Denote S− = S \ G as the non-terminal states ofM. Let M1,M2 ∈M, and let each g in G define MDPs M1,g and M2,g with reward functions
rM1,g := r̄M1(s, g, a) and rM2,g := r̄M2(s, g, a) for all (s, a) in S ×A.

heading: Then for all g in G and s in S−,
text: π∗g(s) ∈ arg max a∈A Q∗M1,g (s, a) iff π ∗ g(s) ∈ arg max a∈A Q∗M2,g (s, a).
Proof. Let g ∈ G, s ∈ S− and let π∗g be defined by
π∗g(s ′) ∈ arg max a∈A Q∗M1,g(s, a) for all s ′ ∈ S.
If g is unreachable from s, then we are done since for all (s′, a) in S ×A we have
g 6= s′ =⇒ rM1,g (s′, a) = { N, if s′ ∈ G rs′,a, otherwise = rM2,g (s ′, a)
=⇒ M1,g = M2,g.
If g is reachable from s, then we show that following π∗g must reach g. Since π ∗ g is proper, it must reach a terminal state g′ ∈ G. Assume g′ 6= g. Let πg be a policy that produces the shortest trajectory
to g. Let Gπ ∗ g and Gπg be the returns for the respective policies. Then,
Gπ ∗ g ≥ Gπg
=⇒ Gπ ∗ g
T−1 + rM1,g (g ′, π∗g(g ′)) ≥ Gπg ,
where G π∗g T−1 = T−1∑ t=0 rM1,g (st, π ∗ g(st)) and T is the time at which g ′ is reached.
=⇒ Gπ ∗ g
T−1 +N ≥ Gπg , since g 6= g′ ∈ G
=⇒ N ≥ Gπg −Gπ ∗ g
T−1
=⇒ (rMIN − rMAX)D ≥ Gπg −G π∗g T−1, by definition of N =⇒ Gπ ∗ g
T−1 − rMAXD ≥ Gπg − rMIND, since Gπg ≥ rMIND
=⇒ Gπ ∗ g
T−1 − rMAXD ≥ 0
=⇒ Gπ ∗ g
T−1 ≥ rMAXD.
But this is a contradiction since the result obtained by following an optimal trajectory up to a terminal state without the reward for entering the terminal state must be strictly less that receiving rMAX for every step of the longest possible optimal trajectory. Hence we must have g′ = g. Similarly, all optimal policies of M2,g must reach g. Hence π∗g(s) ∈ arg max
a∈A Q∗M2,g (s, a). Since M1 and M2 are
arbitrary elements ofM, the reverse implication holds too.

heading: A.4 PROOF FOR THEOREM 2
text: Theorem 2. Let Q̄∗ be the set of optimal extended Q̄-value functions for tasks in M. Define Q̄∗∅, Q̄ ∗ U ∈ Q̄∗ to be the optimal Q̄-functions for the tasks M∅,MU ∈ M. Then Q̄∗ forms a Boolean algebra when equipped with the following operators:
¬ : Q̄∗ → Q̄∗
Q̄∗ 7→ ¬Q̄∗, where ¬Q̄∗ : S × G ×A → R (s, g, a) 7→ ( Q̄∗U (s, g, a) + Q̄ ∗ ∅(s, g, a) ) − Q̄∗(s, g, a)
∨ : Q̄∗ × Q̄∗ → Q̄∗
(Q̄∗1, Q̄ ∗ 2) 7→ Q̄∗1 ∨ Q̄∗2, where Q̄∗1 ∨ Q̄∗2 : S × G ×A → R
(s, g, a) 7→ max{Q̄∗1(s, g, a), Q̄∗2(s, a)}
∧ : Q̄∗ × Q̄∗ → Q̄∗
(Q̄∗1, Q̄ ∗ 2) 7→ Q̄∗1 ∧ Q̄∗2, where Q̄∗1 ∧ Q̄∗2 : S × G ×A → R
(s, g, a) 7→ min{Q̄∗1(s, g, a), Q̄∗2(s, a)}
Proof. Let Q̄∗M1 , Q̄ ∗ M2 ∈ Q̄∗ be the optimal Q̄-value functions for tasks M1,M2 ∈ M with reward functions rM1 and rM2 . We show that ¬,∨,∧ satisfy the Boolean properties (i) – (vii).
(i)–(v): These follow directly from the properties of the min and max functions.
(vi): For all (s, g, a) in S × G ×A, (Q̄∗U ∧ Q̄∗M1)(s, g, a) = min{(Q̄∗U (s, g, a), Q̄∗M1(s, g, a)}
= min{G∗s:g,a + r̄MU (s′, g, a′), G∗s:g,a + r̄M1(s′, g, a′)} (Corollary 1) = G∗s:g,a + min{r̄MU (s′, g, a′), r̄M1(s′, g, a′)} = G∗s:g,a + r̄M1(s ′, g, a′) (since r̄M1(s ′, g, a′) ∈ {r∅, rU , N}) = Q̄∗M1(s, g, a).
Similarly, Q̄∗U ∨ Q̄∗M1 = Q̄∗U , Q̄∗∅ ∧ Q̄∗M1 = Q̄∗∅, and Q̄∗∅ ∨ Q̄∗M1 = Q̄∗M1 .
(vii): For all (s, g, a) in S × G ×A, (Q̄∗M1 ∧ ¬Q̄∗M1)(s, g, a) = min{Q̄∗M1(s, g, a), (Q̄∗U (s, g, a)− Q̄∗∅(s, g, a))− Q̄∗M1(s, g, a)}
= G∗s:g,a + min{r̄M1(s′, g, a′), (r̄MU (s′, g, a′) + r̄M∅(s′, g, a′)) − r̄M1(s′, g, a′)} = G∗s:g,a + r̄M∅(s ′, g, a′) = Q̄∗∅(s, g, a).
Similarly, Q̄∗M1 ∨ ¬Q̄∗M1 = Q̄∗U .

heading: A.5 PROOF FOR THEOREM 3
text: Theorem 3. Let F : M → Q̄∗ be any map fromM to Q̄∗ such that F(M) = Q̄∗M for all M in M. Then F is a homomorphism.
Proof. Let M1,M2 ∈M. Then for all (s, g, a) in S × G ×A, Q̄∗¬M1(s, g, a) = G ∗ s:g,a + r̄¬M1(s ′, g, a′) (from Corollary 1)
= G∗s:g,a + (r̄MU (s ′, g, a′) + r̄M∅(s ′, g, a′))− r̄M1(s′, g, a′) = [ (G∗s:g,a + r̄MU (s ′, g, a′)) + (G∗s:g,a + r̄M∅(s ′, g, a′)) ] − (G∗s:g,a + r̄M1(s′, g, a′))
= [ Q̄∗U (s, g, a) + Q̄ ∗ ∅(s, g, a) ] − Q̄∗M1(s, g, a)
= ¬Q̄∗M1(s, g, a) =⇒ F(¬M1) = ¬F(M1)
Q̄∗M1∨M2(s, g, a) = G ∗ s:g,a + r̄M1∨M2(s ′, g, a′)
= G∗s:g,a + max{r̄M1(s′, g, a′), r̄M2(s′, g, a′′)} = max{G∗s:g,a + r̄M1(s′, g, a′), G∗s:g,a + r̄M2(s′, g, a′′)} = max{Q̄∗M1(s, g, a), Q̄∗M2(s, g, a)} = (Q̄∗M1 ∨ Q̄∗M2)(s, g, a)
=⇒ F(M1 ∨M2) = F(M1) ∨ F(M2). Similarly F(M1 ∧M2) = F(M1) ∧ F(M2).

heading: A.6 GOAL-ORIENTED Q-LEARNING
text: Below we list the pseudocode for the modified Q-learning algorithm used in the four-rooms domain.
Algorithm 1: Goal-oriented Q-learning Input: Learning rate α, discount factor γ, exploration constant ε, lower-bound return N Initialise Q : S × S ×A → R arbitrarily G ← ∅ while Q is not converged do
Initialise state s while s is not terminal do
if G = ∅ then Select random action a else
a← arg maxb∈A ( max t∈G Q(s, t, b) ) with probability 1− ε
a random action with probability ε end Choose a from s according to policy derived from Q Take action a, observe r and s′ foreach g ∈ G do
if s′ is terminal then if s′ 6= g then
δ ← N else
δ ← r −Q(s, g, a) end
else δ ← r + γmaxbQ(s′, g, b)−Q(s, g, a) end Q(s, g, a)← Q(s, g, a) + αδ
end s← s′
end G ← G ∪ {s}
end return Q
Figure 5: A Q-learning algorithm for learning extended value functions. Note that the greedy action selection step is equivalent to generalised policy improvement (Barreto et al., 2017) over the set of extended value functions.
A.7 INVESTIGATING PRACTICAL CONSIDERATIONS
The theoretical results presented in this work rely on Assumptions 1 and 2, which restrict the tasks’ transition dynamics and reward functions in potentially problematic ways. Although this is necessary to prove that Boolean algebraic composition results in optimal value functions, in this section we investigate whether these can be practically ignored. In particular, we investigate two restrictions: the requirement that tasks share the same terminal states, and the impact of using dense rewards.

heading: A.7.1 FOUR ROOMS EXPERIMENTS
text: We use the same setup as the experiment outlined in Section 4, but modify it in two ways. We first investigate the difference between using sparse and dense rewards. Our sparse reward function is defined as
rsparse(s, a, s ′) = { 20 if s′ ∈ G −1 otherwise,
and we use a dense reward function similar to Peng et al. (2019):
rdense(s, a, s ′) =
1 |G| ∑ g∈G exp( |s′ − g|2 4 ) + rsparse(s, a, s ′)
Using this dense reward function, we again learn to solve the two base task MT (reaching the centre of the top two rooms) and ML (reaching the centre of the left two rooms). We then compose them to solve a variety of tasks, with the resulting value functions illustrated by Figure 6.
We also modify the domain so that tasks need not share the same terminating states (that is, if the agent enters a terminating state for a different task, the episode does not terminate and the agent can continue as if it were a normal state). This results in four versions of the experiment:
(i) sparse reward, same absorbing set (ii) sparse reward, different absorbing set
(iii) dense reward, same absorbing set (iv) dense reward, different absorbing set
We learn extended value functions for each of the above setups, and then compose them to solve each of the 24 tasks representable in the Boolean algebra. We measure each composed value functions by evaluating its policy in the sparse reward setting, averaging results over 100000 episodes. The results are given by Figure 7.
Our results indicate that extended value functions learned in the theoretically optimal manner (sparse reward, same absorbing set) are indeed optimal. However, for the majority of the tasks, relaxing the restrictions on terminal states and reward functions results in policies that are either identical or very close to optimal.

heading: A.7.2 FUNCTION APPROXIMATION EXPERIMENTS
text: In this section we investigate whether we can again loosen some of the restrictive assumptions when tackling high-dimensional environments. In particular, we run the same experiments as those presented in Section 5, but modify the domain so that (i) tasks need not share the same absorbing set, (ii) the pickup-up action is removed (the agent immediately collects an object when reaching it), and (iii) the position of every object is randomised at the start of each episode.
We first learn to solve three base tasks: collecting blue objects, collecting purple objects, and collecting squares , which can then be composed to solve new tasks immediately. We then demonstrate composition characterised by disjunction, conjunction and exclusive-or, with the resulting trajectories and value functions illustrated by Figure 8.
In summary, we have shown that our compositional approach offers strong empirical performance, even when the theoretical assumptions are violated. Finally, we expect that, in general, the errors due to these violations will be far outweighed by the errors due to non-linear function approximation.

heading: A.8 SELECTING BASE TASKS
text: The Four Rooms domain requires the agent to navigate to one of the centres of the rooms in the environment. Figure 9 illustrates the layout of the environment and the goals the agent must reach.
Since we know the goals upfront, we can select a minimal set of base tasks by assigning each goal a Boolean number, and then using the columns of the table to select the tasks. To illustrate, we assign Boolean numbers to the goals as follows:
As there are four goals, we can represent each uniquely with just two Boolean variables. Each column in Table 1 represents a base task, where the set of goals for each task are those goals assigned a value rU . We thus have two base tasks corresponding to x1 = {top-right,top-left} and x2 = {bottom-left,top-left}.

heading: A.9 DQN ARCHITECTURE AND HYPERPARAMETERS
text: In our experiments, we used a DQN with the following architecture:
1. Three convolutional layers: (a) Layer 1 has 6 input channels, 32 output channels, a kernel size of 8 and a stride of 4. (b) Layer 2 has 32 input channels, 64 output channels, a kernel size of 4 and a stride of 2. (c) Layer 3 has 64 input channels, 64 output channels, a kernel size of 3 and a stride of 1.
2. Two fully-connected linear layers: (a) Layer 1 has input size 3136 and output size 512 and uses a ReLU activation function. (b) Layer 2 has input size 512 and output size 4 with no activation function.
We used the ADAM optimiser with batch size 32 and a learning rate of 10−4. We trained every 4 timesteps and update the target Q-network every 1000 steps. Finally, we used -greedy exploration, annealing to 0.01 over 100000 timesteps.

Review summaries:
The paper proposes a method of combining value functions for a certain class of tasks, including shortest path problems, to solve composed tasks. By expressing tasks as a Boolean algebra, they can be combined using the negation, conjunction and disjunction operations. Analogous operations are available for the optimal value functions of the tasks, which allows the agent to have immediate access to the optimal policy of these composed tasks after solving the base tasks. The theoretical composition properties are confirmed empirically on the four rooms environment and with function approximation on a more complex domain. 

This paper introduces a framework for composing tasks by treating tasks as a Boolean algebra. The paper assumes an undiscounted MDP with a 0-1 reward and a fixed absorbing set G, and considers a family of tasks defined by different reward functions. Each task defers only by the value of the reward function at the absorbing set G. These restrictions are quite severe but basically describes goal-state reaching sparse reward tasks, which are quite general and valuable to study. The paper then defines a mapping onto a Boolean algebra for these tasks and shows how the mapping also allows re-using optimal Q functions for each task to solve a Boolean composition of these tasks. This is demonstrated on the tabular four-rooms environment and using deep Q learning for a 2D navigation task.