A Boolean Task Algebra for Reinforcement Learning
Authors: Geraud Nangue Tasse
Steven James
Benjamin Rosman
Venue:  (2020)
Keywords: Reinforcement Learning
Transfer
Composition
Lifelong
Multi-task
Deep 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. 

Under review as a conference paper at ICLR 2020
A BOOLEAN TASK ALGEBRA FOR REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a framework for defining Boolean algebra over the space of tasks, This allows to formulate new tasks in terms of the negation, disjunction and conjunction of a set base tasks. We then show that by learning grie-oriented value functions and restricting the transition dynamics of the tasks, an agent solve these new tasks with no further learning. We prove that by composing these value functions in specific ways, for all tasks expressible under the Boolean algebra. We verify our approach in two inclins-including a high-dimensional video game environment requiring function approximation -whrii an agent first learns a set of base skills, and then composes them to solve super-exponential number of new tasks.
immediately recover the optimal policies
INTRODUCTION
Reinforcement learning (RL) has achieved recent success in a number of difficult, high-dimensional environments (Mnih al. 2015 Levine et al., 2016; Lillicrap al. 2016; Silver al., (017). However, these methods generally require millions of samples from the environment to learn op- timal 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 multitask lifelong setring, since learning solve complex tasks from scratch is typically infeasible.
One approach 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 new task. this work, we focus on concurrent composition, where existing base skills are combined to produce new skills (Todorov 2009 Saxe et al. [207]: HHarnoja et al.) 2018 Van Niekerk et al., 2019 Hunt al. [0199] Peng et al. 2019). This differs from other forms of composition, such as options (Sutton et al. 1999) and hierarchical RI. (Bacon et al. (017)) where actions and skills are chained in a temporal sequence.
In this work, define 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 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 Boolean expression can immediately be solved without further learning, resulting in zero-shot super-exponential explosion in the agent's abilities.
We illustrate approach in simple domain, where agent first learns reach number of rooms, after which can then optimally solve any task expressible in the Boolean algebra. We then demonstrate composition in nigh-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, p, r), where (i) S is the state space, (ii) A is the action space, (iii) p is Markov transition

---

