Generalisation in Lifelong Reinforcement Learning through Logical Composition 
Authors: Geraud Nangue Tasse
Steven James
Benjamin Rosman
Venue: ICLR 2022 Poster (2022)
Keywords: Reinforcement Learning
Lifelong learning
Multi task learning
Transfer learning
Logical composition
Deep Reinforcement Learning

Abstract: We leverage logical composition in reinforcement learning to create a framework that enables an agent to autonomously determine whether a new task can be immediately solved using its existing abilities, or whether a task-specific skill should be learned. In the latter case, the proposed algorithm also enables the agent to learn the new task faster by generating an estimate of the optimal policy. Importantly, we provide two main theoretical results: we bound the performance of the transferred policy on a new task, and we give bounds on the necessary and sufficient number of tasks that need to be learned throughout an agent's lifetime to generalise over a distribution. We verify our approach in a series of experiments, where we perform transfer learning both after learning a set of base tasks, and after learning an arbitrary set of tasks. We also demonstrate that, as a side effect of our transfer learning approach, an agent can produce an interpretable Boolean expression of its understanding of the current task. Finally, we demonstrate our approach in the full lifelong setting where an agent receives tasks from an unknown distribution. Starting from scratch, an agent is able to quickly generalise over the task distribution after learning only a few tasks, which are sub-logarithmic in the size of the task space.

