Title: A BOOLEAN TASK ALGEBRA FOR REINFORCEMENT LEARNING

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.

1. INTRODUCTION:

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.

2. PRELIMINARIES:

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) → ρ (s,a) from S × A to S, and (iv) r is the real-valued reward function bounded by [r MIN , r MAX ]. 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(s t , a t )],

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.

3. BOOLEAN ALGEBRAS FOR TASKS AND VALUE FUNCTIONS:

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 MDPs M 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 ∅ , r U } ⊂ R with r ∅ ≤ r U . For all non-terminal states, we denote the reward r s,a to emphasise that it is constant across tasks. Assumption 2. For all tasks in a set of tasks M 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 ∅ , r U } ⊂ R with r ∅ ≤ r U . For all non-terminal states, we denote the reward r s,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.

3.1. A BOOLEAN ALGEBRA FOR TASKS:

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. Let M be a set of tasks. Define M U , M ∅ ∈ M to be tasks with the respective reward functions

r M U : S × A → R (s, a) → r U , if s ∈ G r s,a , otherwise. r M∅ : S × A → R (s, a) → r ∅ , if s ∈ G r s,a , otherwise.

Then M forms a Boolean algebra with universal bounds M ∅ and M U when equipped with the following operators:

¬ : M → M M → (S, A, ρ, r ¬M ), where r ¬M : S × A → R (s, a) → r M U (s, a) + r M∅ (s, a) -r M (s, a) ∨ : M × M → M (M 1 , M 2 ) → (S, A, ρ, r M1∨M2 ), where r M1∨M2 : S × A → R (s, a) → max{r M1 (s, a), r M2 (s, a)} ∧ : M × M → M (M 1 , M 2 ) → (S, A, ρ, r M1∧M2 ), where r M1∧M2 : S × A → R (s, a) → min{r M1 (s, a), r M2 (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.

3.2. EXTENDED VALUE FUNCTIONS:

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

EQUATION

where N ≤ min{r MIN , (r MINr MAX )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

EQUATION

where

V π (s, g) = E π [ ∞ t=0 r(s t , g, a t )].

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. From left to right we plot the reward for entering a region of the state space for the individual tasks, the negation of M LEFT , and the union (disjunction) and intersection (conjunction) of tasks. For reference, we also plot the average reward function, which has been used in previous work to approximate the conjunction operator (Haarnoja et al., 2018; Hunt et al., 2019; Van Niekerk et al., 2019) . Note that by averaging reward, terminal states that are not in the intersection are erroneously given rewards.

Lemma 1. Let r M , rM , 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) r M (s, a) = max g∈G rM (s, g, a), and (ii)

Q * M (s, a) = max g∈G Q * M (s, g, a).

Proof.

(i): 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.

max g∈G rM (s, g, a) = max{N, r M (s, a)}, if s ∈ G max g∈G r M (s, a), otherwise. = r M (s, a) (N ≤ r MIN ≤ r M (s,

Lemma 2. Denote S -= S \ G as the non-terminal states of M. Let M 1 , M 2 ∈ M, and let each g in G define MDPs M 1,g and M 2,g with reward functions r M1,g := rM1 (s, g, a) and r M2,g := rM2 (s, g, a) for all (s, a) in S × A.

Then for all g in G and

s in S -, π * 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 max a∈A max g∈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 + rM (s , g, a ), where s ∈ G and a = arg max b∈A rM (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 r M (s t , π * g (s t ))

is the same up to (but not including) g.

3.3. A BOOLEAN ALGEBRA FOR VALUE FUNCTIONS:

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 ∅ , M U ∈ M. Then Q * forms a Boolean algebra when equipped with the following operators:

¬ : Q * → Q * Q * → ¬ Q * , where ¬ Q * : S × G × A → R (s, g, a) → Q * U (s, g, a) + Q * ∅ (s, g, a) -Q * (s, g, a) ∨ : Q * × Q * → Q * ( Q * 1 , Q * 2 ) → Q * 1 ∨ Q * 2 , where Q * 1 ∨ Q * 2 : S × G × A → R (s, g, a) → max{ Q * 1 (s, g, a), Q * 2 (s, g, a)} ∧ : Q * × Q * → Q * ( Q * 1 , Q * 2 ) → Q * 1 ∧ Q * 2 , where Q * 1 ∧ Q * 2 : S × G × A → R (s, g, a) → min{ Q * 1 (s, g, a), Q * 2 (s, g, a)}

Proof. See Appendix.

3.4. BETWEEN TASK AND VALUE FUNCTION ALGEBRAS:

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 from M to Q * such that F(M ) = Q * M for all M in M. Then F is a homomorphism. Proof. See Appendix.

4. ZERO-SHOT TRANSFER THROUGH COMPOSITION:

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.

4.1. LEARNING BASE TASKS:

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 M T , which requires that the agent visit either of the top two rooms, and M L , which requires visiting the two left rooms. We illustrate this selection procedure in the Appendix.

4.2. BOOLEAN COMPOSITION:

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 2 2 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 2 K -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 log 2 K + 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) . 

5. COMPOSITION WITH FUNCTION APPROXIMATION:

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.

6. RELATED WORK:

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 Figure 4 : By composing extended value functions from the base tasks (collecting blue objects, and collecting squares), we can act optimally in new tasks with no further learning. To generate the value functions, we place the agent at every location and compute the maximum output of the network over all goals and actions. We then interpolate between the points to smooth the graph. Any error in the visualisation is due to the use of non-linear function approximation.

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.

7. CONCLUSION:

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 RLsince 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.

(vi): Let r M U ∧M1 and r M1 be the reward functions for M U ∧ M 1 and M 1 respectively. Then for all (s, a) in S × A,

r M U ∧M1 (s, a) = min{r U , r M1 (s, a)}, if s ∈ G min{r s,a , r s,a }, otherwise. = r M1 (s, a), if s ∈ G r s,a , otherwise. (r M1 (s, a) ∈ {r ∅ , r U } for s ∈ G) = r M1 (s, a)

.

Thus M U ∧ M 1 = M 1 . Similarly M U ∨ M 1 = M U , M ∅ ∧ M 1 = M ∅ , and M ∅ ∨ M 1 = M 1 .

Hence M ∅ and M U are the universal bounds of M.

(vii): Let r M1∧¬M1 be the reward function for M 1 ∧ ¬M 1 . Then for all (s, a) in S × A,

r M1∧¬M1 (s, a) = min{r M1 (s, a), (r U + r ∅ ) -r M1 (s, a)}, if s ∈ G min{r s,a , (r s,a + r s,a ) -r s,a }, otherwise. =    r ∅ , if s ∈ G and r M1 (s, a) = r U r ∅ , if s ∈ G and r M1 (s, a) = r ∅ r s,a , otherwise. = r M∅ (s, a). Thus M 1 ∧ ¬M 1 = M ∅ , and similarly M 1 ∨ ¬M 1 = M U . A.3 PROOF FOR LEMMA 2

Lemma 2. Denote S -= S \ G as the non-terminal states of M. Let M 1 , M 2 ∈ M, and let each g in G define MDPs M 1,g and M 2,g with reward functions r M1,g := rM1 (s, g, a) and r M2,g := rM2 (s, g, a) for all (s, a) in S × A.

Then for all g in G and s in S -,

π * 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 = s =⇒ r M1,g (s , a) = N, if s ∈ G r s ,a , otherwise = r M2,g (s , a) =⇒ M 1,g = M 2,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 = 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 + r M1,g (g , π * g (g )) ≥ G πg , where G π * g T -1 = T -1 t=0 r M1,g (s t , π * g (s t

)) and T is the time at which g is reached.

=⇒ G π * g T -1 + N ≥ G πg , since g = g ∈ G =⇒ N ≥ G πg -G π * g T -1 =⇒ (r MIN -r MAX )D ≥ G πg -G π * g T -1 , by definition of N =⇒ G π * g T -1 -r MAX D ≥ G πg -r MIN D, since G πg ≥ r MIN D =⇒ G π * g T -1 -r MAX D ≥ 0 =⇒ G π * g T -1 ≥ r MAX D.

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 r MAX for every step of the longest possible optimal trajectory. Hence we must have g = g. Similarly, all optimal policies of M 2,g must reach g. Hence π * g (s) ∈ arg max a∈A Q * M2,g (s, a). Since M 1 and M 2 are arbitrary elements of M, the reverse implication holds too.

(vi): For all (s, g, a) in S × G × A, s, g, a) , Q * M1 (s, g, a)} = min{G * s:g,a + rM U (s , g, a ), G * s:g,a + rM1 (s , g, a )} (Corollary 1) = G * s:g,a + min{r M U (s , g, a ), rM1 (s , g, a )} = G * s:g,a + rM1 (s , g, a )

( Q * U ∧ Q * M1 )(s, g, a) = min{( Q * U (

(since rM1 (s , g, a ) ∈ {r ∅ , r U , 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 M U (s , g, a ) + rM∅ (s , g, a )) -rM1 (s , g, a )} = G * s:g,a + rM∅ (s , g, a ) = Q * ∅ (s, g, a). Similarly, Q * M1 ∨ ¬ Q * M1 = Q * U .

A.5 PROOF FOR THEOREM 3 

Theorem 3. Let F : M → Q * be any map from M to Q * such that F(M ) = Q * M for all M in M. Then F is a homomorphism. Proof. Let M 1 , M 2 ∈ M.

= Q * U (s, g, a) + Q * ∅ (s, g, a) -Q * M1 (s, g, a) = ¬ Q * M1 (s, g, a) =⇒ F(¬M 1 ) = ¬F(M 1 ) Q * M1∨M2 (s, g, a) = G * s:g,a + rM1∨M2 (s , g, a ) = G * s:g,a + max{r M1 (s , g, a ), rM2 (s , g, a )} = max{G * s:g,a + rM1 (s , g, a ), G * s:g,a + rM2 (s , g, a )} = max{ Q * M1 (s, g, a), Q * M2 (s, g, a)} = ( Q * M1 ∨ Q * M2 )(s, g, a) =⇒ F(M 1 ∨ M 2 ) = F(M 1 ) ∨ F(M 2 ). Similarly F(M 1 ∧ M 2 ) = F(M 1 ) ∧ F(M 2 ).

A.6 GOAL-ORIENTED Q-LEARNING 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 max b∈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 = g then δ ← N else δ ← r -Q(s, g, a) end else δ ← r + γ max Q(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.

A.7.1 FOUR ROOMS EXPERIMENTS:

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 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:

EQUATION

(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 2 4 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. 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.

Q * MT Q * ML Q * MT ¬Q * ML Q * ML ¬Q * MT Q * MT Q * ML Q * MT ¬Q * MT Q * ML ¬Q * ML Q * MT Q * ML Q * MT ¬Q * ML Q * ML ¬Q * MT Q * MT Q * ML ¬(Q * MT Q * ML) Q * MT Q * ML

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 . 

:

Since 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 ω.

We provide a description of these axioms in the Appendix.

The diameter is defined as D = max s =s ∈S minπ E [T (s |π, s)], where T is the number of timesteps required to first reach s from s under π.

The hyperparameters and network architecture are listed in the Appendix

Figures and Tables:

Figure 1: Consider two tasks, M LEFT and M DOWN , in which an agent must navigate to the left and bottom regions of an xy-plane respectively.From left to right we plot the reward for entering a region of the state space for the individual tasks, the negation of M LEFT , and the union (disjunction) and intersection (conjunction) of tasks. For reference, we also plot the average reward function, which has been used in previous work to approximate the conjunction operator(Haarnoja et al., 2018;Hunt et al., 2019;Van Niekerk et al., 2019). Note that by averaging reward, terminal states that are not in the intersection are erroneously given rewards.

a) by definition). (ii): Each g in G can be thought of as defining an MDP M g := (S, A, ρ, r Mg ) with reward function r Mg (s, a) := rM (s, g, a) and optimal Q-value function Q * Mg (s, a) = Q * M (s, g, a). Then using (i) we have r M (s, a) = max g∈G r Mg (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) = max g∈G Q * M (s, g, a).

Figure 2: An example of zero-shot Boolean algebraic composition using the learned extended value functions. Arrows represent the optimal action in a given state. (a-b) The learned optimal goal oriented value functions for the base tasks. (c) Zero-shot disjunctive composition. (d) Zero-shot conjunctive composition. (e) Combining operators to model exclusive-or composition. (f) Composition that produces logical nor. Note that the resulting optimal value function can attain a goal not explicitly represented by the base tasks.

number of samples required to learn optimal extended and regular value functions. Error bars represent standard deviations over 100 runs.

of tasks that can be solved as a function of the number of existing tasks solved. Results are plotted on a log-scale. number of samples required to solve tasks in a 40-goal Four Rooms domain. Error bars represent standard deviations over 100 runs.

Figure 3: Results in comparison to the disjunctive composition of Van Niekerk et al. (2019). (a) The number of samples required to learn the extended value function is greater than learning a standard value function. However, both scale linearly and differ only by a constant factor. (b) The extended value functions allow us to solve exponentially more tasks than the disjunctive approach without further learning. (c) In the modified task with 40 goals, we need to learn only 7 base tasks, as opposed to 40 for the disjunctive case.

Value function for conjunctive composition. (f) Value function for exclusiveor composition.

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 M U (s , g, a ) + rM∅ (s , g, a )) -rM1 (s , g, a ) = (G * s:g,a + rM U (s , g, a )) + (G * s:g,a + rM∅ (s , g, a )) -(G * s:g,a + rM1 (s , g, a ))

otherwise, and we use a dense reward function similar to Peng et al. (2019):r dense (s, a, s ) = 1 |G| g∈G exp( |s -g| 2 4 ) + r sparse (s, a, s )Using this dense reward function, we again learn to solve the two base task M T (reaching the centre of the top two rooms) and M L (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 Figure6.

Figure 6: An example of Boolean algebraic composition using the learned extended value functions with dense rewards. Arrows represent the optimal action in a given state. (a-b) The learned optimal goal oriented value functions for the base tasks with dense rewards. (c) Disjunctive composition. (d) Conjunctive composition. (e) Combining operators to model exclusive-or composition. (f) Composition that produces logical nor. We note that the resulting value functions are very similar to those produced in the sparse reward setting.

Figure 7: Box plots indicating returns for each of the 16 compositional tasks, and for each of the four variations of the domain. Results are collected over 100000 episodes with random start positions.

Trajectories for exclusiveor composition (collect blue or square objects, but not blue squares). (d) Value function for disjunctive composition. (e) Value function for conjunctive composition. (f) Value function for exclusiveor composition.

Figure8: Results for the video game environment with relaxed assumptions. We generate value functions to solve the disjunction of blue and purple tasks, and the conjunction and exclusive-or of blue and square tasks.

Peer review (iclr2020):
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. The paper is generally well-written with a clear theoretical contribution and convincing experiments. The problem of composing tasks is important and I think this paper would be a good addition to the literature. My only concerns are in regards to the assumptions made in this formulation. I would be wiling to increase my score if the authors address the following points: 1) Some further explanation on why extended value functions are necessary would be welcome at the beginning of section 3.2. Currently, it is only said that regular value functions are insufficient without any explanation. Also, additional motivation for the definition of extended value functions would be helpful to guide the reader. 2) Concerning assumption 1, it seems that the assumption that the reward functions only differ on the absorbing states is fairly limiting. For example, in a navigation task, if one goal location is A, then it must be an absorbing state under this formulation. So, if we have another goal location B, then we cannot use paths through A since it is set as absorbing, even though that A may be part of the shortest path to B. Would it be possible to modify this assumption to circumvent this problem? 3) In a similar vein, could the authors discuss possible limitations to this framework? For example, could this task/value composition be extended to arbitrary reward functions and continuing tasks or are there some fundamental limitations to this approach? If lifelong learning is a motivating setting for this work, it seems like dealing with non-episodic tasks and more complex rewards would be an important goal. 4) Fig. 3 b) does not seem to be particularly important as the result is clear enough in text. Perhaps the space could be used for something else. As an aside, the paper is well-polished and the lack of typos is appreciated.