Under review as a conference paper at ICLR 2020
kernel a) + P(s.a) from S x A to S, and (iv) is the real-valued reward function bounded by IMMIN TMAX]- In this work, we focus on stochastic shortest path problems (Bertsekas & Tsitsiklis 199T]. 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 to compute a Markov policy x from S to A that optimally solves a given task. A given policy π is characterised by a value function V (s) E, |Σr=o (st az)], specifying the expected return obtained under starting from state s The optimal policy x² is the policy that obtains the greatest expected return at each state: V" (s) - V>))
max= (*) for all s in S. A related quantity is the Q-value function, Q a), which defines the expected return obtained by executing from and thereafter following æ. Similarly, the optimal Q-value function is given by (* a) = max; Q" a) for all s in S and a in A. Finally, we denote a proper policy to be policy that is guaranteed to eventually reach the absorbing set G (James & Collins 2006
Van Nickerk et al.] 2019). We assume the value functions for improper policies those that never reach absorbing states are unbounded below.
BOOLEAN ALGEBRAS FOR TASKS AND VALUE FUNCTIONS
In this section, we develop the notion of Boolean task algebra, allowing us to perform logical operations operations--conuncciioo conjunction (A), disjunction (V) and negation (-)-over the space of tasks. We then show that, having solved series of base tasks, an agent can use its knowledge to solve tasks ex- pressible 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 set of tasks M, (i) the tasks share the same state space, action spuce and transition dynamics, (ii) the transition dynamics are deterministic, (ii) 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 x A, we have that r(g, a) E {Tg ru) C R with Tz S Tu- For all non-terminal states, we denote the reward Tsa to emphasise that it is constant across tasks.
Assumption 2. For all tasks in a set of tasks M which adhere to Assumption I the set of possible terminal rewards consists of only two values. That is, for all (g, a) in G x A, we have that r(g, a) E (re, ru C. I with To S Tu. For all non-terminal states, we denote the reward aa to emphasise that it is constant across tasks.
Assumption D is similar to that of Todorov (2007) and identical to Van Nickerk 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 7, V, A that satisfy the Boolean axioms of (i) idempotence, (ii) commutativity, (iii) associativity, (iv) absorption, (v) distributivity, (vi) identity, and (vii) complements Given the above definitions and the restrictions placed on the set of tasks consider, can now define a Boolean algebra over set of tasks.
Theorem 1. Let M be a set of tasks. Define Ma E M to be tasks with the respective reward functions
MM S A- R
TM S A
as + nus Tre otherwise.
ifsE
(s, + Teo (reas otherwise.
Ef
'iinee we consider undiscounted MDPs, we can ensure the value function is bounded hy augmenting the state space with a virtual state w such that (() (w) = 1 for all (s, a) in G x A, and r = O after reaching w. We provide description of these axioms in the Appendix.
2

---

Under review as a conference paper at ICLR 2020
Then M forms Boolean algebra with universal bounds Mz and Mu when equipped with the following operators:
M - M
M + (S,A, M)) where r M S x A - IR
(s,a) + (s, (rMols (s,
V: M
(2) + p. where TMVM
8 A + R (8,a) + max (rM (8, (as
M M (M1, - AS P.MMMM))) where AMA 8 x A +
(s, + min (M,
Proof. See Appendix.
Theorem I allows us to compose existing tasks together to create new tasks principled way. Figure Ilsttrtes the semantics for each of the Boolean operators in 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 define goal-oriented versions of the reward and value function, given by the following two definitions:
Definition 1. The extended reward function F : S x G A
IR is given by the mapping
NN
ifg
(s, + (r(s,a) otherwise,
where S min (FMIN D), and D is the diameter of the MDP (Jaksch et al. 2010
To understand why standard value functions are insufficient, consider two tasks that have multiple different goals, but at least common goal. Clearly, there meaningful conjunction between them- them-namely, achieving the common goal. Now consider an agent that learns standard value func- tions for both tasks, and which 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, can simply set N to be the lowest finite value representable by the data type used for rewards. Definition 2. The exlended Q-value function Q : G x A +
R given by the mapping
(8,g.a) a() + [ v= (s..))(s.))
(2)
where (* = E. E F(t.. g, az)) 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 (Kacibling 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.
"The diameter is defined as D max. min, (TT(s'(T,))) s)]; where 7' is the number of timesteps required to first reach s' from under n.
3

---

Then for all g in G and S Under review as a conference paper at ICLR 2020
(a) Maam
(b) TMMowN
(c) .unT .LIF
(d) Disjunction
(c) Conjunction
(f) Average
Figure 1: Consider two tasks, MLEFT and MDOWN, in which an agent must navigate to the left and
bottom regions of zy-plane respectively. From left right plot the reward for entering region of the state space for the individual tasks, the negation of MLEFT, and the union (disjunction) and intersection (conjunction) of tasks. For reference, which has been used in previous work to approximate the conjunction operator (Haarnoja et al., 2018 Hunt al. 2019: Van Nickerk et al. 2019). Note that by averaging reward, terminal states that are not in the intersection are erroneously given rewards.
also plot the average reward function,
Lemma 1. Let TM, M VMa- Qis be the reward function, extended reward function, optimal Q- value function, and optimal extended Q-value function for task M in M. Then for all (s,a) in x A. we have (i) TM (s, a) max FM (8, J, a), and (ii) Q (8, a) max (8, gEg
gEg
Proof.
(i):
if otherwise.
max FM (8, WE9
max (8,a), a), gEG
(8,
(N S UMIN S TM (8, a) by definition).
(ii): Each g in G can be thought of as defining MDP Mg (S,AA,,, with reward function TM,, (8, a) == Far(s, (s. g, and optimal Q-value function Qú, (s, a) (s, a). Then using (i) we have (M, a) max TM, (8, and from Van Niekerk et (2019) Corollary 1), we
9Eg
have that (s, max Qú, (s, a) max (ir gE9
9E9
In the same way, can also recover the optimal policy from these extended value functions by first applying Lemma] [ and acting greedily with respect to the resulting value function.
Lemma 2. Denote S S \ as the non-terminal states of M. Let M1, M2 e M, and let each G define MDPs Mi.g and M2.3 with reward functionn
MM, FM, (8, g, a) and M2.9 (8, 9, a) for all (s,a) in S A.
(s) arg argmax QM,, (s, iff (5) arg max Uh,, (s)
aed
aEA
Proof. See Appendix.
Combining Lemmas and can extract the greedy action from the extended value func-
tion by first maximising over goals, and then selecting the maximising action: π (s) arg max,e-A maxges (s, g, a). If we consider the extended value function be of standard value functions (one for each goal), then this 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 the sum of rewards received by the agent until first encountering terminal state.
4

---

Under review as a conference paper at ICLR 2020
Corollary 1. Denote Gegga the sum of rewards starting from and taking action up until, but not including, 9. Then let M M and Qis be the extended Q-value function. Then for all E S, E, a E A. there exists Gagga E R such that
QM a) = Gegga + FMs(s' ,9,0,99000 d'), where s' E G and a' = arg max Fa .s'.g.b).
DEA
Proof. This follows directly from Lemma 2 Since all tasks M E M share the same optimal policy
Tg up to (but not including) the goal state E G, their return G = Ei= rar (s))) 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 set of tasks, we can also do so for 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 Qo.Qu Qu E Q" to be the optimal Q-functions for the tasks Mu E M. Then Q forms Boolean algebra when equipped with the following operators:
7: Q- + Q-
Q" + QQ²,
where -Q" SxxxA= R
(8, + (Qī((, + -
V: x- -" (Q1 + Qi v Q2, where Qi V Q7 Sxgx
(s,g,a) + (Q)
A: x' O
(01.0) 0i 02 where Q7 A Q2: S ExGxA-1
(s,g,a) ())
Proof. See Appendix.
3.4 BETWEEN TASK AND VALUE FUNCTION ALGEBRAS
Having established Boolean algebra over tasks and extended value function, 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) = O's for all M in
M. Then F is 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 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 wall leaves the agent in the same location. The transition dynamics are deterministic, and rewards -0.1 for all non-terminal states, and 1 at the goal.

---

Under review as a conference paper at ICLR 2020
4.1 LEARNING BASE TASKS
1989 to learn extended Q-value functions de- scribed previously. Our algorithm differs in number of ways from standard Q-learning: keep track of the set of terminating states seen so far, and at each timestep we update the extended Q-value function with respect both the current state and action, well 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 different task, receives reward N. The full pseudocode is listed in the Appendix.
We use a modified version of Q-learning (Watkins
If we know the set of goals (and hence potential base tasks) upfront, then it is easy to select 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 table, and then use the columns of the table as base tasks. The goals for each base task are then those goals with value according to the table. this domain, the two base tasks select are Mr. which requires that the agent visit either of the top two rooms, and Mr. 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 base tasks, now leverage The- orems [ to solve new tasks with no further learning. Figure Salurrrillsttttee this composition, where an agent able to immediately solve complex tasks such exclusive-or. We illustrate few com- posite tasks here, but note that in general. if we have K base tasks, then Boolean algebra allows for 2 new tasks to be constructed. Thus having trained only two tasks, our agent has enough information to solve a total 16 composite tasks.
(a) Mr.
(b) Mr
(c) M. V MT
(d) Mr. A Mr
(e) M. Mr
(1 Mr V Mr
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. b) The learned optimal goal oriented value functions for the base tasks. ( Zero-shot disjunctive composition. (d) Zero-shot
conjunctive composition. (c) Combining operators to model exclusive-or composition. i Compo-
sition that produces logical nor. Note that the resulting optimal value function attain goal not explicitly represented by the base 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 Van Niekerk et al. (2019), who used regular value functions to demonstrate optimal disjunetive composition. We note that while the upfront learning cost is therefore lower, the number of tasks expressible using only disjunction is 2* -1, which is significantly less than the full Boolean algebra. We also test using 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
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, need to leam only llog2 K| + 1 base tasks, 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 al. 2019).

---

Under review as a conference paper at ICLR 2020
1014
XII
1015
Rasinos tark algetra Daaaniionn only
Cinsaatee Unestess cennirg"
3.23
Eno ean tack zigekr
Die unetion only
trandee
107
3300
100
9:75
3.30
9:35
13
12
14
16
Number
(a) Cumulative number of sam- ples required to learn optimal ex- tended and regular value func- tions. Error bars represent stan- dard deviations over 100 runs.
(b) Number tasks that can be solved as a function of the num- ber of existing tasks solved. Re- sults are plotted on log-scale.
(c) Cumulative number of sam- ples required to solve tasks in a 40-goal Four Rooms domain. Er- ror bars represent standard devia- tions over 100 runs.
Figure 3: Results in comparison to the disjunctive composition of Van Nickerk et al. (019). (a) The number samples required learn the extended value function greater than learning a standard value function. However, both scale linearly and differ only by constant factor. (b) The extended value functions allow us to solve exponentially more tasks than the disjunctive approach without further learning. { In the modified task with 40 goals, we need to learn only 7 base tasks, as opposed to 40 for the disjunctive case.
5 COMPOSITION WITH FUNCTION APPROXIMATION
Finally, we demonstrate that our compositional approach can also be used to tackle high-dimensionaal domains where function approximation is required. We use the same video game environment as Van Nickerk al. (2019), where an agent must navigate 2D world and collect objects of different shapes and colours. The state space is an 84 x 84 RGB image, and the agent able to move in any of the four cardinal directions. The agent also possesses pick-up 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 total of six unique objects. The position of the agent is randomised at the start of each episode.
We modify deep Q-learning (Mnih al. 2015) to learn extended action-value functions D 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 encountered, is added to the collection of goals seen so far, and when learning updates occur, these goals are sampled randomly from 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 disjunction, (ii) conjunction and (iii) exclusive- or. 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 illustratee sample trajectories, as well as the subsequent composed value functions, for the respective tasks.
6 RELATED WORK
The ability compose value functions 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 stan- dard 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 func- tions, 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 conjunetive case. More recently, Peng et al. (2099) introduce a few-shot learning approach to compose policies
*The hyperparameters and network architecture listed in the Appendix

---

Under review as a conference paper at ICLR 2020
(a) Trajectories for disjunctive composition.
(b) Trajectories for conjunctive composition.
(c) Trajectories for exclusive-or composition.
1.5
1.5
1.0
1.0
1.0
0,5
0.5
0.5
(d) Value function for disjunctive composition.
(c) Value function for conjunc-
Value function for exclusive- or composition.
tive composition.
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, 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 weighted composition of existing base skills to solve 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 compose tasks using the standard Boolean algebra operators, These com- posite tasks can be immediately solved by first learning goal-oriented value functions, and then composing them in similar manner. Finally, 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 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, well as developing better algorithms for solving tasks with sparse rewards. For example, it is likely that approaches such as hindsight experience replay (Andrychowicz al. 2017) could reduce the num- ber of samples required to learn extended value functions, while Mirowski et al. (017)) 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 step towards both interpretable RI.- 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 sample-efficient manner.
note that there is much room for improvement
for the first task,
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
M. Andrychowicz, F. Wolski, A. Ray. J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, P. Abbeel, and W. Zaremba. Hindsight experience replay. Advances Neural Information Processing Systems, pp. 5048-5058, 2017.
Bacon, Harb, and D. Precup. The option-critic architecture. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
A. Barreto, W. Dabney, R. Munos, J. Hunt, T. Schaul, H. Hasselt, and D. Silver. Successor features for transfer in reinforcement learning. In Advances in neural information processing systems, pp. 4055-4065, 2017.
D.P. Bertsekas and J.N. Tsitsiklis. An analysis of stochastic shortest path problems. Mathematics of Operations Research, 16(3):580-595, 1991.
R. Fox, A. Pakman, and N. Tishby. Taming the noise in reinforcement learning via soft updates. In 32nd Conference on Uncertainty in Artificial Intelligence, 2016.
Haarnoja, Pong, A. Zhou, Dalal, P. Abbeel, and S. Levine. Composable deep reinforcement learning for robotic manipulation. arXiv preprint arXiv:1803.06773, 2018.
Hunt, A. Barreto, Lillicrap, and N. Heess. Composing entropic policies using divergence correction. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2911-2920. PMIR, 09-15 Jun 2019.
T. Jaksch, R. Ortner, and P. Auer. Ncar-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1533-666 2010.
H.W. James and E.J. Collins. An analysis of transient Markov decision processes. Journal of applied probability, 43(3):603-62) 2006.
Leslie Pack Kaelbling. Learning to achieve goals. In International Joint Conferences on Artificial Intelligence, pp. 1094-1099, 1993.
Levine, C. Finn, T. Darrell, and P. Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-1377 2016.
T.. Lillicrap, J. Hunt, A. Pritzel, Heess, Erez, Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representa- tions, 2016.
P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukeuoglu, et al. Learning to navigate in complex environments. International Confer- ence on Learning Representations, 2017.
V. Mnih, K. Kavukcuoglu, D. Silver, Rusu, Veness, M. Bellemare, A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
X. Peng, M. Chang, G. Zhang, P. Abbeel, and S. Levine. MCP: Learning composable hierarchical control with multiplicative compositional policies. arXiv preprint ar05v: 190.00000.00008. 2019.
A.M. Saxe, A.C. Earle, and B.S. Rosman. Hierarchy through composition with multitask LMDPs. Proceedings of the 34th International Conference on Machine Learning, 70:3017-3026, 2017.
T. Schaul, D. Horgan, K. Gregor, and D. Silver. Universal value function approximators. In Pro- ceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1312-1320, Lille, France, 07-09 Jul 2015. PMLR.
D. Silver, J. Schrittwieser, K. Simonyan, Antonoglou, A. Huang, A. Guez, T. Hubert. L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676); 354, 2017.

---

Under review as a conference paper at ICLR 2020
R. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):111-1111 1999.
E. Todorov, Linearly-solvable Markov decision problems. In Advances in Neural Information Pro- cessing Systems, pp. 1369-1376, 2007.
E. Todorov. Compositionalliy of optimal control laws. In Advances Neural Information Process- ing Systems, pp. 1856-1864, 2009.
B. Van Nickerk, S. James. A. Earle, and B. Rosman. Composing value functions in reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97
of Proceedings of Machine Learning Research, pp. 6401-6409. PMLR, 09-15 15 Jun 2019.
C. Watkins, Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 BOOLEAN ALGEBRA DEFINITION
Definition 3. Boolean algebra a set B equipped with the binary operators V (disjunction) and (conjunction), and the unary operator (negation), which satisfies the following Boolean algebra axioms for a, b, B:
(i) Idempotence: a A = a aaaa =====a a
(ii) Commutativity: a b = b A a av
(iii) Associativity; A (b c) (a A a a (aV)
(iv) Absorption: A (a b) Va (a) =a.
(V) Distributivity: a (b V c) (a (a A c) and (b^c) = (
(vi) Identity: there exists 0, in such that
Oλa
0 a
AAa a
1 1
(vii) Complements: for every a in B, there exists an element a' in B such that a A a' 0 and
V.Vo a'
A.2 PROOF FOR THEOREM 1
Theorem 1. Let M be set of tasks. Define Ma M be tasks with the respective reward functions
TMu S R
TM S A R
(s, + ruu Ef&
(s, + fra, ifsE9 (1 otherwise.
(s otherwise.
Then M forms a Boolean algebra with universal bounds Mæ and Mu when equipped with the following operators:
M + MM
M + (S,
where r-M S x A + (s, + (rMu (8, + (m, (s)
V: M
(2) + P.T...M))....... where TM, S x A + + R (s,a) max (s,
N: M
(M, + (S. A, P.MM)))) where TMLAM
S A (s, + min(rM, (s, a), TM, (s, a)}
Proof. Let M,. M2 E M. We show that -, V.A 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.
11

---

Under review as a conference paper at ICLR 2020
(vi): Let MM and MM, be the reward functions for Mu M1 and Mi respectively. Then for all (s, a) in S A,
minfrr, rM, (s, a)), min rs,ah
if Eg otherwise.
MMuAM, (8,a)
(ras (s, e
(r,) E (re, for 9)
otherwise.
rM, (8)
Thus Mu A M1 = M1. Similarly V = Mu, Ma A = Me, M1 Hence Ma and Mu the universal bounds of M.
VM =
(vii): Let TMA-M, be the reward function for M1 A -M, Then for all (s,a) in S x A.
minnrra (8, a), (nu + rz) - TM (8, if [minfre.os (Taja Ta,a) rsaa)
TM ()
otherwise.
r
if E 9 and TMI (s, = ru
ræ
if E G and TM, (s, a) =
Pe,01
otherwise.
-Mo as,
Thus M1 A -M1 MM, and similarly Mi M1 Mu-
A.3 PROOF FOR LEMMA 2
Lemma 2. Denote S ' as the non-terminal states of M. Let Mi, M2 E M, and each in G define MDPs M1.g and M2.g with reward functions
FM, (8, 9, a) and M (F,,(8, a) for all (s,a) in S A. MM
Then for all in G and in S
(s) arg QM, (s, (s)) arg max Uis,, (s,
acA
aEA
Proof. Let g E 9,8 - and let ny be defined by
(s') E arg max (s, for all s' S.
aeA
g is unreachable from s, then are done since for all () in S A have
# = TM (s',a) {NN,
if EG otherwise
= TM2 (s', a)
M1 M2.9.
If g is reachable from 8, then show that following oi must reach g. Since T is proper, it must reach terminal state o' G. Assume o' # 9. Let ny be policy that produces the shortest trajectory
12

---

Under review as a conference paper at ICLR 2020
to g. Let & and 6 be the returns for the respective policies. Then,
G G
= G + T. (1', (g')))) 2 =
where G
a (st, Ty (st)) and T is the time at which g' is reached.
GT-1 N GT since g + eg
2 G G
(IMIN mMAX) 2 G - G7-11 by definition of N
GT-1 TMAXD G TMIND, since x 2 "MMN D
G TMAX 20
G 2 M. D.
But this is 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 strietly less that receiving rMAX for every step of the longest possible optimal trajectory. Hence we must have g' = 9. Similarly, all optimal policies of M2.g must reach g. Hence T5(s) arg max Viz (s, Since Mi and M2 aeA
arbitrary elements of M, the reverse implication holds too.
A.4 PROOF FOR THEOREM 2
Theorem 2. Let Q" be the set of optimal extended Q-value functions for tasks in M. Define Qo Qu E Q" to be the optimal Q-functions for the tasks Mu E M. Then Q forms Boolean algebra when equipped with the following operators:
-" Q' Q", where Q 5 A- R
(8, + -
V: x' Q+
(i) Qi v Q2 where Q1 Q2 S SxgxA-x
(8,g,a) + max
-' ( Q3) Qi Q2, where Qi Q5 S x 9 x R
(8,g.a) + min,Qi(s,g,,) (s,,))
Proof. Let QM, Dis, Ô- be the optimal Q-value functions for tasks M1, M2 M with reward functions TM, and TMg- We show that -, V, A satisfy the Boolean properties (i) - (vii).
(i)-(v): These follow directly from the properties of the min and max functions.
13

---

Under review as a conference paper at ICLR 2020
(vi): For all (s) in S x 9 x A,
(Qu A Qae, (s, = min 9, a). (s,
min S:g,a + Mu (5', g,)'), G + + (s',g.a)))
(Corollary !
Gaggaa + m "', FM (6,,0''')
Gasy,a" + FM, (5')
(since FM, (5' gs')),a') E (r),
Qi,, (8.
Similarly, Qú V QM, Qi Q's A Qis, Q2. and O2 v Qi,, = Uu6.
(vii): For all (s,g. a. in S x G x A.
(Oir A -- a. = min min(QM (s, a), (Q - -gll6.)))) - (s,gaa)
Gagg,a + min f (8', a,)'), (s a.)a + Pm g
Fm, ,.)))
Gagga + EMa (8' ,,,a')
Similarly, lis, V --M. Qi
A.5 PROOF FOR THEOREM 3
Theorem 3. Let : M - e- be any map from M to ¹" such that F(M) = Qis for all M in
M. Then F is homomorphism.
Proof. Let M1, M2 E .. Then for all (8,9,a) x A.
Q M,,, (s, (s,g.a) a) Gagg.a + F-M. (s' a') (from Corollary
1
Gsigaa" (FMu (s', a') + i (5', a')) - Far, (6' 9,,')"")
[[Grig + + (' (G + + a'))] (G FM, (d')),'))
[Qū((,9, (s,g,,))) Qis, (8,
-iM (5,
F(-M) F(M))
@ivMms (8) (s. = Gogg + ($..
Gog. + max (5',g,'),, a' (s' (5.
max + + (s', a'), Gr.g. + (ss
max (8,g, Qia, {,
-QQa,, V (i,,))s,
= F(M M2) F(MM) V F(M2). Similarly F(M, A M2) -((M) AF(M).
14

---

Under review as a conference paper at ICLR 2020
A.6 GOAL-ORIENTED O-EARNNNGG
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 a, discount factor ", exploration constant e, lower-bound return N Initialise Q x x R. arbitrarily
G <- Ø
while Q is not converged do
Initialise state
while 8 is not terminal do if g Ø then
Select random action a else
arg max max Q(s,t,b) DEA
with probability 1
+-
random action
with probability
end
Choose from 8 according to policy derived from Q Take action a, observe and s
foreach g E G do
if s is terminal then if 8 + 9 then + N
else
8 ((s.g.a)
end
else
+ y maxs Q(s', gg ())
end
Q(s.g,a) Q( ad
end +- s end G - (u(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.
15

---

Under review as a conference paper at ICLR 2020
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 but modify it in two ways. We first investigate the difference between using sparse and dense rewards. Our sparse reward function is defined as
20 i Eg
T sspprse (s, a,
-1
otherwise,
and we dense reward function similar to Peng al.
2019):
densse (8, a, 8')
Σ gEG
exp
Is'
g + r rsparso 0, 8')
4
Using this dense reward function, we again learn to solve the two base task My (reaching the centre of the top two rooms) and Mr (reaching the centre of the left two rooms). We then compose them to solve a variety tasks, with the resulting value functions illustrated by Figure 6
(a) ML
(b) Mr
(c) M. V Mr
(d) ML A Mr
(c) ML Mr
(f) ML V Mr
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. The learned optimal goal oriented value functions for the base tasks with dense rewards. c Disjunctive composition. <cp Conjunctive composition. (c) Combining operators model exclusive-or composition. (f) Compo- sition that produces logical nor. We note that the resulting value functions are very similar to those produced in the sparse reward setting.
We also modify the domain so that tasks need not share the same terminating states (that is, agent enters terminating state for different task, the episode does not terminate and the agent can continue as if 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, di ffferentt absorbing set
We learn extended value functions for each of the above setups, and then compose them to solve each of the 2 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 given by Figure 7
Our results indicate that extended value functions learned in the theoretically optimal manner (sparse reward, same absorbing set) indeed optimal. However, for the majority of the tasks, relaxing the restrictions on terminal states and reward functions results policies that either identical very close to optimal.
16

---

Under review as a conference paper at ICLR 2020
Sparse rewards, same absorbing set
Dense rewards, same absorbing set different Dense rewards, abworbing
400
4
4 +
00.0%
-10L10L)
Figure 7: Box plots indicating returns for each the 16 compositional tasks, and for each the four variations of the domain. Results are collected over 100000 episodes with random start positions.
A.7.2 FUNCTION APPROXIMATION EXPERIMENTS
In this section we investigate whether we can again loosen some the restrictive assumptions when tackling high-dimensional environments. In particular,
the same experiments 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 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 col- lecting 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 trajecto- ries and value functions illustrated by Figure
(a) Trajectories for disjunctive composition (collect blue pur- ple objects).
(b) Trajectories for conjunc- tive composition (collect blue squares).
(c) Trajectories for exclusive- composition (collect blue square objects, but not blue squares).
2.0
2.0
1.5
1.5
1.5
1.0
1.0
0.5
0.5
0.5
(d) Value function for disjunctive composition.
(c) Value function for conjunc-
(f) Value function for exclusive- or composition.
tive composition.
Figure 8: 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.
17

---

Under review as a conference paper at ICLR 2020
In summary, have shown that 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.
A.8 SELECTING BASE TASKS
The Four Rooms domain requires the agent to navigate to one of the centres of the rooms in the environment. Figure Siguregiilusterr Iillustrates the layout of the environment and the goals the agent must reach.
Figure 9: The layout of the Four Rooms domain. The circles indicate goals the agent must reach. We will refer to the goals as top-left, top- right,
left, and bottom-B ciin-rigght right.
Since we know the goals upfront, we can select minimal of base tasks by assigning each goal 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:
F1
T2
Goals
Fø
Tø
bottom-right
Tø
Tu
bottom-left
ru
To
top-right
Tu
top-left
Table I: Assigning labels to the individual goals. The two Boolean variables, 21 and æ2, represent the goals for the base tasks the agent will train
As there are four goals, we can represent each uniquely with just two Boolean variables. Each column in Table[[re base task, where the set goals for each task are those goals assigned a value Tuz We thus have two base tasks corresponding to = stop-rrght,, top- and D2 = {portom-left, top-left).
A.9 DQN ARCHITECTURE AND HYPERPARAMETERS
In our experiments, used DQN with the following architecture:
1. Three convolutional layers:
(a) Layer has 6 input channels, 32 output channels, kernel size of 8 and stride of 4.
(b) Layer has 32 input channels, 64 output channels, a kernel size 4 and stride of 2.
(c) Layer has 64 input channels, 64 output channels, a kernel size and a stride of
2. Two fully-comnected linear layers:
(a) Layer has input size 3136 and output size 512 and uses ReLU activation function.
(b) Layer has input size 512 and output size 4 with no activation function.
We used the ADAM optimiser with batch size and a learning rate of 10-4, We trained every timesteps and update the target Q-network every 1000 steps. Finally, we used c-greedy exploration, annealing to 0.01 over 100000 timesteps.
18


Reviews:
[{"review_id": "rklZsDLptr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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.\nI would be wiling to increase my score if the authors address the following points:\n1) 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.\n\n2) 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? \n\n3) 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. \n\n4) 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. \n\nAs an aside, the paper is well-polished and the lack of typos is appreciated.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gpyr26tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe writing is relatively clear and the experiments support the claim in the paper that the framework allows learning compositions of skills. Both experiments show that after learning a set of base tasks, the method can solve a task in a zero-shot manner by composing Q functions according to the specified task. This capability seems very useful wherever it can be applied. But I worry that since the setting is so constrained, it is not likely to be widely applicable. The method in the paper likely does not apply to non-sparse, non-goal reaching settings, and prior methods have explored compositionality in that space anyways.\n\nThe coverage of prior work seems complete. One suggestion is to discuss recent goal relabeling work such as Hindsight Experience Replay (Andrychowicz 2017). Kaelbling 1993 is mentioned already, but this line of work has recently shown significant progress in learning to achieve multiple goals at the same time from a different perspective (and also considers sparse rewards).\n\nHowever, my main concern with this paper is that it is not clear the language of Boolean algebra leads to significant insights in solving these compositional problems. Take Figure 1, which shows the disjunction and conjunction of tasks. While it is true the average does not lead to the same optimal policy as the conjunction, people use it because learning from the completely sparse reward is often prohibitively difficult. This kind of reasoning is straightforward in the restricted case of MDPs considered in the paper and people can design their reward function directly without considering boolean algebra. The result and proofs about recovering optimal Q functions without extra further training are interesting, but again, seem straightforward in the restricted family of MDPs considered without looking at Boolean algebra. Therefore, I am currently considering the paper borderline.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1e4FUxTFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new framework for defining Boolean algebra over the space of tasks in goal conditioned reinforcement learning and thereby achieving composition of tasks, defined by boolean operators, in zero-shot. The paper proves that with some assumptions made about a family of MDP’s, one can build Boolean algebra over the optimal Q-functions of the individual MDP and these Q-functions are equipped with all the mathematical operations that come with the Boolean algebra (e.g negation, conjunction). The paper verify their theoretical results by experiments in both the 4-room domain with standard Q-learning and in a simple video game domain with high-dimensional observation space and DQN. The proofs of all the theoretical results seem sound and the experiments support the theory. I enjoyed reading this paper as the paper is generally well written and the idea is quite neat.\n\nThat being said, I have a few concerns and questions about the paper that I would like the authors to respond to so I am leaning towards rejecting this paper at the moment. However, I will raise my score if the revision addresses my concerns or provide additional empirical evidence. My concerns are the following:\n\n    1. My biggest concern is whether boolean algebra is the right abstraction/primitive for task level composition. Thus far, the most important application of boolean algebra has been in designing logic circuits where the individual components are quite simple. In the proposed framework, it seems that all of base tasks are required to be a well defined task which are already quite complex, so the utilities of composing them seems limited. For example, in the video game domain the author proposed, a very reasonable base task would be “collect white objects” -- this task when composed with the task “collect blue objects” is meaningless. This seems to be true for a large number of the MDP’s in the super-exponential composition. Furthermore, [1] also considers task level composition with sparse reward but I think these compositions cannot be expressed by boolean algebra. One of the most important appeal of RL is its generality so It would be great if the author can discuss the limitations of the proposed framework and provide an complex/real-world scenarios where composing these already complex base tasks are useful. Just writing would suffice as I understand setting up new environments can be difficult in short notice (Of course, actual experiments would be even better).\n\n    2. Does the maze not change in the environment setup? (It would be nice if source code is provided) If that is the case I would like to see additional experiments on different mazes (i.e. different placement of walls and objects). In my opinion, if there is only a single maze, then the only thing that changes is the location of the agent which makes the task pretty easy and do not show the full benefit of function approximators. I think it’d strengthen the results if the framework generalizes to multiple and possibly unseen mazes.\n\n    3. In the current formulation, a policy is discouraged to visit goals that are not in its current goal sets (receives lowest reward). While this could be just a proof artifact, it can have some performance implications. For example, in the 4 room domain, if I place a goal in the left corridor, then the agent in the bottom left room will need to take a longer route to reach top left (bottom left -> bottom right -> top right -> top left) instead of the shorter route (bottom left -> top left). From this perspective, it seems some non-trivial efforts need to be put into designing these \"basis\" tasks. I am curious about the discussion on this as well.\n\n    4. Haarnoja et al. 2018 and other works on composing Q values can be applied to high-dimensional continuous control using actor-critic style algorithms and relies on the maximum entropy principle. Can the method proposed in this paper be used with actor-critic style? Is the max-entropy principle applicable here as well? Discussion would be great and experiments would be even better.\n\nOut of all my concerns, 1 matters the most and I am willing to raise my score to weakly accept if it’s properly addressed. If, in addition, the authors could adequately address 2-4 I will raise my score to accept.\n\n=======================================================================\nMinor comments that did not affect my decision:\n    - In definition 1, it would be nice to define r_min and r_max and g \\ne s \\in \\mathcal{G} is also somewhat confusing.\n    - In definition 2, \\pi_g is never defined\n\nReference:\n[1] Language as an Abstraction for Hierarchical Deep Reinforcement Learning, Jiang et al. 2019\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the situation where a set of reinforcement learning tasks are related by means of a Boolean algebra.  The tasks considered are restricted to stochastic shortest path problems. The paper shows that learning goal-oriented value functions for subtasks enables the agent to solve new tasks (specified with boolean operations on the goal sets) in a zero-shot fashion.  Furthermore, the Boolean operations on tasks are transformed to simple arithmetic operations on the optimal action-value functions, enabling the zero short transfer to a new task to be computationally efficient. This approach to zero-shot transfer is tested in the four room domain without function approximation and a small video game with function approximation.

The reviewers found several strengths and weaknesses in the paper.  The paper was clearly written.  The experiments support the claim that the method supports zero-shot composition of goal-specified tasks.  The weaknesses lie in the restrictive assumptions.  These assumptions require deterministic transition dynamics, reward functions that only differ on the terminal absorbing states, and having only two different terminal reward values possible across all tasks.  These assumptions greatly restrict the applicability of the proposed method.  The author response and reviewer comments indicated that some aspects these restrictions can be softened in practice, but the form of composition described in this paper is restrictive.  The task restrictions also seem to limit the method's utility on general reinforcement learning problems.

The paper falls short of being ready for publication at ICLR.  Further justification of the restrictive assumptions is required to convince the readers that the forms of composition considered in this paper are adequately general. 
Decision: Reject