Published as a conference paper at ICLR 2022
GENERALISATION IN LIFELONG REINFORCEMENT LEARNING THROUGH LOGICAL COMPOSITION
Geraud Nangue Tasse, Steven James & Benjamin Rosman School Computer Science and Applied Mathematics University of the Witwatersrand Johannesburg. South Africa geraudnt gma com, (steven. james, benjamin. rosmanl @ewits..cc...
ABSTRACT
We leverage logical composition in reinforcement learning to create framework that enables an agent to autonomously determine whether a new task can be immediately solved using its existing abilities, or whether a task-specific skill should be learned. In the latter case, the proposed algorithm also enables the agent to learn the new task faster by generating an estimate of the optimal policy. Importantly, provide two main theoretical results: we bound the performance of the transferred policy on a new task, and we give bounds on the necessary and sufficient number of tasks that need be learned throughout agent's lifetime generalise over a distribution. We verify our approach in a series of experiments, where we perform transfer learning both after learning set of base tasks, and after learning an arbitrary set of tasks. We also demonstrate that, as a side effect of our transfer learning approach, an agent can produce an interpretable Boolean expression of its understanding of the current task. Finally, we demonstrate our approach the full lifelong setting where an agent receives tasks from an unknown distribution. Starting from scratch, an agent is able to quickly generalise over the task distribution after learning only a few tasks, which are sub-logarithmic the size of the task space.
INTRODUCTION
Reinforcement learning (RL) is framework that enables agents to learn desired behaviours by maximising the rewards received through interaction with an environment (Sutton et al.) [1998.. While
RL has achieved recent success in several difficult, high-dimensional domains (Mnih et al. 2015
Levine et al. 2016 Lillicrap et al. 2016 Silver et al. (017), these methods require millions of samples from the environment to learn optimal behaviours. This is ultimately fatal flaw, since learning to
solve complex, real-world tasks from scratch for every task of interest is typically infeasible. Hence a major challenge in RL is building general-purpost agents that able to existing knowledge quickly solve new tasks in the environment. The question of interest is then: after learning n tasks sampled from some distribution, how can an agent transfer leverage the skills learned from those tasks to improve its starting performance or learning speed in task n + 1?
This problem setting formalised by lifelong RL (Thru 1996 Abel al. 2018). One approach to transfer in lifelong RL is composition (Todorov) 2009). which allows an agent to leverage its existing skills to build complex, novel behaviours that can then be used solve or speed up learning of a new
task (Todorov) 2009: Saxe et al., 2017 Haarnoja et al. 2018 van Niekerk et al. 2019 Hunt et al. |019| et al. 2019). Recently, Nangue Tasse et al. (2020) proposed framework for defining Boolean algebra over the space of tasks and their optimal value functions. This allowed for tasks and value functions to be composed using the union, intersection and negation operators in a principled manner to yield optimal skills zero-shot.
In this work, we propose a framework for lifelong RL that focuses not only on transfer between tasks for faster RL, but also provides guarantees the generalisation of an agent's 'ss skills over unknown task distribution. We first extend the logical composition framework of Nangue Tasse et al. (2020) to discounted and stochastic tasks. We provide theoretical bounds for our approach in stochastic settings,

---

Published as a conference paper at ICLR 2022
and also compare them to previous work in the discounted setting. We then show how our framework leverages logical composition to tackle the lifelong RL problem. The framework enables agents to iteratively solve tasks as they are given, while at the same time constructing a library of skills that can be composed to obtain behaviours for solving future tasks faster, or even without further learning.
We empirically verify our framework in series of experiments, where an agent is i) pretrained on a set of base tasks provided by the Boolean algebra framework, and ii) when the pretrained tasks are not base tasks. We show that agents here are able achieve significant jumpstarts on new tasks. Finally, we demonstrate our framework in the lifelong RL setting where an agent receives tasks from an unknown (possibly non- con-stationary) distribution and must determine what skills to learn and add to its library, and how to combine its current skills to solve new tasks. Results demonstrate that this framework enables agents to quickly learn set of skills, resulting in a combinatorial explosion in their abilities. Consequently, even when tasks are sampled randomly from an unknown distribution, an agent can leverage its existing skills to solve new tasks without further learning, thereby generalising over task distributions.
2 BACKGROUND
We consider tasks modelled by Markov Decision Processes (MDPs). An MDP is defined by the tuple (S,A, r, 7), where (i) S is the state space, (ii) A is the action space, (iii) p(s' (s,a) is Markov transition probability, (iv) r is the real-valued reward function bounded by [TMIN, rMAX]. and (v) 7 E [0, 1) is the discount factor. In this work, we focus on tasks where agent is required to reach a set of desirable goals in goal space G C S (a set of boundary states). Here, termination in is modelled similarly
van Nickerk et al. (2019) by augmenting the state space with a virtual state, such that p(w|s, a) = (Vs,,a) a) E (9 A) and the rewards are zero after reaching w. We hence consider the set of tasks M such that the tasks are in the same environment described by a background MDP (S, 7, ro),and each task can be uniquely specified by set of desirable and undesirable goals:
M(S,A,PP = ((p.)))).)))) Va E A, r(s, = ro((s Vs E
r(g.a) = ry E {rMIN. TMAX] Vg E 9}
(I)
The goal of the agent is 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*8 (s) = E,, EΣ,,, 7'r(st, at)], 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) = (*)s) = max, V*(s) for all in S. A related quantity is the Q-value function, Q"((sa), which defines the expected return obtained by executing a from 8, and thereafter following æ. Similarly, the optimal Q-value function given by (2, a) max, (= a) for all s S and a in A.
2.1 LOGICAL COMPOSITION
Nangue Tasse et al. 2020 recently proposed the notion of a Boolean task algebra, which allows an agent to perform logical
cenatiionn-oojnnntttiin (A), disjunction (V) and negation (-)-over the space of tasks and value functions. While they only considered deterministic shortest path tasks (y = with deterministic dynamies), we summarise their approach here and later extend it to discounted stochastic tasks (Section 3.1
To achieve zero-shot logical composition, Nangue Tasse et al. (2020) extend the standard rewards and value functions used by agent to define goal-oriented versions follows:
Definition 1. The extended reward function S G x R is given by the mapping
TMIN if f and a E G (s.g, + (r(),a) otherwise,
(2)
where FMIN S. min(FMMN, - (MMN) and D is the diameter of the MDP (Jaksch et al. 2010). function Definition 2. The extended functionn Q S x G x A + R is given by the mapping
(8,9,0) a) +ト F(8,9,0) 0) + Σ p( (s),
(3)
2

---

Published as a conference paper at ICLR 2022
where ("(s,) E, 1Ei=o F(s,...a)) a.)]
By penalising the agent for achieving goals different from those it wanted to reach (FMIN if * and s G). the extended reward function has the effect of driving the agent to learn how to separately achieve all desirable goals. Importantly, the standard reward and value func- tions be recovered from their extended versions by simply maximising such, the agent can also recover the task policy by maximising over both goals and actions: (s) arg max maXgeg Q(s, 9. a.a..
goals. As
The logic operators over tasks and extended action-value functions are then defined as follows:
Definition 3. Lel M be a set of tasks with bounds MMIN MMMNNMMMx E M such that, TMMIN (5, a) = min TM (s,(s)) a) MEM
TMMAX (s,a) = max T' (s, a)
MEM
Define the 7, V, and operators over M as
(M) = (S, A. p, r-d),, where (-M (PMMAx(s,0) M.MMM (8, - (s,
V(M, M2) (S, where TM, TM (8, a) = max(rM, (8, a). rM (8, a))
A(MI, M2) = (S, (.....MM)..))) where (s,A, = min(rM (8, a), rMg a)}
Definition 4. Let Q" be the set of optimal extended Q-value functions for tasks in M, with bounds QMINN, QMMX E Q" which are respectively the optimal Q-functions for the tasks MMAX M. Define the -,V, and operators over Q* as.
((,')s,) = (QaiIN(, (.)
A(O1. (501,0)(ss.g.a)) = 0ttp::066.0o0mmmiii(r/gg........ min(((((s..0000(1.....)
Using the definitions for the logical operations over M and Q" given above, Nangue Tasse al. (2020) construct a Boolean algebra over tasks and extended value functions. Furthermore, by leveraging the goal-oriented definition of extended value functions, they also show that M and Q* are homomorphic. As result, if a task can be expressed using the Boolean algebra, the optimal value function for the task can immediately be computed. This enables agents to solve any new task that given as the logical combination of learned ones.
3 LIFELONG TRANSFER THROUGH COMPOSITION
In lifelong RL, an agent is presented with a series of tasks sampled from some distribution D. The agent then needs not only transfer knowledge learned from previous tasks solve new but related tasks quickly, but it also should not forget learned knowledge in the process. We formalise this lifelong learning problem follows:
Definition 5. Let D be unknown, possibly non-stationary, distribution over set of tasks M(S, p,),) The lifelong learning problem consists of the repetition of the following steps for LE N:
1. The agent is given a task M, ~ D(t).
2. The agent interacts with the MDP Mr until it is e-optimal in Mo, Me.
This formulation of lifelong RL is similar to that of Abel et al. (2018;; the main difference is that we do not assume that D is stationary, and we explicitly require agent retain leamed skills.
As discussed the introduction, one of the main goals in this setting is that transfer (Taylor & Stone 2009). We add important question this setting: how many tasks should agent learn
3

---

Published as a conference paper at ICLR 2022
during its lifetime in order to generalise over the task distribution? In other words, how many tasks should it learn to be able to solve any new task immediately? While most approaches focus on the goal of transfer, the question of the number of tasks is often neglected by simply assuming the case where the agent has already learned n tasks (Abel et al. 2018 Barreto et al., 2018). Consider, for example, a task space with only |و] 40 goals. Then, given the combination of all possible goals, the size of the task space is [M]] 2 ss 10 If D is a uniform distribution over [.M], then for most transfer learning methods an agent will have to learn most of the tasks it is presented with, since the probability of observing the same task will be approximately zero. This is clearly impractical for a setting like RL, where learning methods often have a high sample complexity even with transfer learning. is also extremely memory inefficient, since the learned skills of most tasks must be stored.
3.1 EXTENDING THE BOOLEAN ALGEBRA FRAMEWORK
In this section, we show how logical composition can be leveraged to learn subset of tasks that is sufficient to generalise over the task distribution. Since the logical composition results of Nangue Tasse et al. (2020) were only shown for deterministic shortest path tasks (where y = 1), we extend the framework to discounted and stochastic tasks M (Equation D. To achieve this, we first redefine the extended reward function (Definition I
to use the simpler penalty EMIN = TMIN. We
also redefine over Q as follows:
if if(( (max(( (MIIN() otherwise,
1 OMIN (²)() -Qaxx( ESxGxX
()))))=
The intuition behind this re-definition of the negation operator is as follows: since each goal is either desirable or not, the optimal extended value function Q" g. a) is either Qiaa (s. g. a) or QMINN(S (s. (.S...... a). Hence, if (s, g. a) is closer QMAX (8,9. 9. a), and vice versa. For tasks in M. this is equivalent to the previous definition of - for optimal Q-value functions, but it will give us tight bounds when composing 6-optimal Q-value functions (see Theorem 1.
MIIN (s. g. a), then its negation should be
We now show that the Boolean algebra and zero-shot composition results of Nangue Tasse et al. (2020) also hold for tasks in M.
Proposition 1. Let Q" be the set of optimal Q-value functions for tasks in M. Let st M - ¹" be any map
from map
M to º³ such that of (M) = Qhs is for all M in M. Then,
(i) M and ¹* respectively form a Boolean task algebra (M,VA,, -, MMAXX,MMNN and a Boolean extended value functions algebra (²', A,A, QMAX: VMIND.
(ii) a is a homomorphism between M and "*
We now solve any new task in M zero-shot if are given the correct Boolean expression that informs the agent how to compose its optimal skills. This is essential for the following results.
3.2 TRANSFER BETWEEN TASKS
In this section, we leverage the logical composition results to address the following question of interest: given an arbitrary set of learned tasks, can we transfer their skills to solve new tasks faster? As will show in Theorem | we answer this question in the affirmative. To achieve this, we first note that each task M E M can be associated with a binary vector T E {0, 1] which represents its set of desirable goals, as illustrated by the tasks in Table The approximation π of this task representation can be learned just from task rewards (raz (s, a)) by simply computing T(s) = 1 (x Ax at each terminal state that the agent reaches. We can then use any generic method, such the sum-of- products (SOP), to determine a candidate Boolean expression (BEXP) in terms of the learned binary representations J, = .T..... } of a set of past tasks . = [M,,..,, 3, C M. An estimate of the optimal Q-value function of M can then be obtained by composing the learned Q-value functions Ō; = (Ộr,... Φ according to BExP. Theorem shows the optimality of this process!
See Appendix A for proofs of theorems and Appendix for brief description of the SOP method.
4

---

Published as a conference paper at ICLR 2022
Theorem 1. Let M M be task with reward function binary representation T and optimal extended action-value function Q.. Given e-upproximations of the binary representations Tn = (TI...,TT, and optimal Q Q-functions ē; (Qi,.... .....Q.)
for for tasks M {M..... Mn} M,, let
TF= = (T and QF = BEXP((n))
where BEXP is derived from In and T using a generic method F. Define ((8) arg mA Qr where QF == maxgeg Qr a). Then,
(i) 1Q-- S T (UT+T, + trerroha +c). (ii) if the dynamics are deterministic,
||Q - QFllo S (1a
where I is the indicator function, rg(s,a) == F(s,g.0), TA = -MAX - TMIN and IIf hlloo =
gax [[(s, [s,, h(s, (,,, a)).
Theorem i states that Q, is close to optimal, then acting greedily with respect to it is also close
to optimal. Interestingly, this is similar to the bound obtained by Barreto al. (218)) (Proposition 1) for transfer learning using generalised policy improvement (GPI), but stronger This is unsurprising, since (s)) arg max maxgeş (r g, a) can be interpreted as generalised policy improvement on the set of goal policies of the extended value function Q Importantly, if the environment is deterministic, then we obtain a strong bound on the composed value functions (Theorem (i)) This bound shows that transfer learning using logical composition is 6-optimal-that is, there is no loss in optimality-wher the new task expressible as a logical combination of past ones. With the exponential nature of logical combination, this gives agents strong generalisation ability over the task space-and and hence over any task distribution-4 as we will show in Theorem 2
3.3 GENERALISATION OVER A TASK DISTRIBUTION
We leverage Theorem I to design an algorithm that combines the SOP approach with goal-oriented learning to achieve fast transfer in lifelong RL. Given an off-policy RL algorithm sf the agent initializes its extended value function Q, the task binary vector T, and goal buffer. At the beginning of each episode, the agent computes Tsop and QsoP for T using the SOP method and its library of learned task vectors and extended Q-functions. It then acts using the behaviour policy (e-greedy for example) of of with QsOP for the action- action-value function if TsoP T, and QsOP V Q otherwise TSO # T, the agent also updates Q for each goal in the goal buffer using s/. Additionally, when the agent reaches a terminal state s, it adds it to the goal buffer and updates T(s) using the reward receives (T) (x. Training stops when the agent has reached the desired level of optimality (or after episodes in practice), after which the agent adds the learned π and Q to its library if Tsor # Î. The full algorithm included in Appendix B We refer to this algorithm as SOPGOL (Sum Of Products with Goal-Orientee Learning).
When is finite, we show Theorem that SOPGOL generalises over any unknown task distribution after learning only number of tasks logarithmic in the size of the task space. The lower bound is [[og[[]] since this is the minimum number tasks that span the task space, as can be seen in Table I (top) for example. The upper bound is [ because that is the dimensionality of the task binary representations {0, 1) Since the number of tasks is JM 2 we have that the upper bound |G] = [g|=log]MM M| is logarithmic in the size of the task space.
2See Section 1.4 of the appendix for detailed discussion of this with the simplification of the bound in Proposition 1 (Barreto et al. 2018) to the same form as Theorem Ii).
SSince QSOP V Q max QsOP, Q). it is equivalent GPI and hence is guaranteed to be equal optimal than the individual value functions. Hence using Qsor Q in the behaviour policy gives straightforward way of leveraging Qsor to learn Q faster.
5

---

Published as a conference paper at ICLR 2022
Theorem 2. Let D be unknown, possibly non-stationary, distribution set of tasks M(S.A, Y, with finite G. Let of (M) Qis for all M in M. Let
:M Q: be any map from M to Q such that
T++, θi+1 SOPGOL Mr Tr, 21) where Mr D(t) and To 20 Ø e.N.
Then,
[log [9|] < lim N₂ S [g] where N₂ = [7]] = 15:1
t-100
Interestingly, Theorem 2 holds even in the where task is expressible in terms of past tasks (Tsor- -T), but wish solve it to higher degree of optimality than past tasks. In this case, can pretend TsoP + T and learn new Q-function the desired degree of optimality. We can then add it to our library, and remove any other skill from our library (the least optimal for example).
4 EXPERIMENTS
Goals
1
9
T
75
0
0
1
1
0
T
T2
0
0
0
I
1
8
Goals
1
B
0
0 0
75
0
0
D
Figure 1: PICKUPOBJ domain.
Table I: Binary representation for base (top) and test (bottom)
The red triangle represents the agent.
tasks. 0 or 1 corresponds to a goal reward of TMIN TMAX.
4.1 TRANSFER AFTER PRETRAINING ON A SET OF TASKS
We consider the PICKUPOBJ domain from the MINIGRID environment (Chevalier-Boiie Boisvert et 2018), illustrated by Figure I where an agent must navigate in a 2D room to pick up objects of various shapes and colours from pixel observations This type domain is prototypical in the literature (Nangue Tasse et al. 2020 Barreto et al., 2020 van Niekerk et al.) 2019 Abel et al. 2018). because it allows for casy demonstration of transfer learning in many-goal tasks. In this domain, there are [ = 15 goals each corresponding to picking up objects of 3 possible types- box, ball, key-and 5 possible colours- redd blue, green, purple, and yellow. Hence a set of [loga [g]] base tasks can be selected that can be used to solve all 2| = 32768 possible tasks under a Boolean composition of goals. The agent receives reward of when it picks up desired objects, and 00.1 otherwise. For all of our experiments in this section, we use deep Q-learning (Mnih et al. 2015) the RI. method for SOPGOL and the performance baseline. We also compare SOPGOL to SOPGOL-transfer. or to SOPGOL-continual SOPGOL-transie learned and SOPGOL-continual refers when new skill is always learned using the SOP Q estimate to speed up learning, even if the new task could be solved zero shot. Since SOPGOL determines automatically which one use, we compare whichever one it chooses with the other one in each of our experiments.
refers to when no new skill is
We first demonstrate transfer learning after pretraining on set base tasks-a minimal set of tasks that span the task space. This can be done if the set of goals is known upfront, by first assigning Boolean label to each goal table and then using the rows of the table as base tasks. These are illustrated in Table (top). Having learned the e-optimal extended value functions for our base tasks,
Further environment details are given in Appendix D

---

Published as a conference paper at ICLR 2022
Returss
contrcal DOn
SDMOOL D0V
S00GOL
-16
60
10
A5 Episodes
20
10
-10
69
1/ Episodes
2.3
Goals
Geale
Episodes
Episodes
Episodes
(a) M1
(b) M2
(c) M3
Figure 2: Episodic returns (top) and learned binary representations (bottom) for test tasks M1, M₂ and M3 after pretraining on the base set of tasks Ma. Mr. M, and Ma. The shaded regions on the episodic returns indicate one standard deviation over 4 runs. The learned binary representations similarly averaged over runs, and reported for the first 500 episodes. The initial drop in DQN performance is result of the initial exploration phase where the exploration constant decays from 0.5 to 0.05. The Boolean expressions generated by SOPGOL during training for the respective test tasks are:
Mi
Me A Mr A Mc Ma.
M2 =
(Ma A -M, A -Ma) (Ma A Mc A MJ) V (- A M, A - A -Ma) V (-Ma A
MM, A -M A Ma).
M3 = =(M A M, M.) V (Ma A -M -Ma) V (Ma A M. A Ma) V-MaAMMA MMA
-Ma) (-Ma A MM, A -M, A Ma) V (-M, A Mc Ma).
we can now leverage logical composition for transfer learning on test tasks. We consider the three test tasks shown in Table (bottom). For each, we run SOPGOL, SOPGOL-continual and a standard DQN. Figure illustrates the results where, as predicted by our theoretical results in Section 3.2 SOPGOL correctly determines that the current test tasks are solvable from the logical combinations of the learned base tasks. Its performance from the start training hence the best.
Now that we have demonstrated how SOPGOL enables agent to solve any new task in an environment after training on base tasks, we consider the more practical case where new tasks are not fully expressible as Boolean expression of previously learned tasks. The agent in this case
SONGOL
Returns
Raturns
Soro2L serdder
SorGOL
50nCOL tranaeer
D0N
DCN
Episodes
364
Episodes
144
Episodes
3x3
Goals
Goals
Episades
Episades
1x2
Episodes
(a) M1
(b) M2
(c) M3
Figure 3: Episodic returns (top) and learned binary representations (bottom) for test tasks Mj. M2 and M3 after pretraining the non-base of tasks returns indicate one standard deviation over 4 runs. The learned binary representations are similarly averaged over runs, and reported for the first 500 episodes. The initial drop in DQN performance is a result of the initial exploration phase where the exploration constant decays from 0.5 to 0.05. The Boolean expressions generated by SOPGOL for the respective test tasks are:
and The shaded regions the episodic
Mi
M2
V((
A A A
-t)
M₁
7

---

Published as a conference paper at ICLR 2022
is pretrained a set of tasks that do not span the task space, tasks of picking up green objects. blue objects, yellow objects, and keys. We then train the agent with SOPGOL, SOrGOL-rransfer, and standard DQN the same set of test tasks considered previously (Table (bottom)) The results in Figure 3 demonstrate how SOPGOL now chooses to learn task-specific skill after transfer, and hence outperforms SrrGOL-rransfer since the test tasks are not entirely expressible in terms of the pretrained ones. Consider Figure 3a for example. The test task is to pick up yellow box, but the agent has only learned how pick up red objects, blue objects, yellow objects, and keys. It has not learned how to pick up boxes. However, we note from the inferred Boolean expression (M1) that the agent correctly identifies that the desired objects are, at the very least, yellow. Without further improvements to this transferred policy (SOPGOL-transfee can see that this approach outperforms DQN from the start. This is due to two main factors: (i) the transferred policy navigates to objects more reliably, so takes fewer random actions; and (ii) although the transferred policy does not have a complete understanding of which are the desirable objects, at least navigates to yellow objects, which are sometimes yellow boxes.
8). corresponding to the
Finally, since SOPGOL is able determine that the current task is not entirely expressible in terms of its previous tasks (by checking whether TSop = 'T), is able learn a new Q-value function that improves on the transferred policy. Additionally, its returns are strictly higher than those of SOPGOL. because SOPGOL learns the new Q-value function faster by using Qsor V Q in the behaviour policy.
4.2 LIFELONG TRANSFER
In this section, we consider the more general setting where the agent is not necessarily given pretrained skills upfront, but is rather presented with tasks sampled from some unknown distribution. We revisit the example given in Section 3] but now more concretely by using a stochastic Four Rooms domain (Sutton et al. 1999), with goal space of size |g] = 40 and task space of size |M| 2 = 10
Complete environment details are given in Appendix C
We demonstrate the ability of SOPGOL generalise over task distributions by evaluating the approach with the following distributions: (i) 'D Dsampied: the goals for each task are chosen uniformly random over 9; (ii) Dreat: the first [log, [9]] tasks the base tasks, while the rest follow D Pempled. This distribution gives the agent the minimum number of tasks to learn and store, since the agent learns the base tasks first before being presented with any other task. (iii) Dworsti the first [G] tasks are each defined by single goal that differs from the previous tasks, while the rest follow D Dsampled. This distribution forces the agent to learn and store the maximum number of tasks, since none of the [g] tasks can be expressed as a logical combination of the others. We use Q-learning (Watkins) 1989) as the RL method for SOPGOL, and Q-learning with max initialisation as a baseline. This has been shown by previous work (Abel al., 2018) to be practical method of initialising value functions with a thcoretically optimal optimism criterion that speeds-up convergence during training. Our results (Figure 4 show that SOPGOL enables a lifelong agent to quickly generalise over an unknown task distribution. Interestingly. both graphs show that the convergence
X33
Des
Dasnt
Policies stored
Dhaught
2.0
Timestpp
mas
0.5
1.0
20
43
14
Tasks
Tasks
(a) Number of policies learned and stored after solving tasks.
(b) Number of samples required to learn 6- optimal policies for each task.
Figure 4: Number of policies learned and samples required for the first 50 tasks of an agent's 's lifetime in the Four Rooms domain. The shaded regions represent standard deviations over 25 runs.
8

---

Published as a conference paper at ICLR 2022
speed during a randomly sampled task distribution D Dampled is very close that of the best task distribution Dbest. This suggests that there is room to make the bound in Theorem 2 eeen tighter by making some assumptions on the task distribution- interesting avenue for future work.
RELATED WORK
There have been several approaches in recent years for tackling the problem of transfer in lifelong
RL. Most closely related is the line of work on concurrent skill composition ( [oooooov] 2009; Saxe
et al. 2017 Haarnoja et al.] 2018 van Niekerk et al.] 2019 Hunt et al.] 2019). These methods usually focus on multi-goal tasks, where they address the combinatorial amount of desirable goals by composing learned skills to create new ones. Given a reward function that is well approximated by
a linear function, |Barreto et al. (2020) propose scheme for few-shot transfer in RL by combining GPI and successor features (SF) (Barreto al.) 2017). In general, approaches based on GPI with SFs (Barreto et al., )021) are suitable for tasks defined by linear preferences over features (latent goal states). Given the set of features for an environment, [Alver Precup (2022) shows that base set of successor features can be learned, which is sufficient to span the task space. While these approaches also support tasks where goals are not terminal, the smallest number of successor features that must be learned to span the task space is | (the upper-bound in Theorem 2). Our work is similar to these approaches in that it can be interpreted as performing GPI with the logical composition of extended value functions, which leads to stronger theoretical bounds than GPI with the linear composition of successor features (see Appendix A.4). Finally, none of these works consider the lifelong RL setting where an agent starts with no skill and receives tasks sampled from unknown distribution (without additional knowledge like base features or true task representations). In contrast, SOPGOL is able to handle this setting with logarithmic bounds on the number of skills needed to generalise over the task distribution (Theorem 2
Other approaches like options (Sutton et al. 1999) and hierarchical RL (Barto & Mahadevan 2003) address the lifelong RL problem via temporal compositions. These methods are usually focused on single-goal tasks, where they address the potentially long trajectories needed to reach a desired goal by composing sub-goal skills sequentially (Levy et al., [017 BBaaaria & Konidaris 2019). While they do not consider the multi-goal setting, they can be used conjunction with concurrent composition to learn how to achieve combinatorial amount of desirable long horizon goals. Finally, there also non non-coopositional approaches (Finn et al. 2017 Abell et al., 2018; (iinhh et al. 202I). which usually aim to learn the policy for a new task faster by initializing the networks with some pre-training procedure. These can be used in combination with SOPGOL to learn new skills faster.
6 CONCLUSION
In this work, we proposed an approach for efficient transfer learning in RL. Our framework, SOPGOL, leverages the Boolean algebra framework of Nangue Tasse et al. (0020) determine which skills should be reused in a new task. We demonstrated that, if a new task is solvable using existing skills, an agent is able solve it with further learning. However, even if this is not the case, an estimate of the optimal value function can still be obtained to speed up training. This allows agents in a lifelong learning setting to quickly generalise over any unknown (possibly satssttttooay) task distribution.
The main limitation of this work is that it only consider tasks with binary goal ewwards-whers goals are either desirable or not. Although this covers vast number of many-goal tasks, combining our framework with works on weighted composition (van Nickerk et al. 2019 Barreto et al., 2020) could enable a similar level of generalisation over tasks with arbitrary goal rewards. Another exciting avenue for future work would be to extend our transfer learning and generalisation results to include temporal tasks by leveraging temporal composition approaches like options. Finally, we note that just like previous work, we rely on the existence of an off-the- RL method that is able to learn goal-reaching tasks in a given environment. Since that is traditionally very sample inefficient, our framework can be complemented with other transfer learning methods like MAXQINIT (Abel et al. 2018) to speed up the learning of new skills (over and above the transfer learning and task space generalisation shown here). Our approach is step towards the goal of truly general, long-lived agents, which are able to generalise both within tasks, as well as over the distribution of possible tasks it may encounter.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
GNT is supported by an IBM PhD Fellowship. This research was supported. in part, by the National Research Foundation (NRF) of South Africa under grant number 117808. The content is solely the responsibility of the authors and does not necessarily represent the official views of the NRF.
The authors acknowledge the Centre for High Performance Computing (CHPC), South Africa, for providing computational resources to this research project. Computations were also performed using High Performance Computing Infrastructure provided by the Mathematical Sciences Support unit the University of the Witwatersrand.
REFERENCES
D. Abel, Y. Jinnai, S. Guo, G. Konidaris, and M. Littman. Policy and value transfer in lifelong reinforcement learning. In International Conference on Machine Learning, pp. 20-29, 2018.
S. Alver and D. Precup. Constructing good behavior basis for transfer using generalized policy updates. In International Conference on Learning Representations, 2022. URL https:// openreview net
A. Bagaria and Konidaris. Option discovery using deep skill chaining. International Conference Learning Representations, 2019.
A. Barreto, W. Dabney, R. Munos, J. Hunt, T. Schaul, H. van Hasselt, and D. Silver. Successor features for transfer in reinforcement learning, In Advances in Neural Information Processing Systems, pp. 4055-4065, 2017.
A. Barreto, D. Borsa, J. Quan, T. Schaul, D. Silver, M. Hessel, D. Mankowitz, A. Zidek, and R. Munos. Transfer deep reinforcement learning using successor features and generalised policy improvement, In International Conference on Machine Learning, pp. 501-510. PMLR, 2018.
A. Barreto, Hou, D. Borsa, D. Silver, and Precup.
Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 1 117(48)330099-3000 2020.
A. Barreto, Borsa, S. Hou, G. Comanici, E. Aygün, P. Hamel, D. Toyama, J. Hunt, S. Mourad, D. Silver, et al. The option keyboard: Combining skills in reinforcement learning. arXiv preprint arXiv:2106. 13105, 2021.
A. Barto and S. Mahadevan. Recent advances in hierarchical reinforcement learning, Discrete event dynamic systems, 1311:441-77, 2003.
M. Chevalier-Boisvert, L. Willems, and S. Pal. Minimalistic gridworld environment for openai gym. gym-minimmmmimmmm 2018.
https: com
C. Finn, Abbeel, and Levine. Model-agnostic meta-lcarning for fast adaptation of deep networks.
In International Conference on Machine Learning, pp. 1126-1133 PMLR, 2017.
Haarnoja, V. Pong, A. Zhou, M. Dalal, P. Abbeel, and S. Levine. Composable deep reinforcement learning for robotic manipulation. In 2018 IEEE International Conference Robotics and Automation, pp. 6244-6251, 2018.
J. Hunt, A. Barreto, T. Lillicrap, and N. Heess. Composing entropic policies using divergence correction. In International Conference on Machine Learning, pp. 2911-2920. 2019.
T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(0 2010.
S. Levine, C. Finn, T. Darrell, and P. Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 1334331334-333, 2016.
A. Levy, R. Platt, and K. Saenko. Hierarchical actor-critic. arXiv preprint arXiv: 12. 2017.
10

---

Published as a conference paper at ICLR 2022
T.. Lillicrap, J. Hunt, A. Pritzel. N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. International Conference on Learning Representations, 2016.
V. Mnih, K. Kavukcuoglu, D. Silver, A. 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.
G. Nangue Tasse, S. James, and Rosman. A Boolean task algebra for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
X. Peng, M. Chang, G. Zhang, P. Abbeel, and S. Levine. MCP: Learning composable hierarchical control with multiplicative compositional policies. In Advances in Neural Information Processing Systems, pp-
2019.
A. Saxe, A. Earle, and B. Rosman. Hierarchy through composition with multitask LMDPs. Interna- tional Conference on Machine Learning, pp. 3017-3026, 2017.
D. Silver, J. Schritwieeser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L.. Baker, M. Lai, Bolton, et Mastering the game of Go without human knowledge. Nature, 550(7676): 354, 2017.
A. Singh, H. Liu, G. Zhou, A. Yu, N. Rhinehart, and S. Levine. Parrot: Data-driven behavioral priors for reinforcement learning. In International Conference on Learning Representations, 2021.
N. Subrahmanyam. Boolean vector spaces. Mathematische Zeitschrift, 83(5):422-433, 1964.
R. Sutton, A. Barto, et al. Introduction to reinforcement learning, volume 135. MIT press Cambridge, 1998.
R. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 1 11((11):111-111, 1999.
M. Taylor and P. Stone. Transfer learning for reinforcement learning domains: survey. Journal of Machine Learning Research, 10:1633-1685, 2009.
S. Thrun. Is learning the n-th thing any easier than learning the first? In Advances in neural information processing systems, pp. 640-646, 1996.
E. Todorov. Compositionality of optimal control laws. In Advances in Neural Information Processing Systems, pp. 1856-1866 2009.
B. Niekerk, S. James, A. Earle, and B. Rosman. Composing value functions in reinforcement learning. In International Conference on Machine Learning, pp. 6401-6409, 2019.
C. Watkins. Learning from delayed rewards. PhD thesis, King's i College, Cambridge, 1989.

---

Published as a conference paper at ICLR 2022
A PROOFS OF THEORETICAL RESULTS
A. BOOLEAN ALGEBRA DEFINITION
Definition 6. Boolean algebra a 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:
a. (ii) Commutativity: a b b and
(i) Idempotence:
(ii) Associativity: a (b c) = (a e cndd as (bV))=
(iv) Absorption: (a V b) = a (a =a
(v) Distributivity: a (b c) = (a (a c) and a (b c) = ((Vo))
(vi) Identity: there exists 0, in such that
0 DAa- = 0
0 a = a
Aaa
1
(vii) Complements: for every in B, there exists an element a' in B such that a A a' 0 0nd a
A.2 PROOFS FOR PROPOSITION
Lemma 1. Let M be a set of tasks. Then (M, MMMIN) is Boolean algebra.
Proof. Let M,, M2 E M. We show that -, V, satisfy the Boolean properties (i) -vvi).
(i)-(v: These easily follow from the fact that the min and max functions satisfy the idempotent, commutative, associative, absorption and distributive laws.
(vi): Let TMMAXAM AM, and rM, be the reward functions for MMAX A M1 and M1 respectively. Then for all (s, a) in S x A,
TMMAXAM, (s,a) = minnfrmAx, T'M (s, a)}, if E (min(ro(s,a) a), ro(s, otherwise.
(s, e a), otherwise.
(s,) frMIN. rMAx] for s 9)
= TM, a).
Thus MMAX A M1 = M₁. Similarly MMAX V M1 = MMAX MMIN A M1 = MMIN.
and MMIN Mj = Mi Hence MMIN and M MA are the universal bounds of M.
(vii): Let TMA-M, be the reward function for M1 A M1 Then for all (s, in S x A,
min((M, (s, a), (rMAX + mMin) - TM, (8, a)}, if TMAA-M (s,a) [min a), (ro a) + ro(s, a)) - ro(s, otherwise.
(MIN,
if E 9 and FM, (8, TMAX
TMAX:
if E & and TM, (8,a) a) = TMIN otherwise.
a))
=TMaIN (s,
Thus Mi A -M -MINN and similarly Mi V -M =MMAX.
12

---

Published as a conference paper at ICLR 2022
Lemma 2. Let Q' be the set of optimal Q-value functions for tasks in M. Then (Q".V,A 7, TMAX: (MIN) is Boolean Algebra.
Proof. Let VM, UMa Q" be the optimal Q-value functions for tasks M1, M2 M with reward functions rM, and FM22- 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.
(vi): For all (s, a) in S x 9 x A.
(MMAx A (8, = min (s, (i TM, (8,9,a)
(nin(Curaxxsss.. (s. (g,,)) TMAX Va' E A (s..
(s,g. (MIN)) a)},
otherwise.
(Qrrax(s,g,a). if (g. TMX Va' A
(S. otherwise.
QM, (s, (since TM, (g, {rMIN, TMAX] Va' E A).
Similarly, QMAX Vh,,
QMAX QMIN Qi, QMINs and QMIN V Qis, Qis,
(vii): For all (.) in S 9 x A.
(Qis, A (.) = min min(Qin, ()), QQi,
(min(QMin (,), (Max())) if @²))(() (() ( 11) QMax (min ()), (M)N()) otherwise,
(..IN().
Similarly, Qi, --M QMAX
Lemma 3. Let Q" be the set of optimal extended Q-value functions for tasks in M. Then for all M2 E M, we have (i) Q-M, = -Qii, (ii) UM. = Qis, V Qiay and (iti) OMAMM= = Qir, ^ Qivz
Proof. Let M1, M2 M. Then for all in A
(::
@-M,(
(MMxx(S, a).
ifr-M, (g. a') TMAX Val E A otherwise.
if (g,a') = PMIN Val E otherwise.
(8,
if Qir, (s, a) = (MIN(s,g,a) otherwise.
(s, (x,I
if QQM, (s, a) Qiainss a) & 197, (s.g,a) Q'Mxx(s,g. otherwise.
Lin, ())
13

---

Published as a conference paper at ICLR 2022
(ii):
(8, (r, = TMAX Va' EA (s.9.n
@M (s.9,a)
otherwise.
QM (),
if max(rM, ( TMAX Va' EA otherwise.
@MINN(S (8.
[iMAx( (8, g,a):
if max (QM, (8,9, a), (h. (āsax(5:9,a) otherwise.
( g,,g.a)
max( (s, g)). (s,,(s,ga))
(QM, V (s,
(iii): Follows similarly (ii).
Proposition 2. Let Q* be the set of optimal Q-value functions for tasks in M. Let of :M - Q* be any map from M to 2' such that of (M) Qis for all M in M. Then,
(i) M and Q" respectively form Boolean task algebra (M,VA, MMAXX and a Boolean extended value functions algebra (Ω", .VA, 7, MMAX QMIND.
(it) of is homomorphism between M and Q*
Proof. (i): Follows from Lemma
1
and
(ii): Follows from Lemma
A.3 PROOFS FOR THEOREM
Lemma 4. Let Q* be the set of optimal Q-value functions for tasks in M. Denote Qig as the c-optimal Q-value function for task M E -M such that
(s, - (ir(s,g,a) Se for all (s.g.a)
Then for all M1, M2 in M and (8,g,a) A.
(i) Qir, v (i,,1(s,g.a) -Qen v V sc
(i)
Qhr, A (i,,1(s, (6:, @ū,,((,,,, Se
(s,g,a) -ii, (s.g.a) sc
(ii)
Proof.
(i)
[ v (in, - -iêi, v V
(s) max
(2r().0)))
max Mg) Mc(M).N))
Qir(s. Qir(s,g.a)
max Mc(
6.
14

---

Published as a conference paper at ICLR 2022
(ii):
QMh, A (Mgl(s,g,a) - 1Âān a @irgl(..9.a)
= min (ir((,
min
(2r(8.9.a)
Ma) Mc(M),M))
min (ir(s, (s,(s,g,a) Mc(M).M2)
$
(iii):
Qai (s,g.a) - (s.g.a)
(0
(M if, = (MIN(8,9,
(1
otherwise.
( (M
if Qh, (MIN(s,g,aa
1 Q'rIn(s,g,a),,
otherwise.
SE.
Lemma 5. Let M -M be task with reward function r, binary representation T and optimal extended action-value function Q². Given e-approximations of the binary representations Tn (T1...,TT, Tn) and optimal Q Q-fanctions 2; (Qi,...,
........ Qi,) for n tasks M {M,,..., Mn} S SM, let
Ty BFxP(TT) and QF (E
where BEXP is derived from tn and T using a generic method F. Define T()) arg max QF where QF == max Qf(8,g,d Then,
1lē² - 1 S (1r4T))a
where 1 is the indicator function. rs h(s,9,a)). a)).
TMAX TMIN. and ||f blloo = max, lf(ssg.a)
Proof.
(s.gg..)) Qx(s,g,
- (, Q=(s. a. < <1Q"(s,9,.) + Q=(s, a)
< <1Q"(s,9,a) ())
(Using Lemma
IfT TTT=Tr. then Q" a) = (= a), and wee done. Let + Ty. Without loss of generality, let (*(,.g,a) = QMAX (s. g. and Q3 (s. g. QUMIN(S.g. Then,
(Q" (5 a)l 1 < (s. (mnN(ss
STA.
Lemma 6. Let Q" and Q* be the optimal Q-value function and optimal extended Q-value function respectively for a deterministic task in M. Then for all (s, a) in A, we have
(x a) = max (.)
gEg
15

---

Published as a conference paper at ICLR 2022
Proof. We first note that
7(s,, i
maxf(s,g,a)
otherwise. = as),
(4)
maxr(s. r(8, a); .99
gEg
Now define
mmaz(s, max Q" (*) gE9
Then it follows that
[Tiinar] (s, (g.a)=r(s,a)) +y Σ
p(s'|s, a) max Qimalss a') a'EAA
s'ES
=r(s,a) +7
Σ
p(s'|s,
max a'EA
max (s' (s'.g.aaa) g. DEg
s'ES
= =r(ssa) + Σ
p(s'ls
max DEG
max Q' (6' (6',g, a'EA
s'ES
= =r(s,a) + max
Σ e'ES
p(8'(s, a) max (' ('''..a')) 2.a')
(Since is deterministic)
8E9
maxF(ss90
p(s'l a) max (s' (s..g.a)) ? Σ
(Using Equation 4
.EG
DEG
a'EA
s'ES
F(s: g. a) + Σ (s))) max ('('s,
max 9EG
a'EA
since F(s, g, a) = a) Vs 9 and p(s, a, = 1 with d'' = =0 E G.
max Q" (s.
DEG
Qiann (s, a).
Hence Qina is fixed point of the Bellman optimality operator. If E G. then
(s max Q" (s,gg.a) maxf(s,ggo) = r(s,a) Q(
9Eg
gEß
Since Qinan Q" holds and Qinan a fixed point of the Bellman operator, then Qinan Q* holds everywhere.
Theorem 1. Let M E MM be task with reward function r, binary representation T and optimal extended action-value function Q-. Given e-approximations of the binary representations Tn (Ti,.., Tnj and optimal Q-functions 2; -Qi,, Qi.) for tasks M [M,,.., Mn) C M, let
TF BTXP(TT) and Q BEXP(²"),
where BEXP is derived from T. and T using a generic method F. Define T(s) e arg max Qr where QJ maxgec Qr Then,
(i) IQ' - 1 S - (UTTTT + tretrola + +c),
(ii) if the dynamics deterministic,
l|Q" QFllo & (ITYTy)ra +
16

---

Published as a conference paper at ICLR 2022
where I is the indicator function. rg(s.a) = F(s,g.a), rs TMAX MMIN, and |I hello g.x. (f a) h(s, a.)).
Proof. (i): We first note that each g in 9 can be thought of as defining an MDP Mg (S,A, P. 7) with reward function rg( a) == F(s, 9. a), optimal policy =s(s) (s, and optimal Q-value function Q = (s, a). Then this proof follows similarly to that Barret al. (2017) Theorem 2,
(s, (s)
(s, - (s, + 1-7 (11 )T +
(Barreto al, (0117) Theorem 1)
2
2
< 1 y
max |r(s, a) (s) +
1-7 (11TTT>)r )ra +()
(Barreto et al. (017) Lemma 1)
(L Mr 1-7 ((1TT>>) ) +e)
(Since rewards only differ in 9 where r(s, a), (8) E (rMIN, for 9)
1-7 (LTTTT> + 1.4rr) )ra t)).
Hence,
2
10" 10
((ITTT> min 1r )rs + +e)
1 1-9
8
2
$
1 ((IYTT> 144h)a rra + c)
(Since min 1,4r, only when E (rahei).
(ii):
((s,a)-Qx((5)) max (*,,,,, max (=(s, a)
(Lemma
9
g
I max (s - (s(s.g
< (ITAT))ra+ +E. (Lemma
A.4 COMPARING THE ROUNDS OF THEOREM WITH THAT OF GPI IN BARRETO ET AL. (2018)
We first restate Proposition
Barreto et al. 2018 here.
Proposition 3 ((Brrrtoo al. 2018). Ler M e M and let Q,¹² be the action value function of an optimal policy of M, E M when executed in M, E M. Given approximations { ,.., QTh such that QQ, 2,1² < e for all s, E S x A, and j E [l,...,nh, let
T(s) arg max max Q, (8, a).
3
then,
2 (1|r T /lc + min ||: ry 1/ + c),
QQ" --1l
1-
where Q" is the optimal value function of M. Q is the value function of a in M, and || hllbo = max (s ((8,g,0) g)a) hhs,g,a))
17

---

Published as a conference paper at ICLR 2022
We simplify the bound in Proposition 3 as follows:
2
lIQ 2=1
1 (I|r rill00 + min
j |r; rylloo +e)
2
$ 1 1-7 (11,4r)r + min |r, - rryllo +e)
(Since rewards only differ in where r(s, a(), E (rMIN, for 9)
2
(1ntrrr + (min metts rra +c)
3
2
I ((1rm))a )aa (1) +c)
(Since min 1 1,ttr = 0 only when ri E (rihm)
2 (L1 InE(s))) tc).
where 1 the indicator function, and ra = TMAX TMIN. We can see that this bound is similar to that of Theorem[]] Ti) but weaker. This because:
(i) The first term of this bound (Lr requires that reward function of the current task (r) be identical to that of reference task (rz). In Barreto al. 20188. r; is taken the best linear approximation of r. In contrast, the first term of Theorem I (ITşTy> only requires the current task to be expressible
Boolean composition of past tasks.
(ii) The second term of this bound (1::((r;): requires that the reference task (the best linear approximation to the current task) is exactly one the past tasks. In contrast, the second term of Theorem Ti) (Irg(r only requires the current task to have single desirable goal.
This suggests that we can can think of the logical composition approach an efficient way of doing GPI, one which leads to tight performance bounds on the transferred policy (Theorem Ii)).
A.5 PROOFS FOR THEOREM
Theorem 2. Let D be unknown distribution, possibly non-stationary. over of tasks M(S,A, for all M in M. Let
Let a M + Q* be any map from M to Q" such that (M) = Q
T4L. δ = SOPGOL(d Me, T., ②7) where Me D(t) and To = -0==00 = V.
Then,
[log |9] < lim N₂ < [g] where N₂ = | Ot
t-100
Proof. Let T. be the approximate binary representation of task M, learned by SOPGOL. We first note that SOPGOL returns T, U (T:} only if f, is not in the span of Í. That is,
= U (T.) iff T, + (TxP(T)) where BEXP = SOP T.).
Hence, it is sufficient to show that the number, N, of linearly independent binary vectors, Í e (o, 1 1ه1و,, that span the Boolean vector space (Subrahmanyam 1964). GF(2) is bounded by
[log |6| < N < (g).
This follows from the fact that [o is the size of a minimal set of generators for GF 9 (as easily be with Boolean table), and |g] is its dimensionality.
*GF(2) is the Galois field with elements, (f0, 1), +y),, where + XOR and AND.
18

---

Published as a conference paper at ICLR 2022
B SUM OF PRODUCTS WITH GOAL ORIENTED LEARNING
Algorithm shows the full pseudo-code for SOPGOL. Here, SOP(T, 7) is the classical sum
of products method in Boolean logic. Given a list of binary vectors T = [Ti,... Tal. a Boolean expression for new binary vector T is obtained as follows:
1. Identify all rows of T with 1.
2. For each such row: Make product (conjunction) of all the input variables and make the negation of each variable with this row.
3. Take the sum (disjunction) of all these product terms.
The output of SOP a function BEXP that takes in [ variables, and applies disjunctions, con- junctions and negations to them according to the Boolean expression obtained above.
Algorithm 1: SOPGOL
Input: ooflpooiyy RL algorithm o
e.g DON +/
task MDP M,
set of e-optimal task binary representations T,
set of c-optimal Q-value functions Q
Initialise T' G + {0, 1}
Initialise Q S x G x A according to s
Initialise goal buffer & with terminal states observed from random policy
while Q is not converged do Initialise state from M BEXP- + SOP((,T)
TsoP, Qsor (
QSOP if Tsop else Q QSOP
max (n,,Q(ss aEA
g arg max
9'Eğ
while is not terminal do Select action a using the behaviour policy from s:: a /+ e.g c-greedy
/
Take action a, observe reward r and next state s' M
if T + Tsop then
foreach g' 9 do
TMIN if g' + & e
Update Q with (s,g', g' a, F, s') according to a
end if is terminal then
T(s) < 1,=nxx
else
s s' end
end end
BEXP + SOP(T,T)
-, (T, ②) i BEXP(T) else (TU(T), (
return 7.
19

---

Published as a conference paper at ICLR 2022
C FOUR ROOMS ENVIRONMENT
We use the Four Rooms domain (Sutton et al. 1999), where an agent must navigate grid world to particular locations. The goal locations are placed along the sides of the walls and at the centre of rooms (Figure This gives goal space of size [ 40 and task space of size [M] = 2 = 10 The agent can move in any of the four cardinal directions at each timestep, but colliding with a wall leaves the agent the same location. We add 5th action for "stay" that the agent chooses to achieve goals. A goal location only becomes terminal if the agent chooses to stay in it. All rewards are at non-terminal states, and at the desirable goals. The transition dynamics are stochastic with a slip probability (sp 0.1). That is, with probability 1-sp the agent moves in the direction chooses, and with probability sp moves one of the other three chosen uniformly random.
Figure 5: 40 goals Four Rooms domain with goals in green and the agent in red.
20

---

Published as a conference paper at ICLR 2022
D FUNCTION APPROXIMATION EXPERIMENT DETAILS
D.1 ENVIRONMENT
The PICKUPOBJ environment is fully observable, where each state observation is 56 56 3 RGB image (Figure 1). The agent has 7 actions it can take in this environment corresponding to: rotate left, 2 rotate right, 3 move one step forward there no wall or object in front, 4 pickup object if there is object in front and object has been picked, 5 drop the object in front if an object has been picked and there is no wall or object front, open the door in front there a closed-door in front, and 7 close the door in front if there is an opened door in front.
For each task, each episode starts with desirable object and 4 other randomly chosen objects placed randomly in the environment. The agent is also placed random position with random orientation at the start of each episode. The agent receives a reward of -0.1 at every timestep, and a reward of 2 when it picks up desirable object. The environment transitions to terminal state once the agent picks up any object and the agent observes the picked object. There are 15 types of objects (illustrated in Table resulting in 15 possible goal states. Hence, the dimension of the state space is |S| 56 x 56 x 3, the goal space is [ 15, and the action space is |A| 7.
D.2 NETWORK ARCHITECTURE AND HYPERPARAMETERS
our function approximation experiments, we represent each extended value function Q with a list of [ DQNs, such that the value function for each goal (7 a) = Q- (s, g. is approximated with a separate DQN. The DQNs used have the following architecture, with the CNN part being identical to that used by Mnih et al. (2015):
1. Three convolutional layers:
(a) Layer has 3 input channels, 32 output channels, kernel size of 8 and a stride of 4.
(b) Layer has 32 input channels, 64 output channels, kernel size of 4 and stride of 2.
(c) Layer has 64 input channels, 64 output channels, kernel size of and stride of 1.
2. Two fully-connected linear layers:
(a) Layer has input size 3136 and output size 512 and uses a ReLU activation function.
(b) Layer has input size 512 and output size 7 with no activation function.
We used the ADAM optimiser with batch size 256 and learning of 10-3, We started training after 1000 steps of random exploration and updated the target Q-network every 1000 steps. Finally, we used e-greedy exploration, annealing from 0.5 0.05 over 100000 timesteps.
Finally, we used the same DQN architecture and training hyperparameters for the baseline in all experiments.
21


Reviews:
[{"review_id": "yIqZ6Qt2Q9I", "reviewer": "Reviewer_td5N", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work is sound and can potentially shape future lifelong reinforcement learning (LRL) research.\nI'm a bit skeptical however about its applicability in any use cases. \n\n**Strengths:**\n- The introduced problem formulation is a good first step towards lifelong compositional RL agents.\n- the theoretical guarantees for SOGPOL are satisfying\n- the empirical study is well-aligned w/ the problem formulation and highlights the relevant regimes , i.e., 4.1 a)  vs 4.1 b) vs 4.2 \n\n**Weaknesses:**\n- The boolean task algebra is quite restrictive. I don't see many use cases for it. If the authors introduce a new problem setting, they should motivate it.\n- assuming the agent can interact with the task as long as it needs is quite an unrealistic assumption in LRL.\n- all experiments on toy tasks. I think a more realistic benchmark should be introduced. \n- there's no LRL baselines.\n- in SOGPOL,\n    - the new skill is initialize randomly. This will be pretty inefficient is more realistic settings.\n    - IIUC, when learning, to enable transfer from previous tasks, goals need to be reached. But in realistic settings, goals will be hard to reach. So essentially lots time and compute will be wasted relearning over and over same things.\n\n**Minor details:**\n- def 3: $r_{MAX}$ is the same as $r_{MIN}$\n- theorem 1: what is $\\gamma$ ?\n- what's the difference between prop. 1 and prop. 2 ?\n- theorem 2: can you provide some intuition/explanation on those bounds?", "summary_of_the_paper": "This works introduces a lifelong RL problem in which new tasks can be possibly be expressed as a logical composition of previous ones.\n\nAccordingly, they introduce algorithm (SOPGOL) that can autonomously determine whether a new task can be immediately solved using its existing abilities, or whether a task-specific skill should be learned.\n\nThe authors provide some theoretical guarantees on the performance of the algorithm, as well as empirical evidence that it can work in a toy setting.", "summary_of_the_review": "I think this work as merits.\nI'm giving a weak reject because I would like to see more motivation for this work and how it could be adapted to use cases.\nI'm currently keeping my confidence score somewhat low because the theoretical contribution could be significant enough to alleviate the need for thorough motivations/experiments.\n\n======= POST REBUTTAL ==============\n\nThanks for all the explanations and clarification.\nSome of my concerns have been resolved.\nI'll increase my score to 6.\nI will not go higher because I still think some experiments should be added in a realistic lifelong RL benchmark, i.e., where the tasks won't actually obey the theoretical task algebra. Upon acceptance, I still encourage the authors to add such an experiment.\n\nMinor detail: please add the provided intuitions for Theorem 2 in the manuscript ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hIoa4-nBqfG", "reviewer": "Reviewer_AVki", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Goal-based tasks: I think this is an interesting subset of RL problems, and that it is great to study this class of problems.  However, not mentioning this limitation in the abstract (and not even in intro) seems very odd; ideally “goal-based” would be not only in the abstract and intro, but also in the title, since there is such a fundamental difference between looking at RL in general and at this subset of RL.  It was odd to read the title, abstract, and intro, and then have my expectations of what the paper was about completely disrupted in the third sentence of Section 2.\n\nSection 2 issues:\n\n- r_0 is neither formally defined nor intuitively explained (ideally it should have both a definition and an explanation), so its significance and the difference between it and r is unclear.\n\n- ”By penalising the agent for achieving…” are there typos in this sentence?  I cannot parse it.  Is \\mathcal G— a new symbol (with the additional “—”)?  What does “r_min&” mean in this context?\n\n- Definitions 1-2, extended reward function and extended Q-value function: I’m a little confused by what these are supposed to do.  Are we changing the problem/MDP, replacing the old reward function with the extended one?  Or are we changing the agent to utilize these concepts, while the problem remains the same?  Ideally, the text before/after these definitions would better explain the purpose of the definitions, avoiding this potential reader confusion.\n\n- “the extended reward function has the effect of driving the agent to learn how to\nseparately achieve all desirable goals.” This is confusing to me; it seems like this may have the effect of driving the agent to learn how to achieve only some of the goals (perhaps only one), not all the goals.  (I suspect the confusion is due to one of the issues above, and will be cleared up by fixing and clarifying one of those issues.)\n\n- Definition 3: since r_0 and r_[some task] have not been defined, I cannot parse definition 3.\n\n- Because of the cumulative effect of the Section 2 issues above (particularly the notation issues), I am not able to give constructive feedback on the theoretical contributions of Section 3.  I found Section 3 difficult to follow, but could not determine if the problem was Section 3, or some of my confusions with Section 2.  While Section 2 is only the background section, it establishes some notation and concepts that likely are not standard for many readers with an RL background.  Since Section 3 proceeds to build upon Section 2, I think that the issues with Section 2 will significantly harm the readability of Section 3 for many readers.\n\n[End Section 2 issues]\n\n4.1 experiments: The experiments used only 4 runs, which is concerning for any experimental claims.  The claim is that SOPGOL is exhibiting transfer learning (4.1), and the evidence is that SOPGOL starts with much stronger performance than the baseline.  However, 4 runs is simply not a sufficient amount of data to make this claim.  I would encourage the authors to take the time to run 30+ runs in the future to make this claim more substantial.  Statistical significance testing would also be nice, but, if something like a t-test is used, much more data is needed anyway, since the t-test normality assumption is not reasonable with 4 runs (but might be reasonable with 30+, because of the CLT).\n\nMinor Figure 4 formatting issue: I was thrown off by the lack of spacing between the two subfigures’ captions, and for a couple minutes was trying to understand it as a single paragraph starting as: “(a) Number of policies required to learn and store (b) Number of samples required…”.  The correct way of reading it, as two separate paragraphs side-by-side, is obvious once one sees it, but the way the paragraphs are set so close together makes me think that other readers may get confused as well.  (Also, the first lines of the two paragraphs are unfortunate in that they almost make sense when read in the wrong way; the wrong way of reading it only turns into obvious nonsense in the second or third lines.)  I suggest adding a bit of horizontal spacing between the sub-captions to help avoid this issue (if negative horizontal space was used here, please do not do that).\n\nMinor notation edits:\n\n- inconsistency in MDP tuple ordering (sometimes discount parameter is last, other times reward function is last).\n\n- In theorem 1, T_SOP and \\bar Q_SOP definitions use the equals symbol, should they use \\coloneqq instead?\n\n**Update after rebuttal:**\n\n> We think of transfer along these lines of works [1,2,3]. For example, if an agent can learn to “pickup yellow objects”, then we would like it to transfer this knowledge to “pickup yellow keys” or even “pickup keys that are not yellow”. We are curious as to the kinds of tasks that you believe we should cover.\n\nI’m not suggesting changing the tasks at all, but merely suggesting that the fact that the paper exclusively studies goal-based tasks be mentioned earlier (which you already said you would do, so no need to discuss this further).\n\nOr am I misunderstanding?  Is the reasoning that most or all of transfer learning in RL can be framed as goal based tasks?  If so, it’s not so much a limitation that necessarily needs to be mentioned earlier; instead, in that case, I think the fix is to explain that most/all of transfer learning can be framed as goal-based tasks in the first paragraph of Section 2.\n\n> Definitions 1-2...We will make that clearer in the paper\n\nGreat, thank you.\n\nPoint 3 of rebuttal: The revised version is much more clear, thank you.\n\nMore Definition 3 feedback: I still struggled with Definition 3 despite the clarifications above.  Was a “task” ever formally defined?  (See my clarity concerns below, the setting is still not clear to me.)  I was also confused about how a task could be “bounded”.\n\nTwo more points regarding lack of clarity in the setting:\n\n1) > During each episode, the agent samples a goal to reach from its goal buffer. If it successfully reaches that goal, then the extended reward it receives is just the regular task reward from the environment. If it reaches a different terminal goal state, then the extended reward it receives is the large penalty. Hence the agent only gets the high task rewards when it reaches the goal it is trying to reach. This drives it to learn to achieve all the goals it encounters. Please see Fig 4 of Tasse et al. if that helps.\n\nIt’s not clear from the paper that each episode has the agent sampling a new goal for the task.  It becomes slightly more clear in Section 3 (but still isn’t completely clear then), but I think a big source of ambiguity and confusion in Section 2 is that this is not explained well.  More generally, the explanation of the relationships between goals, tasks, episodes, and the distribution of tasks needs work to improve clarity.\n\n2)  3.1, task space size being 2^|G|: it’s not clear to me exactly where this is coming from.  Is it because each goal can be either r_min or r_max for a given task?  More clarity in section 2 would probably help avoid this confusion.\n\nSummary of update:  Some concerns have been addressed (particularly the promised change in phrasing weakening the claims regarding the empirical results in 4.1), and I am increasing my score slightly, but clarity is still a major concern for me.  Because I am not understanding the setting and theory well, my confidence in my assessment is low, and I recommend disregarding my assessment if the other reviewers' clarity concerns are addressed.\n", "summary_of_the_paper": "The authors study goal-based lifelong RL.  They leverage logical composition to create an algorithm for this setting, with the goal of better generalization.  They provide theoretical bounds for their approach, and provide empirical evidence that their approach generalizes and transfers well in practice.", "summary_of_the_review": "This paper is fascinating and well-motivated.  However, a few notation and clarity issues made it difficult to follow Sections 2-3, and I am also concerned about the statistical significance of the authors’ claims in 4.1.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "c1M_mRS4b7", "reviewer": "Reviewer_KyZj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n* This work extends the previous results of (Nangue Tasse et al. 2020) to handle stochastic transitions.\n* The topic area is relevant for ICLR.\n* Lifelong learning is an important and challenging topic and this work proposes a compelling path toward addressing that challenge through a combination of reinforcement learning and logical composition.\n* Overall the paper is well-organized and does not have too many typos, although see my notes below.\n* The theoretical results may be of interest, although I had difficulty understanding some of the main statements, which hopefully I can clear up during the rebuttal period.\n\n## Weaknesses\n\n* The paper is overall difficult to follow and the notation is not always clear.\n* I had a lot of trouble parsing the statement of Theorem 1. \n   * SOP(., .) is not defined, where the first argument is a set of binary vectors and the second argument is a single binary vector. The result of SOP is B_exp, which is then applied to \\tilde{T}_n as if B_exp were a function (and similarly for Q)? I think I ultimately understand this part, but the notation seems abused to the point where it’s difficult to follow.\n   * \\tilde{T} (the approximation of T, presumably) is not defined within the scope of this theorem -- is it meant to appear in that line or not? I suspect that it was meant to be T, because the theorem does not have any assumptions about the accuracy of \\tilde{T} as an approximation of T, and I’m sure that some assumptions would be required to draw any conclusions.\n   * In (i), what is the meaning of $1_{T \\not\\in \\tilde{T}_n}$? $T$ is a specification and $\\tilde{T}_n$ is a set of specifications, so that subscript would either be true or false. But from context, this object must be a binary vector. What is it exactly?\n   * Since I remain confused about the Theorem 1 formal statement, for now, I am trusting the written descriptions surrounding it.\n* I also have some confusions surrounding Theorem 2:\n   * Why are the cardinalities all that we care about? Is there an implication that a task and Q function are only included in those sets if they have been “mastered” with a certain level of accuracy?\n   * How can we draw any conclusions when we have an arbitrary nonstationary distribution of tasks? What prevents a pathological example where we see the same task for the first T steps and then a different one on step T+1, for any T?\n* As a delta on the previous work of (Nangue Tasse et al. 2020), I am not sure if this work constitutes a substantial enough standalone contribution for an ICLR paper. There are advances to be sure, but they are relatively incremental. If I am able to get a better understanding of the theorems, that may change my perspective.\n* The experiments are good to illustrate the main ideas, but they are not a substantial standalone contribution, since the domains are very simple and the baseline comparisons are very limited.\n* I was surprised by the new definition of Q-function negation in section 3.2 because the value of the Q-function before negation is not used, except when determining whether the output should “toggle” between Qmax or Qmin. Can you explain this?\n* I would like to see a discussion of the relationship between this line of work and propositional AI planning. The composition of goals is very related. It will be easy to find differences, and I think this line of work may offer a different and valuable perspective. I just think that the work would be strengthened by deeply exploring these connections.\n* The premise of the transfer results in this work is that the task specification for a given task is not known, and so we have to compute and use an approximation of it. I am having trouble imagining a scenario where this structured space of possible task specifications is known, but the specification for a given task is not known. Is the idea that for a given task, there may actually be no “true” task specification, and so the approximation is just the “closest” specification that we can find? That would be more compelling, but I don’t think that we can use this interpretation because it would require leaving the class of MDPs defined in this work, and including MDPs that do not necessarily have the good-goal/bad-goal structure with the fixed r0 reward function.\n* This comment is about boolean task algebra for RL in general, not just the present work. Though the theoretical contributions here may be interesting in their own right, I am struggling to imagine a practical scenario where it would be preferable to use this framework instead of one where we learn or compute a universal goal-conditioned value function instead. To elaborate, here is my attempt to describe this line of work through the lens of universal goal-conditioned value function learning:\n   * Say that we compute/learn a universal goal-conditioned Q function $Q(s, g, a)$. Given any goal state $g$, we can do $argmax_{a} Q(s, g, a)$ to get optimal actions.\n   * This line of work says: instead of learning a single goal-conditioned Q function, we could compute/learn multiple goal-conditioned Q functions, one per “task”, where a task is a set of goal states. Each of these Q functions is like an “expert” about some part of the goal space.\n   * When given a new task $\\mathcal{G}$, if we had a universal $Q$, then we could recover an optimal action via $argmax_{a} \\max_{g \\in \\mathcal{G}} Q(s, g, a)$. This would be “zero-shot” transfer in the sense of this paper.\n   * But instead, if we only have the goal-space expert Q functions, we will query the experts for whom $\\mathcal{G}$ is within their expertise and combine their outputs according to the relationships between $\\mathcal{G}$ and the expertises. This too will accomplish “zero-shot” transfer. But what is gained over the universal approach?\n* Related to the previous point, the super-exponential zero-shot generalization advertised in this work and the previous work strikes me as a little bit disingenuous. If I am able to do X, and I’m also able to do Y, then I am automatically also able to do “X or Y”. Is that really generalization? Fundamentally, that is my reading on what’s happening in this work -- we’re learning how to accomplish each of the goals (indirectly, through the tasks, which are sets of goals), and then we’re recombining them in different ways, so that if we know how to achieve goal 1 and goal 2, we also know how to achieve “goal 1 or goal 2.”\n\n\n## Minor Points\n\n* In the first sentence of the paragraph before Definition 3, is that & meant to be there? I think there may be a formatting error.\n* I know that the notation $g \\neq s \\in \\mathcal{G}$ is not original to this work, but it is confusing and should be changed. For example, two different ways to parse this: $\\forall s \\in \\mathcal{G}. g \\neq s$; or $\\exists s \\in \\mathcal{G}. g \\neq s$. Furthermore, $\\mathcal{G} \\subseteq \\mathcal{S}$, so can’t we just say $g \\not\\in \\mathcal{G}$?\n* It would be useful to define SOP explicitly even if it’s simple.\n* When first defining the approximate task specification $\\widetilde{T}$, it would be helpful to say whether that object is also a binary vector, like $T$, or if it instead could have non-binary values. Since it’s an approximation and there is some uncertainty about the true specification, the latter is plausible.", "summary_of_the_paper": "This paper considers lifelong reinforcement learning. It extends a line of recent work in which logical composition is combined with goal-based reinforcement learning to achieve generalization to new tasks. The main contribution is theoretical, extending prior work to handle stochastic transitions and establishing asymptotic results for the lifelong learning setting. Experiments in grid-based domains illustrate SOPGOL, the main proposed algorithm, and show that it is possible to immediately generalize to new tasks in the lifelong setting.", "summary_of_the_review": "For the reasons described above, especially concerning clarity and novelty, I am recommending a weak reject at this stage. However, after getting a better understanding of the theoretical contributions, I may be willing to raise my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IcwCuGAVTB1", "reviewer": "Reviewer_ovqB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives:\n\n- The idea of using logical composition to autonomously determine whether a given task can be immediately solved using existing policies or whether a new policy has to be learned and added to the policy library is interesting.\n\n- Overall, the paper is well-written and it is easy to follow (if typos are not taken into account).\n\n- It is nice to see that the paper contains theoretical results that provide bounds (i) on the performance of transferred policy on a new task and (ii) on the necessary and sufficient number of tasks that need to be learned by the agent so that it can generalize over a distribution. The proofs of the theorems also seem sound.\n\n- The experiments section of the paper provides comprehensive results, including results on transfer after pretraining on a set of tasks (both base and arbitrary) and on lifelong transfer scenarios where the agent builds the skill set from scratch, verifying the theoretical results. Using three different task distributions in the lifelong RL setting is also a nice way to show how the algorithm would perform in best-case, worst-case and average-case scenarios.\n\n\nConcerns:\n\n1.  On the proposed framework:\n\n\ta.  One of my biggest concerns about this paper is the lack of explanation of where the extended reward (and value) functions come from in Defn. 6 (and Defn. 7). If it is going to be computed by the agent, then it requires the knowledge of the reward model ($r(s,a)$ and $r_{MIN}$) and goals $g\\in\\mathcal{G}$ which are supposed to not be known by the agent apriori (and may never be known if the environment is large). If it is assumed to be known in advance by the agent or if the considered environments are assumed to have an extended reward function themselves (as the experiments suggest), then I believe that it is an important assumption that should perhaps be made more clear. Afterall, regular environments are not likely to have this kind of a reward function. I am curious about a discussion on this.\n    \n\tb.  It would also be nice if the paper can discuss any additional limitations of the proposed framework as there seems to be no discussion on this throughout the paper.\n    \n\tc.  In Sec. 3.2, it is unclear how the negation operator for a task is defined? Could the authors clarify?\n    \n\td.  Also the motivation behind redefining the negation operator for the extended value function seems to be unclear. Is this just for obtaining better bounds as stated in the paper?\n    \n\n2.  Regarding the experiments:\n\n\ta.  Another big concern of mine is that although the experiments support the claims of the paper, I find them to be on very limited settings of the proposed domains. For instance, in the PickOpObj domain, the agent is always in a world with only 5 objects and after it picks one, the episode immediately terminates. What about cases where, for instance, the agent is surrounded by all of the 15 objects (in a larger environment) and it has to pick up all the objects associated with a 1 in the vector $T$? In this case, for the test task $T_2$, the agent would have to sequentially pick up all the 7 objects (as there are 7 1’s in $T_2$) and then terminate the episode. The same argument can be made for the Fourrooms domain as well, where the agent would be required to pass through the locations that have 1’s in the corresponding $T$ vector. Thus, I suggest for performing the same experiments in the paper in settings where the tasks don’t terminate after just picking/reaching an object/location, but continues until all the objects/locations are picked/reached (see e.g. the tasks in [1]). I think that these additional experiments would strengthen the results by showing that the proposed framework applies to a broad range of settings.\n    \n\tb.  On the same note, in my understanding, it looks as if the definition of goal-based tasks is too restrictive. For example, if there are only two yellow keys in the environment and the task is to obtain yellow keys, is the goal defined as obtaining both of the keys and then terminating or obtaining the closest one and then terminating? The experiments seem to indicate that the latter is meant by goal-based tasks. Could the authors clarify on this point and give examples.\n    \n\tc.  Also, although the paper states that there have been earlier work (Saxe et al., 2017; Haarnoja et al., 2018; Van Niekerk et al., 2019; Hunt et al., 2019; Peng et al., 2019) on skill composition, there seems to be no discussion on why there is no comparison with them. If these methods are not applicable in the settings considered, or if comparison with them does not make sense, then I believe that this should explicitly be mentioned (together with the reasons) in the paper. A discussion on this would be great.\n    \n\n3.  Regarding related work:\n\n\ta.  Although the paper briefly talks about the GPE & GPI framework [1] in the related work section, I think there should be an extended discussion on the difference/similarities between this framework and the Boolean algebra framework developed in the paper as the two seem to be very related. For instance, by selecting the appropriate task vectors $\\mathbf{w}$, one can also build a skill set that enables generalization across a distribution of tasks. In fact, this seems to have been demonstrated by a concurrent study [2].\n    \n\tb.  Another closely related study on skill composition is the Option Keyboard framework [3]. It would also be nice to see a discussion on the differences/similarities of this framework and the proposed one.\n    \n\tc.  I believe that providing a detailed discussion on the difference between the prior studies in 2c and the proposed method in the related work section can further clarify how the proposed method fits in the literature.\n\n\nMinor comments (that have no effect on the final decision):\n\n- Adding a newline (`\\\\`) to the title can make the spacing look better.\n    \n- There is a typo in the first paragraph of page 3 where “&” is used right after $\\bar{r}_{MIN}$.\n    \n- In Defn. 3, I think there should be a $\\min$ in the definition of $r_{M_{MIN}}$.\n    \n- In the first paragraph of Sec. 3.1, it should be “learned” instead of “said”. Also, in Defn. 5, does the agent sample a task or is a task provided by the environment? According to the experiments, the tasks seem to be coming from the environment.\n    \n- In the second paragraph of Sec. 4.1, it should be “RL method” instead of “RL learning method”.\n    \n- In Sec. 4.2, what is the value for the slip probability ($sp$)? It is not provided in any part of the paper.\n    \n- Maybe a really minor detail, but the fonts of the plots in Figure 2, 3 and 4 do not seem to match.\n    \n- In the last paragraph of Sec. 4.2, it should be $\\mathcal{D}_{best}$  instead of  $\\mathcal{D}_{sampled}$.\n\n- What is EVF in Prop. 1 and Prop. 2? It should be written explicitly in its non-abbreviated form.\n    \n- In Sec. 2, is the virtual state a terminal state? If it is, I believe that naming it as so can avoid any possible confusion.\n    \n- In the second paragraph of Sec. 3.4, what does “... goal buffer according to $\\mathcal{A}$.” mean? I think this should be clarified.\n    \n- Are policies assumed to be deterministic throughout the paper? If so, this should be stated explicitly.\n    \n- In Defn. 5, what does it mean to be “$\\epsilon$-optimal” in task M? This should be defined explicitly.\n    \n- It seems like the $\\mathcal{M}$’s in Sec. 2.1 do not correspond to the $\\mathcal{M}$ in Eq. (1), as Sec. 2.1 assumes the undiscounted setting? If this is the case, I believe that the set of tasks in Sec. 2.1 should be named differently.\n    \n- In Defn. 5, does it matter whether $\\mathcal{D}$ is a stationary or non-stationary distribution? (This is also assumed in Theorem 2 in Sec. 3.4) It does not seem to make any difference from the point of view of the proposed method. I believe that starting Defn. 5 as “Let D be an unknown distribution, possibly non-stationary, over a set of tasks …” would be more appropriate here.\n    \n- I believe that Eq. (1) is too general and it should be expressed more clearly. For instance, when $r_{MIN}$ and $r_{MAX}$ are both positive, all the states in $\\mathcal{S}$ become desirable states and there will be no undesirable ones. When $r_{MIN} < 0$ and $r_{MAX} > 0$, some states in $\\mathcal{S} \\setminus \\mathcal{G}$ may become desirable or undesirable states depending on $r_0(s,a)$. Having some restrictions on the possible values of $r_{MIN}$, $r_{MAX}$ and $r_0(s,a)$ can be helpful.\n\n\nReferences:\n\n[1] André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117 (48):30079–30087, 2020.\n\n[2] [https://openreview.net/forum?id=7IWGzQ6gZ1D](https://openreview.net/forum?id=7IWGzQ6gZ1D)\n\n[3] Andre Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygun, Philippe Hamel, Daniel Toyama, Jonathan Hunt, Shibl Mourad, David Silver, et al. The option keyboard: combining skills in reinforcement learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 13052–13062, 2019.\n", "summary_of_the_paper": "This paper provides an interesting direction in the field of skill composition in reinforcement learning (RL). In particular, by extending Tasse et al. (2020)’s framework for Boolean task algebra, which allows for composing tasks and value functions using logical operators to yield optimal skills zero-shot, from deterministic shortest path tasks to discounted stochastic tasks, the paper proposes a new framework for lifelong RL that focuses not only on transfer between tasks for faster RL, but also gives guarantees on the performance of the agent over an unknown task distribution. Along with the framework, two main theoretical results are provided: (1) bounds on the performance of transferred policy on a new task, and (2) bounds on the necessary and sufficient number of tasks that need to be learned to guarantee performance over a distribution of tasks. Experiments are performed to verify the theoretical results in both transfer learning and lifelong RL settings in the PickUpObj and Fourrooms domains in the minigrid environment.", "summary_of_the_review": "Overall, I think the paper can be a nice contribution to the field of lifelong RL, however, due to my concerns detailed above, I am currently voting for “marginally above the acceptance threshold”. Out of all my concerns 1a, 2a, 2b and 3a matters the most and I am willing to raise my score to accept if they are properly addressed. If, in addition, the authors can address the remaining points, this will increase the confidence in my voting to accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ElUlE3BGGXq", "reviewer": "Reviewer_BUDa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Good work on this paper. I appreciate the background session as I had forgotten lots of details from the boolean task algebra, since I read it. The papar is very sound and the concern about the number of skills is reassuring. Using GPI on the extended Q_SOP and extended Q~ is a useful trick and yields good results. Within the problem formulation, the empirical method works well enough.\n\nSome improvements can be made on the paper though:\n\n1. The following claim right before theorem 2 seems incorrect: \".We now show ... generalises over any unknown non-stationary task distribution after learning only a number of tasks logarithmic in the size of the task space\". My understanding is that theorem 2 is actually a lower bound on the number of goals needed to learn, and the upper bound is |G|, unless we make further assumptions, as you have shown already with D_worst in the experiments. The same applies to similar claims around the paper, for example, \"which are\nsub-logarithmic in the size of the task space\" (abstract), \n\n2. The background session 2.1. is missing the Lemma 1 from previous work which is crucial to building its intuition and recover the non-extended reward and value (i.e. just maximize over G to recover the non-extended quantities). Without it, readers unfamiliar with previous work may struggle to understand definition 3 onwards.\n\n3. I miss some discussion on the limitations of the method, specially in terms of using finite set of goals, which doesn't seem to be a strong requirement of the related work discussed. It's often not feasible to do that in some scenarios, so it can hinder the further applicability of this method, for example, some goals are defined as continuous regions of the state space.\n", "summary_of_the_paper": "This paper builds upon previous work on the Boolean Task Algebra For Reinforcement Learning extending it to the discounted and stochastic tasks and to the lifelong RL setup. The authors show that techniques introduce in the previous work can perform close to optimal in a zero-shot transfer scenario. Next, they look into the number of skills needed in order to solve all the tasks and arrive at some lower bounds which are encouraging since they are close to log|G|, this is somewhat supported by empirical analysis later on.\nThe authors also introduce a method for using the known skills with SOP to solve new tasks and to bootstrapping the learning of new skills if needed. Overall, the method is very quick to learn when compared to a simple Q-learning baseline. This work is orthogonal to lots of related ones in the skill learning literature and would combine well with many of them.", "summary_of_the_review": "This is a good paper with a sound method and good results. The author just need to work on a few points to award a clear acceptance.\nSome claims about the efficiency of the algorithm with the number of goals need to be removed. A important step of the background is missing. Finally, some short discussion about limitations would be welcome.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7PO4xbvZZ8S", "reviewer": "Reviewer_1zPe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n* The paper is generally well written and easy to follow, and explanations are intuitive.\n* The chosen research problem, lifelong and multi-task RL, is both important and insufficiently studied.\n* I really like the idea of having a task-composition logic. I think that this is an immensely interesting research direction.\n* I like the theoretical results, even though they are a little unsurprising.\n\n### Weaknesses\n* Some important details are missing from the main paper: the exact algorithm proposed, and the exact setup of the experiments.\n* The paper's experimental section is fairly weak in that all experiments are on the same, fairly simple task.\n* It is not clear if the experiments are \"fair\", i.e., if the algorithms play on an equal playing field.\n\n### Detailed questions/comments\n* While the paper is properly anonymized in theory, I looked up \"Nangue Tasse et al (2020)\". The fact that they use near-duplicate language strongly suggests the same authors (or a violation of attribution). Please re-write to avoid this suspicion.\n* Some notations are off or ambiguous (like in (2) - what does \"s \\neq s \\in G\" mean? Similarly in the theorems - why are there two inequalities combined with an equal sign?)\n* It is completely unclear to me how the algorithm interacts with the chosen DQN model in detail. In particular, this sentence baffles me and I suspect that a lot is going on behind the scenes: \"Having learned the \u000foptimal extended value functions for our base tasks, we can now leverage logical composition to do transfer learning on test tasks.\"\n* Is the task composition provided to the learners in some way, or do they have to trial-and-error the task composition?\n* From the look of the plots, a pure DQN may get competetive using sufficient samples? If so, please train with more data/longer. This would spin the paper more towards a data efficiency argument.", "summary_of_the_paper": "The paper introduces an approach of logical decomposition of tasks as a particular set of MDPs. This logical decomposition allows to define a boolean logic over tasks and q-functions. Using this boolean logic, the paper continues in proving two boundaries for generalizing to new, unencountered tasks. The first states a boundary on performance on a new task when following a composition of previously learned policies. The second states that, to solve problems composed of k atomic tasks optimally, at most k skills will ever be required. The paper continues define a lifelong learning algorithm that relies on this logic to form a set of base skills. This algorithm is then evaluated on a multi-task and lifelong learning task, where it decidedly outperforms a standard deep q-learner.", "summary_of_the_review": "The targeted problem - a lack of multi-task and lifelong learning capabilities of most RL algorithms - is an extremely important one, as it resembles real-life applications a lot more closely. Additionally, the idea of finding a decomposition of multiple tasks via boolean logic is highly appealing, as it allows structural abstraction in RL, another important but underexplored question. Unfortunately, the paper's contributions are a little underwhelming. The logical decomposition is nice but fairly straightforward. The theorems provide an interesting, but also not groundbreaking insight. And finally, the experiments are unclear in execution, only on one domain, and therefore unconvincing. Overall I really like the idea, but the paper needs substantial work to become a full contribution.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors for their submission and active participation in the discussions. This papers is borderline. On the positive side, reviewers emphasized this is a well written [ovqB,1zPe] and sound paper [BUDa] with good theoretical [td5N,ovqB,1zPe] and empirical [BUDa,td5N,ovqB] results. On the negative side, reviewers remarked clarity [KyZj,AVki], incremental with respect to Tasse et al (2020) [KyZj], relatively restricted Boolean task algebra [td5N], toyish nature of the environments considered [ovqB], and some missing details [1zPe]. During discussion, the sentiment seems to be somewhat lukewarm with none of the reviewers strongly favoring acceptance or rejection. It seems the main remaining concern is around the toyish nature of the environments used in this paper. I acknowledge that and I believe the authors could include experiments on more complex environments. However, I also give the authors credit for addressing most of the reviewer's concerns during rebuttal and for presenting a solid empirical and theoretical result that the research community can build upon in the future. I am therefore recommending acceptance of this paper and highly encourage the authors to further improve their paper based on the reviewer feedback.
Decision: Accept (Poster)