Constructing a Good Behavior Basis for Transfer using Generalized Policy Updates
Authors: Safa Alver
Doina Precup
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning
lifelong learning
transfer learning
successor features

Abstract: We study the problem of learning a good set of policies, so that when combined together, they can solve a wide variety of unseen reinforcement learning tasks with no or very little new data. Specifically, we consider the framework of generalized policy evaluation and improvement, in which the rewards for all tasks of interest are assumed to be expressible as a linear combination of a fixed set of features. We show theoretically that, under certain assumptions, having access to a specific set of diverse policies, which we call a set of independent policies, can allow for instantaneously achieving high-level performance on all possible downstream tasks which are typically more complex than the ones on which the agent was trained. Based on this theoretical analysis, we propose a simple algorithm that iteratively constructs this set of policies. In addition to empirically validating our theoretical results, we compare our approach with recently proposed diverse policy set construction methods and show that, while others fail, our approach is able to build a behavior basis that enables instantaneous transfer to all possible downstream tasks. We also show empirically that having access to a set of independent policies can better bootstrap the learning process on downstream tasks where the new reward function cannot be described as a linear combination of the features. Finally, we demonstrate how this policy set can be useful in a lifelong reinforcement learning setting.

Published as a conference paper at ICLR 2022
CONSTRUCTING A GOOD BEHAVIOR BASIS FOR TRANSFER USING GENERALIZED POLICY UPDATES
Safa Alver Mila, McGill University sa fa lveermaill m.meii ca
Doina Precup
Mila, McGill University and DeepMind mcgi
dprecupêcs .ma.pppecs..c.ic........ 11.ca
ABSTRACT
We study the problem of learning good set of policies, so that when combined together, they can solve a wide variety of unseen reinforcement learning tasks with no or very little new data. Specifically, we consider the framework of gen- eralized policy evaluation and improvement, in which the rewards for all tasks of interest are assumed to be expressible as a linear combination of a fixed set of features. We show theoretically that, under certain assumptions, having access to specific set of diverse policies, which call set of independent policies, allow for instantaneously achieving high-level performance on all possible down- stream tasks which are typically more complex than the ones which the agent was trained. Based on this theoretical analysis, we propose a simple algorithm that iteratively constructs this of policies. In addition empirically validating our theoretical results, we compare our approach with recently proposed diverse policy set construction methods and show that, while others fail, our approach is able to build behavior basis that enables instantaneous transfer to all possible downstream tasks. We also show empirically that having access to a set of in- dependent policies can better bootstrap the learning process downstream tasks where the new reward function cannot be described as a linear combination of the features. Finally, we demonstrate how this policy set can be useful in a lifelong reinforcement learning setting.
INTRODUCTION
Reinforcement learning (RL) studies the problem of building rational decision-making agents that maximize long term cumulative reward through trial-and-error interaction with given environment. In recent years, RL algorithms combined with powerful function approximators such deep neural networks have achieved significant successes in a wide range of challenging domains (see e.g. MMih et al. 22015; ; Vinyals al. (2019) Silver et al. (2017 2018)). However, these algorithms require substantial amounts of data for performing very narrowly-defined tasks. In addition to being data- hungry, they also very brittle changes in the environment, such changes in the tasks time. The most important reasons behind these two shortcomings is that RI. algorithms usually learn perform task from scratch, without leveraging any form of prior knowledge, and they are trained to optimize performance on only a single task.
A promising approach to tackle both of these shortcomings is learn multiple ways of behaving. i.e, multiple policies that optimize different reward functions, and to reuse them as needed. Having access to multiple pre-learned policies can allow an agent to quickly solve reoccurring tasks lifelong RL setting. It can also allow for learning to combine the existing policies via meta-police to quickly learn new tasks, as in hierarchical RI. Recently, Barreto al. (2020) have proposed the "generalized policy updates" framework, which generalizes the classical policy evaluation and pol- icy improvement operations that underlie many of today's 's RL algorithms. Its goal is to allow reusing policies resulting from previously learned tasks in order to perform well on downstream tasks, while also being data-efficient. More precisely, after learning the successor features of several policies in policy set, also referred to as a behavior basis, they were able to instantaneously "synthesize", in a zero-shot manner, new policies to solve downstream tasks, via generalized policy improvement. However, this work leaves open two important questions: (i) what set of policies should the agent

---

Published as a conference paper at ICLR 2022
learn that its instantaneous performance all possible downstream tasks is guaranteed to be good, and (ii) under what conditions does such a set policies exist.
In this paper, we provide answers to the questions above by proving that under certain assumptions about the environment dynamics and features, learning a diverse set of policies, which we call set of independent policies, indeed guarantees good instantaneous performance tasks. After providing an iterative algorithm for the construction of this set, we perform several experiments that validate our theoretical findings. In addition the validation experiments, we compare this algorithm with recently proposed diverse policy set construction methods (Eysenbach al., 2018: Zahavy et al., 2020 (02I) and show that, unlike these methods, our approach is able to construct a behavior basis that enables instantaneous transfer to all possible tasks. We also show empirically that learning a set of independent policies can better bootstrap the learning process on downstream tasks where the reward function cannot be described by a linear combination of the features. Finally, we demonstrate the usefulness of this set in a lifelong RL scenario, in which the agent faces different tasks over its lifetime. We hope that our study will bring the community step closer to building lifelong RL agents that are able to perform multiple tasks and are able to instantaneouusly/uuickky adapt to ones during its lifetime.
all possible downstream
2 BACKGROUND
Reinforcement Learning. In RL (Sutton & Barto 2018). an agent interacts with its environment by choosing actions to get as much as cumulative long-term reward. The interaction between the agent and its environment is usually modeled Markov Decision Process (MDP). An MDP is tuple M = (S, A, P. r. do, 7), where S the (finite) set of states, A is the (finite) set of actions, P: x A x S > jo. 1] is the transition distribution, r S x A S -+ IR is the reward function, which specifies the task of interest, do S - [0, is the initial state distribution and y E 10, the discount factor. In RL, typically the agent does not have any knowledge about and beforehand, and its goal is to find, through pure interaction, a policy : S + A that maximizes the expected sum of discounted rewards Ex. frS,, As, Set1) Su do]. where Ex denotes the expectation over trajectories induced by π and P.
Successor Features. The successor representation for state s under policy ' allows s to be represented by the (discounted) distribution of states encountered when following æ from (Dayan 1993]. Given policy, successor features (SF, |Barreto et al.) (017) are a generalization of the idea of successor representations from the tabular setting to function approximation. Following Barreto ct al. 2017), we define SI's of a policy æ for state-action (8, a) as:
2" (s, = ET.P Σ
(S Arti S(4111) S A. =a
where the ith component of o gives the expected discounted sum of the ith component of the feature vector, oú when following policy æ, starting from the state-action pair as,
Successor features allow decoupling between the reward function and the environment dynamics. More concretely, if the reward function for a task can be represented as a linear combination of a feature vector @f a, s') R":
(w a s') = ((s, a, W,
where E R",, then, as we will detail below, the sattencction value function Q can be computed immediately as the dro-product of eh and w. The elements of w, w;, can be viewed as indicating a "preference" towards each of the features. Thus, we refer to w interchangeably as either the preference vector or the task. Intuitively, the elements de of the feature vector & can be viewed as salient events that maybe desirable or undesirable to the agent, such as picking up or leaving objects of certain type, and reaching and/or avoiding certain states.
Generalized Policy Evaluation and Improvement. Generalized Policy Evaluation (GPE) and Generalized Policy Improvement (GPD), together referred to as Generalized Policy Updates, are generalizations of the well- policy evaluation and policy improvement operations in standard dynamic programming to a set of tasks and a set of policies (Barreto et al., 2020). They are used as transfer mechanism in RL quickly construct solution for newly given task. One particularly
2

---

Published as a conference paper at ICLR 2022
efficient instantiation of GPE & GPI is through the use of SFs and value- action selection. More concretely, given a set of MDPs having the following form:
M₂ = {(S,A, P. = Φ w, do, 7) w E IR"),
(3)
and given SFs * (s, a) of a policy n, an efficient form of GPE on the task Fw for policy a can be performed as follows:
Φ (" a)
O (s,
(4)
where O (s, a) is the state-action value function of π on the task Tw- And, after performing GPE for all the policies in a finite policy set II, following Baarreto et al. (2017). an efficient form of GPI can be performed as follows:
GPI III (s) E arg max max Q (s, a). a FEll
(5)
We will refer to this specific use of SFs and value-based action selection for performing GPE & GPI as simply GPE & GPI throughout the rest of this study. Note that GG will in general outperform all the policies in II, and that the actions selected by GPI on state may not coincide with any of the actions selected by æ E on that state. Hence, the policy space that can attained by GPI can in principle be a lot larger than, c.g., the space accessible by calling policies sequentially from the original set.
PROBLEM FORMULATION AND THEORETICAL ANALYSIS
GPE & GPI provide a guarantee that, for any reward function linear in the features, 7GPI is at least as good as any of the policies π from the "base set" which was used to construct it. While this is an appealing guarantee of monotonic improvement, it does not say much, for two reasons. First, it is not clear how big improvement can be expected for different tasks. More importantly, leaves open the question of how one should choose base policies in order to ensure as much improvement as possible. After all, if we had weak set of policies and we simply matched their value with π GPI, this may not be very useful. We will now show that, under certain assumptions, having access specific set of diverse policies, which call set of independent policies, can allow for instantancously achieving high-level performance on all possible downstream tasks.
Let us start by assuming that we are interested in set of MDPs MA. as defined in (3), with deter- ministic transition functions (the reason for the determinism assumption will become clear by the end of this section). For convenience, we also restrict the possible values from R" to W, where W is the surface of the l n-dimensional ball. Note that this choice does not alter the optimal poli- cies of the MDPs Ma. as an optimal policy is invariant with respect to the scale of the reward and W contains all possible directions. Next, we assume that the features &; that make up the feature vectors & form set of independent features (SIF), defined as follows:
(.C),CEE4)) is called independent if. for any feature o; E 4 and any initial state ~ do we have: (i) ói(so, Go 31) 0 Vao E and Vs P(so, 0o."). and (ii) there exists least one trajectory, starting from so, in which all the states associated with di (8,, a,, S1+1) = C are visited, while the states associated with 65(st, ae. S141) = C, Vj + i, are not visited.
Definition 1 (SIF). A set of features t { Φb; S x A
It should be noted that a specific instantiation of this definition is the case where each feature is set to a positive constant at certain independently reachable state/states and zero elsewhere, which is the most common instantiation of feature vectors used in previous related work (Barreto et al. 2017 2020).
We define the performance of an arbitrary policy π task Tw as:
J = Eg Σ (Sr, Ar, So ~ do
(6)
where |-] denotes the expectation over trajectories induced by π and P. Note that J is scalar corresponding to the expected undiscounted return of policy under the initial state distribution du, which is the expected total reward obtained by x when starting from so ~ dg- We are now ready to formalize the problem we want tackle:
3

---

Published as a conference paper at ICLR 2022
Problem Formulation. Given set of MDPs Ma with deterministic transition functions and SIF, we want to construct a set of n policies IITh = {- such that the performance of the policy "r" obtained by performing GPI that set will maximize (6) for all rewards Tw. where E W. That is, we want to solve the following problem:
GPi
arg max I1 C"
J F for all W.
should be noted that the performance measure provided in (6) only measures the expected total reward and thus cannot capture the optimality of the GPI policy. For instance, this measure cannot distinguish between two policies that achieve the same expected total reward in a different number of time steps. However, Theorem 2 in Barrrtoo et al. (2017) implies that, in general, the only way to guarantee the optimality of the GPI policy is to construct a behavior basis that contains all possible policies induced by all w E W. Since there are infinitely many values, this is impractical. Thus, in this study, we only consider GPI policies that maximize the expected total reward (6).
As solution candidate to the problem in 7 we now focus a specific set of deterministic policies, called set of independent policies (SIP), that are able to obtain features independently of each other: Definition (SIP). Let 4 that are induced by each of the features in tb II is defined to be SIP if its elements, Ty. satisfy:
{or be a SIF and let 11
{ be a set of deterministic policies
Φ5(St aes St41) (50 ag $1) Nj i, Vi, Vsg dg and Vt (1..... T),
(8)
where T is the horizon in episodic environments and T + oo in non-episodic ones, ag n, (50) and (st, a2 s(+1)==1 is the sequence of state-action-St state triples generated by n. 's interaction with the environment.
In general, having SIP in set of MDPs with stochastic transition functions is not possible, as the stochasticity can prevent (8) from holding. Thus, the assumption of set of MDPs with deterministic transition functions is critical to our analysis. An immediate consequence of having this set of policies is that the corresponding SFs can be expressed in a simpler form, as follows:
Lemma 1. Let be a SIF and let n, be a policy that is induced by the feature di E and is member of a SIP II. Then, the entries of the SF abzt of policy nt, has the following form:
(s,a), ifi=
(s, = 0,
(9)
otherwise
Due to the space constraints, we provide all the proofs in the supp. material. Lemma I implies that once we have a SIP, the SFs take the much simpler form @ which can allow for the GPI policy to maximize performance all possible tasks according to the measure in (6). solving the optimization objective in (
Theorem 1. Let & be SIF and let II be a SIP induced by each of the features in 4. Then, the GPI GPI is solution to the optimization problem defined in 7 policy "il
Theorem I implies that having access to a SIP which consists of only n policies, where n is the dimensionality of &. and applying the policy composition operator GPI on top, allows for instan- taneously achieving maximum performance across all possible downstream tasks. Considering the fact that there infinitely many such tasks, this provides a significant gain in the number of policies that are required to be learned for full downstream task coverage.
4 CONSTRUCTING A SET OF INDEPENDENT POLICIES
Based on our theoretical analysis in Section 3 we now propose a simple algorithm that iteratively constructs a SIP, given SIF. Since independent policies can attain certain features without affecting the others, a set of them can constructed by simply learning policies for each of the appropriate tasks and then by adding these learned policies one-by-one to initially empty set. In particular, by sequentially learning policies for each of the tasks in W = {w,}r-. 1 C W, where w; is an n-dimensional vector with a positive number in the ith coordinate and negative numbers elsewhere, and then adding these policies to a policy set, one can construct a SIP. Algorithm provides a step- by-step description of this construction process. Note that the algorithm does not depend the
4

---

Published as a conference paper at ICLR 2022
(a) Environment
(b) Preference vectors
(c) Trajectories
Figure 1: (a) The 2D item collection environment (Barreto et al.
2020 The environment consists of
10 x 10 cells and the shape (traingle and diamond) of the items represents their type. (b) Five distinct
preference vectors that lie on the surface of the E 2D ball: W1 = (- (-vI/2 +V/22), W2 (0 +1), W3 (+ (+/1/2 + +1/2,, W4 (+1 0) and W; (+v -v1/2) (c) The trajectories taken by the optimal policies ( = 0.95) corresponding to the preference vectors wi...., W5 in a simplified version of the environment with two items of each type.
particular values of w, E W as long as the corresponding coordinate has a positive value and all others are negative. Another thing to note is that the algorithm runs for only iterations, where is the dimensionality of the feature vector Φb
5 EXPERIMENTS
We start this section by performing experi- ments to illustrate the theoretical results derived in Section 3 Then, compare the perfor- mance of the policy construction approach pre- sented in Algorithm [ with recently proposed diverse policy set construction methods (Eysen- bach et al.] 2018) (Zahavy et al., 2020 2021). Next, we show that a SIP can better bootstrap learning on new tasks where the reward func- tion cannot in fact be expressed a linear com- bination of the features. a case that lies outside of our assumptions. Finally, we demonstrate that the set of policies produced by our approach can be useful in a lifelong RL setting. The ex- perimental details together with more detailed results can be found in the supp. material.
Algorithm 1: Constructing a SIP
Require: SIF Φ; Initialize: I1o <- 0. 1, + twikiai
while s n do
Wt W[t]:
nt + solution of the task Tw, using RL;
II 11 - {
t ++;
end return: T7
Experimental Setup. Throughout this section, we perform experiments on the 2D item collection environment proposed in Barreto al. (2020) (see Fig. Fig.[a),, as it is prototypical environment where GPE & GPI is useful and it allows for easy visualization of performance across all downstream tasks. Here, the agent, depicted by the yellow circle, starts randomly in one of the cells and has to obtain/avoid 5 randomly placed red and green items, which are of different type. At each time step, the agent receives image that contains its own position and the position and type of each item. Based on this, the agent selects an action that deterministically moves it to one of its four neighboring cells (except if the agent is adjacent same cell). By moving to the cells occupied by an item, the agent picks that item and gets reward defined by that item type. The goal of the agent is pick up the "good" items and avoid the "bad" ones, depending on the preference vector w. The envernenvironment interaction lasts for 50 time steps, after which the agent receives "done" signal, marking the end of the episode. Note that despite its small size, the cardinality of this environment's 's state space is on the order of 10 and thus requires the use of function approximation. More on the implementation details of the environment and results its stochastic version can be found in the supp. material.
the boundaries of the grid, it remains on the
In order to use GPE & GPI in this environment, we must first define: (i) the features & and (ii) a set of policies II. Following Barreto et al. (2020), we define each feature d; an indicator function signalling whether an item of type has been picked up by the agent. That is, Φz(s. a, s') = taking action in state results in picking up item of type i, and (, a, s') 0 otherwise. Note that these form a SIF, as there exist trajectories which start as ( Op $1) = and in which all the features associated with certain item type can be obtained without affecting the others. We now
5

---

Published as a conference paper at ICLR 2022
Normalized rewards
Normallzed sum rewards
.0
0.8
Wg
0.6
0.4
0.2
0.2
Dis
Disz
0la4
Tlis
W5
T1s234
W9
(a) Disjoint sets
(b) Incrementally growing sets
Figure 2: The normalized sum of rewards over 17 evenly spread tasks over the nonnegative quadrants of the unit circle. The plots are obtained by averaging over 10 runs with 1000 episodes for each task. The performance comparison of 1s (a) with disjoint sets 1l and Ils, and (b) with incrementally growing sets Il 1223 and II 152334
turn to the question on how to determine the set of policies IT. We restrict the policies in II to be solutions of the tasks w E W. With Algorithm [ we have already provided one way of constructing this set. Throughout the rest of this section we will compare Algorithm I with alternative policy set construction methods.
Following Barreto et al. (2000) we use an algorithm analogous to Q-learning to approximate the SFs induced by & and Similarly, we represent the SFs using multilayer perceptrons with two hidden layers. More details can be found in Barreto et al. (2020).
5.1 ILLUSTRATIVE EXPERIMENTS
Question 1. Do the theoretical results, derived in Section 3 also hold empirically?
In order answer this question, we constructed policy set using Algorithm I and evaluated using the evaluation scheme proposed by Barretoo et al.] (2020). Specifically, after initializing W = (WI, Ws} and running Algorithm [ we obtained the SIP 1l { JTJ. whose elements are solutions to the tasks Wi and Ws, respectively (see Fig. [b]. Then, we ran an evaluation scheme that evaluates the GPI policy GPI "Th'. over 17 evenly spread tasks over the nonnegative quadrants of the unit circle in Fig. [b We did not perform evaluations in the negative quadrant, as the tasks there GPI performs well across all the are not interesting. Results are shown in Fig. 2a As can be seen, x "Iss
downstream tasks, empirically verifying Theorem [
Question 2. Is having a SIP essential for full downstream task coverage?
According to Theorem I having SIP is requirement for guaranteeing good performance across all downstream tasks. However, in order see how well the GPI policy performs when this is not the case, similar to Barreto et al. (2020). we compared 1l15 with two other possible policy sets: 1124 = {22 ] and 1l, = {ma}. whose policies cor- respond to the tasks W2, Wa and W3, respectively. It should be noted that 22 is default policy set used in prior stud- ies on SFs (Barreto et al. 2018). The results, in Fig. 2a show that TT2 and Th are not able to perform well across all downstream tasks, specifically failing on quadrants II and IV. This justifies the requirement of learning a SIP for full downstream task cov- erage.
Value
Palkies
homg
Itoms
Figure 3: The learned SFs of the poli- cies in Πıs and 12 for the state in Fig. Icland the left action. Here, each row corresponds to a different pol- icy and each column corresponds to a different item ('R' ed and 'G'reen).
2017 2018 2020 Borsa et al. GPl
GPT
Question 3. Do the SFs of the policies in a SIP have a simple form?
According to Lemmal T the SFs of the policies in SIP should have simple form. To empirically verify this, in Fig. 3 we visualize the SFs of the policies in the sets 11s and II for the simplified environment depicted in Fig. Tc We can see that the SFs of the policies in Ths indeed have simple

---

Published as a conference paper at ICLR 2022
form, in which the off- off-diagonal entries have values that are very close to zero, while this is not the case for I121.
Question 4. Does adding more policies SIP have any effect on its downstream task coverage?
Theorem D iimplis that, given a SIF, having a SIP is enough to guarantee good performance across all possible tasks. To test empirically whether adding more policies to SIP has any effect on its performance across all tasks, we compare the performance of the policy set 1l with policy sets 1552, 1233 and 15234, formed by adding one-by- by-oe the policies 22, Va and TTa I1.- Results are shown in Fig. 2b] As expected, adding more policies to the SIP 11 has no effect on its downstream task coverage.
5.2 COMPARATIVE AND LIFELONG LEARNING EXPERIMENTS
Question 5. How does Algorithm ! compare to prior diverse policy set construction methods?
Prior work has shown that having access to a diverse set of policies can help transfer to downstream tasks. Al- gorithm D can also be seen as a diverse policy set con- struction method, as it constructs a policy set that is di- verse in the feature visitation profile. In order to see how well it compares gorithm M with three recently proposed diverse policy set construction methods: (i) DJAYN" (018)) which constructs a policy set by collectively train- ing policies with information-theon that encourage discriminablity among the policies in the set based on their state visitation profile, (ii) SMP (Za-) havy et al. (020)) which constructs policy set by itera- tively adding policies trained on the worst-case linear re- ward with respect to the previous policies in the set, and (iii) DSP (Zabavy et al., (202)) which constructs a pol- icy set by iteratively adding policies that trained tasks w,, -01 (1/n) Ei=o vik. where n is the numher of policies in the current policy set. More on the specific im- plementation details of these methods can be found in the supp. material. The comparison results, shown in Fig. + indicate that none of the prior diverse policy set construc- tion methods are able consistently construct a policy set that enables full downstream task coverage.
We Normalized of rewards
0.5
0:01
0.2
prior work, we compare Al-
et al.
DIAYN
SMP
reward functions
DSP
Figure 4: The normalized sum of re- wards of 1lss, and the policy sets con- structed by DIAYN, SMP and DSP. Since the policy sets constructed by the prior methods depend on their particular initialization, their plots are obtained by running each of the constructed policy sets for 5 runs and then averaging over their results. For each task, the agent was evaluated on 1000 episodes. The plot for Ihs obtained in a similar way in Fig.
Question 6. Is learning a SIP also effective when the downstream task's reward function cannot be expressed single linear combination of the features?
So far, we have considered the scenario where the GPI policy evaluated on tasks whose reward functions were obtained by linearly combining the features & using single, fixed w. We now consider downstream tasks that do not satisfy this assumption, e.g. where w changes as a function over the environment's state. Note that Theorem I has nothing to say in this case. Nevertheless, in order to test whether if learning a SIP can still be useful in this scenario, we consider a transfer setting in which meta-policy is trained to orchestrate the policies in this set when faced with downstream task. Specifically, after constructing the policy set, we learn a function that maps states to preference vectors, w S + W', whose output is then used by GPE & GPI to synthesize policy for the downstream task of interest (see the "Preferences as Actions" section in Barreto et al. (200)) and the Option Keyboard framework (Barreto al. 2019 for more details). We define W [W1, W2, Ws. W.. }s} and use Q-learning to learn W.
As an instantiation of the scenario discussed above, we consider two different downstream tasks: (i) sequential reward collection, in which the agent must first pick up items of certain type and then collect the items of the other type, and (ii) balanced reward collection, in which the agent must pick up the type of item that is more abundant in the environment. We compared the performance
We use GPE & GPT compatible version of DIAYN whose details are provided in the supp. material.

---

Published as a conference paper at ICLR 2022
1.0
1.0
Nomalzed sum rewartss
0.8
0.6
0.6
0.4
Nomalized
0.4
DQN
DON
0.2
T&4
Das
1.25
1.5
2.5
Time stops
Time steps
1e6
(a) Sequential reward collection task
(b) Balanced reward collection task
Figure 5: The normalized sum of rewards of the policy sets 11 and II24. and DQN on the (a) sequential reward collection and (b) balanced reward collection tasks. Shadowed regions are one standard error over 10 runs.
of the SIP 11 with the policy set 1124- As reference to the maximum reachable performance, we also provided the learning curve DQN (Mnih et al. 2013), whose specific implementation details can be found in the supp. material. The results, shown in Fig. [5 and [bb show that 1hs outperforms 22 both in terms of the learning speed and asymptotic performance, reaching the asymptotic performance of DQN. These results suggest that having access to SIP can also be effective scenarios where the downstream task's ' reward function cannot be described as a single linear combination of the features.
Question 7. How can learning a SIP be useful a lifelong RL setting?
Except for the last question, have consid- cred an idcalistic scenario in which, during transfer, the agent gle preference vector w describing station- ary downstream task of interest. We now con- sider a lifelong RL (LRL) setting, in which the agent has to infer the current from data and has to quickly adapt to the changing w's dur-
Normaizess sum rewaards
provided with sin-
DQN
MaxQUint
0.2
Tl
ing its lifetime Concretely, we consider the setting in which the agent infers w by follow- ing the regression procedure provided in Bar- reto al. (2020) and the tasks change from W1 to ws oye-by-one 5x 10 time steps. After the end of task ws, the task resets back to W1 and this task cycle goes on forever.
0.0
Time steps
Figure 6: The normalized sum of rewards of the policy sets 1l and I124. DQN, and MaxQInit in a lifelong RL setting described in the text. Shad- owed regions are one standard error over 100 runs.
clockwise fashion every
In Fig. [6 we compare the performance of Ihss with the policy set I124, with DQN, and with a LRL method MaxQInit (Abel et al. 2018). For fair comparison, allow for MaxQInit to have access to all the tasks before each task change (see the supp. material for the implementation details). We see that the policy set 1l allows for better transfer changing tasks compared to 1l24. We also see that, although MaxQInit outperforms DQN, they both fail in instantameously adapting to the changing tasks, and DQN sometimes catastrophically fails on tasks that has already encountered before (see the drastic drop in performance when the task transitions from Wa to w1). These results illustrate how SIP can also be useful LRL scenario.
RELATED WORK
Successor Features and GPI. In this study, focused relevant work that set of SFs
together with GPI for performing transfer RL (Barreto et al.) 2017 2018 2019 2020 Borsa
al. 2018 Hansen al. 2019). Among these studies, the study of Barreto et al. 2020 the
closest to our work. We built on top of their approach and tried to answer the following questions: (i) what behavior basis should be learned by the agent so that its instantaneous performance on
We consider setting in which the agent is allowed for certain amount of pre-training before I.R. starts.
8

---

Published as a conference paper at ICLR 2022
all possible downstream tasks is guaranteed to be good, and (ii) what are the conditions required for this? In addition, we provided empirical results illustrating how a good behavior basis can be useful in more realistic scenarios. Another closely related work is the study of Gfimm et al. (2019) which shows that having access to a set of policies that obtain certain disentangled features can allow for achieving high level performance on exponentially many downstream goal-reaching tasks. However, this study requires having access to disentangled features, which have a very specific form; in contrast, we require set of independent features, which are more general and commonly used [Barreto et al.) 2017, 2020). Additionally, we provide a more formal treatment of the instantaneous transfer problem and our experiments address a broader range of questions.
Diverse Skill Discovery. Another related line of research is the information theoretic diverse skill discovery literature (Gregor et al.) 2016 Eysenbach et al., 2018 Achiam et al.) 2018), in which information theoretic objectives are used to construct a diverse policy set that enables better explo- ration and transfer on downstream tasks. An important problem with learning these skills is that most of the discovered policies end up being uninteresting, in the sense that they do not come to be useful in solving downstream tasks of interest, filling up the set with not so interesting policies. Our work prevents this by constructing policy set in which every policy is trained to achieve only particular task so that when combined, can solve more complex downstream tasks of interest.
Other related literature includes the use of SFs to build a diverse skill set. Through using the criterion of robustness. /Zahavy et al. (2020) proposes a method that constructs a set of policies that do as well as possible in the worst-case scenario, and shows that this set naturally becomes diverse. However, a problem with this policy construction method is that it is sensitive to the initialization of the preference vector and thus leads policy sets that do not have full downstream task coverage. By using explicit diversity rewards, Zahavy et al. (202T) proposes another method that aims to minimize the correlation between the SFs of the policies in the constructed set. However, since this method depends on the evolution of the policy set, it also fails in building a policy set with full downstream tasks coverage; by contrast, Algorithm [ does exactly this.
Policy Reuse for Transfer and Lifelong RL. Although there have been prior studies on policy
reuse for faster learning on downstream tasks (Pickett & Barto 2002 Fernández & Veloso 2006
Machado al. 2018; Barrrtto al. 2018) and for achieving lifelong RL (Abel et al. 2018). 3) none of them tackle the problem of learning a set of policies for full downstream task coverage. Recently, by building on top of Barreto et al. (2017), Nemecek & Parr (2021) proposes policy set construc- tion method that starts with a set of policies and gradually adds new ones based on a pre-defined threshold. However, they also do not consider the full downstream task coverage problem. The most closely related work however are the recent studies of Tasse et al. that improve on Van Niekerk et al. (2019) and in which a set of pre-learned base policies are logically composed for super-exponential downstream task coverage (Tasse et al.) 2020) and lifelong RL (Tasse et al., (2022). Despite the
similarities in the motivation, there are important differences compared our work: (i) while their
approach requires extensions to the reward and value function definitions, our approach builds on
top of the readily available GPE& & GPI framework and (ii) while their approach only considers goal-based tasks, where upon reaching goal the episode terminates, our approach handles both these tasks and the ones in which the agent has to achieve multiple goals within a single fixed-length episode.
7 CONCLUSION AND FUTURE WORK
To summarize, in this study, we provided theoretical analysis elucidating what counts as a good behavior basis for performing GPE& & GPI and showed that, under certain assumptions, having access to a set of independent policies allows for instantaneouslly achieving high level performance on all downstream tasks. Based on this analysis, we proposed simple algorithm that iteratively constructs this policy set. Our empirical results (i) validate our theoretical results, (ii) show that the proposed algorithm compares favorably to prior methods, and (iii) demonstrate that a set of independent policies can be useful in scenarios where the downstream task of interest cannot be expressed with a single preference vector, which includes lifelong RL scenarios. Note that our approach relies on the existence of an independent set of features, which are maximized to obtain independent policies. In general, a feature extraction procedure may be needed as a preprocessing step to obtain such features. We hope to tackle this problem in future work. We also hope to find useful generalizations of our theoretical results to MDPs with stochastic transition functions.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This project has been partly funded by an NSERC Discovery grant and the Canada-CIFAR Al Chair program. We would like to thank Shaobo Hou for clarifying some parts of the code and the anony- mous reviewers for providing critical and constructive feedback.
REFERENCES
David Abel, Yuu Jinnai, Sophie Yue Guo, George Konidaris, and Michael Littman. Policy and value transfer in lifelong reinforcement learning. In International Conference on Machine Learning, pp. 20-29. PMLR, 2018.
Joshua Achiam, Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms. arXiv preprint arXiv 2018.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 4058-4068, 2017.
Andre Barreto, Diana Borsa, John Quan, Tom Schaul, David Silver, Matteo Hessel, Daniel Mankowitz, Augustin Zidek, and Remi Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In International Conference on Machine Learning. pp. 501-510. PMLR, 2018.
André Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygün, 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.
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-3000) 2020.
Diana Borsa, Andre Barreto, John Quan, Daniel Mankowitz, Hado van Hasselt, Remi Munos, David Silver, and Tom Schaul. Universal successor features approximators. In International Conference on Learning Representations, 2018.
Peter Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5(4):613-63 624, 1993.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without reward function. In International Conference on Learning Representa- tions, 2018
Fernando Fernández and Manuela Veloso. Probabilistic policy reuse in reinforcement learning agent. In Proceedings of the fifth international joint conference on Autonomous agents and mul- fiagent systems, pp. 720-727, 2006.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.075077 2016.
Christopher Grimm, Irina Higgins, Andre Barreto, Denis Teplyashin, Markus Wulfmeier, Tim Her- tweck, Raia Hadsell, and Satinder Singh. Disentangled cumulants help successor representations transfer to new tasks. arXiv preprint arXiv: 10866, 2019.
Steven Hansen, Will Dabney, Andre Barreto, David Warde-Farley, Tom Van de Wiele, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. In Interna- tional Conference on Learning Representations, 2019.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference Learning Representations, 2018
10

---

Published as a conference paper at ICLR 2022
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning, nature, 518(7540):529-5553 2015.
Mark W Nemecek and Ron Parr. Policy caches with successor features, In International Conference on Machine Learning, pp. 8025-8033. PMLR, 2021.
Mare Pickett and Andrew G Barto. Policyblocks: An algorithm for creating useful macro-actions in reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 506-513, 2002.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354 359, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre. Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140- 1144, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Geraud Nangue Tasse, Steven James, and Benjamin Rosman. A boolean task algebra for rein- forcement learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Geraud Nangue Tasse, Steven James, and Benjamin Rosman. Generalisation lifelong reinforce- ment learning through logical composition. In International Conference on Learning Represen- fations, 2022.
Benjamin Van Nickerk, Steven James, Adam Earle, and Benjamin Rosman. Composing value func- tions in reinforcement learning. In International Conference Machine Learning, pp. 6401- 6409. PMLR, 2019.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameeki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning, Nature, 575(7782):300-35) 2019.
Tom Zahavy, Andre Barreto, Daniel J Mankowitz, Shaobo Hou, Brendan O' O'Donoguue, lurii Ke- maev, and Satinder Singh. Discovering a set of policies for the worst case reward. In International Conference on Learning Representations, 2020.
Tom Zahavy, Brendan O' Donoghue, Andre Barreto, Volodymyr Mnih, Sebastian Flennerhag, and Satinder Singh. Discovering diverse nearly optimal policies with successor features. arXiv preprint 106:06006 2021.

---

Published as a conference paper at ICLR 2022
A PROOFS
Lemma 1. Let be a SIF and let n; be a policy that is induced by the feature ó; E and is member of SIP II. Then, the entries of the SF ah of policy nı has the following form:
(s, u (s,
i
00
otherwise
Proof. The proof follows directly from the definition of SIP. Remember that for policy that is a member SIP, we have that:
6j (St, de. St+1) (50, ao, 81) Vj + i, Vi, Vso do and At E (I....,T).
where 7 is the horizon, = (50) and (8t, de, 86+1) ) is the sequence of state-action-shee actten-state triples that are generated by n. interaction with the environment. Thus, for j # i, we have:
1y (8, ETT,P
(o A,,,, Se 8, A
:==
8 7 (y Ar, Sc+1) St 58, Ae =a
Ep
Σ
(by Definition 2
* EEloo Sc+1 s, a
* (
k=0
3 (Su, 0o)
(by Definition 2
k=0
3 (so ao)
0.
(by Definition 1
Theorem 1. Let & be SIF and let II be a SIP induced by each of the features in 4. Then, the GPI GPI is solution to the optimization problem defined in 7
policy "l
Proof. Remember that the GPI policy for downstream task w is obtained as:
GPI T
(s)
E arg max @ (s, a), aEAA
where Q (s, a) = max Q (s, a). By expressing Q (s, a) as a weighted sum of the SFs of policy Mi, have:
(s, = max Σ wy
= max with (8, + Σ 10 (3,a)
juz
max (s,')
(by Lemma I
Thus, we have:
T (s) E arg max Q (s. a) aEA
arg max max (s.
aEA
12

---

Published as a conference paper at ICLR 2022
which implies that the GPI policy x will obtain all the features associated with a positive w; (in an order that depends on the product waa,"' (s, a)), ignore the ones with a zero Wi, and avoid the ones with a negative wy. This in turn implies that the GPI policy G will solve the optimization problem in
B EXPERIMENTAL DETAILS
In this section, we provide the implementation details of the 2D item collection environment and the experimental details of our policy construction method together with the prior methods that we have used for comparison.
B. IMPLEMENTATION DETAILS OF THE 2D ITEM COLLECTION ENVIRONMENT
As described in the supplementary material of Barreto et al. 2020), at each step the agent receives an 11 x x (n 11+1) 1) tensor (an x image with (n + 1) channels) representing the configuration of the environment, where n is the number of items in the environment. The channels are used to identify the items and the walls. Specifically, there is one channel for each of the items and one channel for the impassable walls around the edges of the grid.
The observations are "egocentric" the sense that images are shifted so that the agent always at the top-left cell of the grid. Barreto et al. (2020) found that this representation helps the learning process as each action taken by the agent results in larger changes in the observations. The observa- tions are also toroidal in the sense that the images wrap around the edges that the agent always observes the environment, even though the walls prevent it from crossing one side to the other.
B.2 OUR METHOD AND DQN
For our experiments with GPE & GPT and DQN (Mnih et al. 2015), we have used the publicly available code of Barreto al. (000)). Thus, implementation details as the neural network archi- tectures that are used, the hyperparameters (replay buffer sizes, learning rates etc.) and the way the SFs and state-action value functions are learned can all be found both in the provided link and in the supplementary material of Barreto et al. (2020). We have also followed the same experimental protocol provided in the supplementary material of Barreto al. (2020).
B.3 PRIOR DIVERSE POLICY SET CONSTRUCTION METHODS
Before moving on to the implementation details the prior diverse policy set construction methods, start this section by defining the concept of reward equivalent policies (REP). This definition allows for a simple representation of the policy sets that are constructed by these prior methods in terms of the policy sets that can be induced by the nine preference vectors in Fig. 7
Definition (REP). Let n; and π be two policies that are induced by tasks w, and w. respectively. and ny are defined to be REP if they achieve the same expected total reward on an arbitrary task w, iee. if:
DC
ERUP P
Σ
Fw (St, Ar, Se. do
Emg.P P
Σ (w Ar, Set1) do
It should be noted that even if two policies are induced by two different tasks, they can still be REP. For instance, the policies induced by the tasks (0.6 0.8) and (0.8 0.6) are reward equivalent as they achieve the same expected total reward by collecting all the items in the environment depicted in Fig. Ia Note that Definition only takes into account what the policies achieve and not how they exactly achieve it.
thub. http:://hhhcccceeeeeeeeeeeeeeeer
keyboard
13

---

Published as a conference paper at ICLR 2022
Importantly. Definition alloww for defining equiva- lences between policy sets. For instance, the policy set induced by tasks (0.6 v.8) and (0.6 -0.8) contains a policy that collects both of the items (reward equiv- alent to m3) and policy that collects the first item while avoiding the second one (reward equivalent to my). The policy 13s5 also contains policies that achieve the same tasks. Thus, the former policy set can be considered be reward equivalent to the pol- icy set 33.. Note that another policy set induced by tasks (0.8 0.6) and (0.8 -0.6) can also be considered to be reward equivalent to the policy set Nas.- In the rest this section, we will use this reward equiva- Ience relation for a simple representation of the pol- icy sets constructed by prior methods (in terms of the policy sets that can be induced by the preference vectors in Fig. 7
W2
W1
Ws
WC
W6
Figure Eight different preference vectors that lie on the surface of the & 2D ball and single preference vector (We) that is at the origin of this ball. The corresponding values
are: W1 = (-V11/2 +V1/2), W2 = (0 +1), (+V1/2 +v122,, W1
W3
(+1 0),
Ws = (+VI/2 -V/22), We = (0 -1) W7 (-V1/2 -1/2), Ws (-1 0), Wg 0).
DIAYN (Eysenbach et al. 2018). Among the prior diverse policy set construction methods that we have used, all except DIAYN are compatible with the GPE & GPI framework. Thus, in order to also make DIAYN compatible, while discovering a set of diverse policies, we have concurrently learned the SFs of the policies in this GPI can be performed later on. Importantly, rather than encouraging diversity in the state visitation profile, we have encouraged diversity in the feature visitation profile by feeding the visited feature vectors & as input to the discriminator (as opposed to feeding the visited states in regular DIAYN). This is because we are interested in policies that are able to obtain certain features, as opposed to ones that just push the agent to different parts of the state space. For the RL algorithm, we have used a vanilla policy gradient algorithm with an additional entropy loss term, for preventing the policy from becoming deterministic in the early stages of training.
that GPE &
After setting the number of policies to be discovered to 3 (as there are 3 possible feature vectors in the environment depicted in Fig. la 0), (0 1) and o)), learning the SFs of these policies and running the GPE & GPI compatible version of DIAYN described above, we have observed that the discovered policies either end up being policies that obtain both of the items (reward equivalent to πa) or policies that obtain none (reward equivalent to T7), corresponding to a policy set that is reward equivalent to the policy set II37 (see Fig. 7). Thus, the results presented in Fig. 4 corresponds results obtained with the policy set 1l37. We have also experimented with larger numbers of policies be discovered, however, we observed no difference in the qualitative behavior of the policies that were discovered.
the
In our experiments, for the representation of the policy we have used the same neural network architecture that was provided in Barreto et al. (2020). The hyperparameters of our implementation are provided Table
Table 1: Hyperparameters of our DIAYN implementation.
Learning rate of the policy Learning rate the discriminator
le 3
1e 3
Discount
0.95
Entropy coefficient
0.001
Gradient clip
1.00
Value function loss coefficient
0.05
SMP (Zahavy et al. 2020). After initializing the preference vector to an arbitrary vector on the surface of the &, 2-dimensional ball (see Fig. 7 and running the SMP algorithm till termination, have observed that for each initialization of preference vector, different policy sets were constructed. The resulting policy sets end up being reward equivalent to of the following sets: IIs7. I117, 1157, 1l77, 1g1 1l27, II47, II, 11... 18857, I88517 Ha I6155 and 18.7. Thus, the results presented in Fig. correspond the average results obtained by these policy sets.
14

---

Published as a conference paper at ICLR 2022
DSP (Zahavy al. 2021). After initializing the preference vector to arbitrary vector the surface of the & 2-dimensional ball (see Fig. 7 setting T = 2 (see Algorithm in Zahavy et al. have observed that for each initialization of preference vector, different policy sets were constructed. The resulting policy sets end up being reward equivalent one of the following sets: 37,., sss, 11. 1T27. 47. 779,, Mas and TTs. Thus, the results presented in Fig. correspond to the average results obtained by these policy sets.
(202I) for the details) and running the DSP algorithm,
We have also experimented with larger T values, however, after T the only policy be added to the set is a policy that is reward equivalent to T7. For instance, when 7 = 3, the resulting policy sets end up being reward equivalent to one of the following sets: II377, IsST.. 11167, 12777. 1177, 19797 and I[s67. Since тy is policy that avoids the items in the environment depicted in Fig. Ia it not useful policy for the tasks considered in this study. Thus, we reported results only for the case of T = 2.
B.4 MAXQINIT
MaxQInit (Abel et al. 2018) is a lifelong RI. approach in which the value function of an agent is initialized to the best possible value that minimizes the learning time new downstream tasks, while the same time preserving PAC guarantees. More specifically, before starting new task, the value function is initialized as follows:
(s) = max (M( MEM
(10)
where M is the set of MDPs that the agent has sampled so far, and Qu is the value function that the agent learned from interacting with each MDP. However, the policy sets (Il15 and 1l24) generated by Algorithm | are obtained as a result of pre-training in the environment, fair a comparison with these policy sets, we have allowed for M to be equal to M, where M is the set of all MDPs (see
In the GPE & GPI framework, 10 corresponds to initializing the value functions using to the values of the task W3 (+v1// + 1/22 (see Fig. 7 as it is with this task that Qas is the maximized. Thus, the results presented in Fig. correspond to the results obtained by initializing the value function of DQN (Mnih et al. 2015 the value function of the task W3 right at the beginning of each new task.
C UNNORMALIZED RESULTS
In this section, we provide the unnormalized results for the experiments in Section 5 The and y-axis the plots now indicates the sum of rewards as is, without any normalization.
Sum of rewards
Sum of rewards
W
W2
Wi
W:
Πas
Tasza
Ws
Mis234
W;
(a) Disjoint sets
(b) Incrementally growing sets
Figure 8: The unnormalized sum of rewards over 17 evenly spread tasks over the nonnegative quad- rants of the unit circle. The plots obtained by averaging over 10 runs with 1000 episodes for each task. The performance comparison of (a) 115 with disjoint sets T2 and Hs, and (b) T1s with incrementally growing sets 1152, 11223 and IT 15231-
15

---

Published as a conference paper at ICLR 2022
W2
Sum rewards
W:
W3
2
DIAYN
SMP
DSP
N1s
W5
Figure 9: The unnormalized sum of rewards of 11s,, and the policy sets constructed by DIAYN, SMP and DSP. Since the policy sets constructed by the prior methods depend their particular initialization, their plots are obtained by running each of the constructed policy sets for runs and then averaging over their results. For each task, the agent evaluated on 1000 episodes. The plot for 11 is obtained in similar way as in Fig.
SSm of rewards
rewards
3-
DON
2
Tox
0p
1
fas
0.00
0.25
0.50
1.00
1.25
150
2.5
Time steps
Time stops
1e6
Sequential reward collection task
(b) Balanced reward collection task
Figure 10: The unnormalized sum of rewards of the policy sets 111s and 1l21, and DQN on the (a) sequential reward collection and (b) balanced reward collection tasks. Shadowed regions are one standard error over runs.
W.
W2
W4
Ws
W:
WV
DON
MaxQinit
rewards
Flas
1-
steps
Figure 11: The unnormalized sum of rewards of the policy sets Iıs and TT2,, DQN, and MaxQInit in a lifelong RL setting described in the text. Shadowed regions are one standard error over 100 runs.
D RESULTS FOR STOCHASTIC ENVIRONMENTS
Even though we have developed our theoretical results by assuming MDPs with deterministic tran- sition functions, order to test the applicability our results with stochastic transition functions, also performed experiments in the stochastic version of the 2D item collection environment with "slip" probabilities 0.125 and 0.25. Results are shown Fig. [2 and [3] As can be seen, even in the stochastic settings, GPI is able perform better across all downstream tasks compared to "Ilas "Ihs
GPI
16

---

Published as a conference paper at ICLR 2022
and T It can also be that adding more policies to the independent policy set 11s again has no effect on the downstream task coverage.
W> Normalized sum of rewards
Normalized rewards
6.0
0.5
0.6
0.6
0.4
0.4
0.2
W4
Thsz
T144
Tis234
Ws
(a) Disjoint sets
(b) Incrementally growing sets
Figure 12: The normalized sum of rewards over 17 evenly spread tasks over the nonnegative quad- rants of the unit circle. The results provided in this figure are for the stochastic 2D item collection environment with "slip" probability 0.125. The plots are obtained by averaging over 10 runs with 1000 episodes for each task. The performance comparison of 1l (a) with disjoint sets Il and Ils. and (b) with incrementally growing sets 112, 11s23 and 112234
Nomalizzd sum of rowards
Normalized sum of rewards
Ws
0.6
This
Thx
TTis
Das224
Ws
(a) Disjoint sets
(b) Incrementally growing sets
Figure 13: The normalized sum of rewards over 17 evenly spread tasks over the nonnegative quad- rants of the unit circle. The results provided in this figure are for the stochastic 2D item collection environment with "slip" probability 0.25. The plots are obtained by averaging over runs with 1000 episodes for each task. The performance comparison of Ils (a) with disjoint sets I2 and II,, and (b) with incrementally growing sets 11152, I1252 and 1112231-
17


Reviews:
[{"review_id": "qHqls39ExZ1", "reviewer": "Reviewer_8NxE", "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": "The paper is, in general terms, interesting for the scientific community in RL. It is well structured and written, it reads very well, the introduction correctly states the problem to be addressed (built around previous works), the limitations that we currently find in the literature and, finally, the contributions. I have not found problems in the notation used or in the mathematical formulations.\n\nHowever, there are a couple of aspects that make me doubt about the merit of this contribution:\n\nIt is a clearly incremental work built on the work of Barreto et al. The novelty of the paper and the contributions offered are limited to answering a series of questions (theoretically and experimentally) about the required conditions and the reliability/guarantee provided by the approximations using SFs & GPI.  On the other hand, the experiments shown, although illustrative, are limited and \"toy-like\". Once again, the settings, frameworks and approximations already presented by Barreto et. al. are used.\n\n", "summary_of_the_paper": "The paper addresses the problem in RL of reusing policies resulting from previously learned (different) tasks in order to perform well on downstream tasks via generalized policy improvement. The authors empirically demonstrate (e.g., using a 2D item collection environment and a lifelong RL scenario) that under certain assumptions about the environment, learning a diverse set of policies bootstrap the learning process on new tasks.", "summary_of_the_review": "See above.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gyIJj0RskXi", "reviewer": "Reviewer_4b5c", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "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 is a strong paper, methodically and clearly presenting its concepts. It is well written, interesting to read, presenting theory before supporting it with experiments. It addresses the main questions with separate experiments. Based on the theory and results, the presented algorithm is better than prior-art in every case. The experiments beyond the original assumptions show that the new algorithm is valuable and interesting for general RL community -- i.e., the last two experiments (reward cannot be expressed as linear combination of features / lifelong RL) show that it outperforms DQN. It would be interesting to see the algorithm also in another domain than 2D item collection (and especially without the linear-combination assumption), but I deem the scope of the paper already well sufficient.\n\nTypos:\np. 3 - it leaveS open the question\np. 3 - clear by the end OF this section\np. 3 - the problem weE want to tackle\np. 7 - tasks that do noT satisfy\np. 7 - test whether IF learning", "summary_of_the_paper": "The paper focuses on reinforcement learning problems with known successor features and rewards expressible as their linear combination. Building on recent research, it presents a concept of independent features and independent policies and way to construct them. Theoretically it shows that the set of independent policies and their combination with GPE & GPI is enough to solve any induced task. Experimentally, the authors verify the theory and compare to existing approaches to create policy sets, outperforming all. They also provide a set of relevant questions and answers, supported by separate experiments. Finally, they perform experiments in problems without the linear combination assumption and lifelong RL setting, with positive results.", "summary_of_the_review": "Well written and interesting paper with strong theory and results, well conducted experiments. Recommending acceptation.\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ehrMGeZ7nAq", "reviewer": "Reviewer_3QcK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 paper tackles an interesting and important question that is clearly critical for developing lifelong agents: which policies or value functions should an agent store in its \"library\" for later use?  The approach taken here is to learn a set of basis policies that are provably optimal (by optimal, we mean that there are no other policies that will result in improved performance after GPI) on downstream tasks within the successor features framework. Given the recent success and adoption of the framework, the results here will likely be of great interest to the community.\n\nI found the paper overall to be extremely well-written and easy to follow (albeit with some details left out, which I will discuss later), and I think that the overall idea is conceptually the correct one concerning the specific question and under the assumptions made. Both theoretical and experimental results are provided, which helps bolster the paper's claims. However, I have certain reservations (and clarifying questions) about some of the results and positioning of the paper, to which I would appreciate a response. \n\n**On related work:**\n\nThe big downside for me is the lack of related work, which makes it difficult to determine the novelty and answer the question of why one should pick this method over existing ones. The paper builds on the successor features framework and so, unsurprisingly, there are numerous references and comparisons to this line of prior work.  However, there is insufficient coverage of other related work outside of this, and particularly on approaches that set out to do precisely the same thing studied here.\n\nOf course, the literature regarding the transfer of policies and value functions for multitask RL is large and it is not possible to survey the entire field in the space of a conference paper. However, several approaches accomplish the same kinds of things in this paper and the paper would be made much stronger by distinguishing its contributions from past approaches. For instance, Abel et al (2018) provide theoretical results (and a simple approach that maximises over the value functions) about how best to reuse learned policies to solve new tasks, while van Niekerk et al (2019) study composition in a similar setup (see Theorem 2 in particular). Closely related to this is also Tirinzoni et al (2018).  Fernandez and Veloso (2006) build on Thrun and Schwartz (1995) to determine how to reuse past policies to accelerate learning on new tasks. \n\nThe most important piece of related work is the recently published paper by Nemecek and Parr (2021). Their approach tackles the exact same problem, but they are able to iteratively build a policy cache without having to rely on the notion of independent features/policies. One of the most important aspects of their work is that they have motivating experiments as to why you would only want to store certain policies. In the experimental setup here, there are very few tasks, and so why not just store all the policies? In their work, they have 1000+ tasks, and so it is clearly infeasible to store every single policy learned. This motivation is in general missing from the paper. Please comment on the difference between this work and theirs.\n\nIt is worth including either direct empirical comparisons, or brief discussions of the differences to this work. Older approaches such as PolicyBlocks (Pickett and Barto 2002) may also be of relevance, since they focus on collecting a cache of policies that are used to inform future learning.\n\n**On theoretical results:**\n\nThe theoretical results speak to the idea that, given a set of policies, is a subset we can choose to keep in our \"library\" to maximise the outcome of doing generalised policy improvement. While this is true, it would have been even nicer to see results that say something about how close to optimal we can get with these policies. For example, closely-related work by Abel et al (2018) provides PAC bounds when maximising a set of previously-learned action value functions, and I can't help but think that a similar kind of result here would be much more impactful. \n\nThe definition of independent features seems quite restrictive to me, and from the intuition provided, I can only see it being useful for goal or subgoal-reaching tasks, where the features are 0 everywhere until a subgoal is reached. I'm also not 100% sure I understand the definition of an independent policy. When it says \"a policy is induced by each feature\", does this mean a policy that \"achieves\" a feature by reaching a state where its value is non-zero? If so, then I take it to mean that independent policies are policies that cause different features to be set to non-zero (and all others remain 0). Thus, to use the given domain as an example, two independent policies would be a policy that collects triangles, and one that collects diamonds. \n\nIf so then I wonder how useful Lemma 1 and the results in Figure 3 are, since the expected features are essentially the Q-value function for solving a task with rewards of 0 everywhere and C when a goal is achieved. These results basically say: the policy for collecting diamonds has a high expected return for collecting diamonds and 0 for collecting triangles (and vice versa), which does not seem particularly surprising.\n\nFurthermore, if this is the case, then the setup seems almost identical to Nangue Tasse et al (2020a) who also introduce the concept of a \"policy basis\". While that work does not deal with preferences, it seems like it is extremely related, and even if not used as a baseline, it would be helpful to describe how the notion of basis policies differs from that here.  \n\n**On empirical results:**\n\nThe empirical experiments are well aligned with the theory and the story being told, but I wonder if they do not go far enough. I really liked Figure 2 as an initial start, but there are a few assumptions baked into that result and it would be better if it could be shown how to remove them. In order of importance, these are:\n  1. The agent is essentially told which policies are independent, since these weight vectors are provided up front. However, in general the agent does not get to control the order in which it sees the task, and so a better setup would be to have tasks randomly sampled from a distribution, and require the agent to determine whether a policy is independent. This way, the library can be grown in an informed manner, instead of being provided to the agent directly. \n  2. The above experiment could also be combined with the regression procedure used in Question 7 to infer the weights. Then the agent would essentially be receiving no information, and would have to learn everything directly from data.  \n  3. The lifelong experiment doesn't have any \"lifelong-oriented\" baselines. I think a much stronger experiment would be to test it against MAXQ (Abel et al 2018), Nangue Tasse (2020b) or Nemecek and Parr (2021).\n  4. The theory only holds for deterministic cases, but it would be interesting to test empirically in the stochastic setting, which could easily be done by adding a \"slip\" probability to actions\n\nI also worry a bit about the results in Figure 5. While DQN was used to show what optimal performance looks like, it is remarkably similar to the method presented here. This is despite the fact that DQN must learn everything from scratch, whereas the other approaches only need to learn a mapping from states to weights and then combine them with the pretrained independent (and non-independent) policies. I would have expected the latter approach to completely dominate DQN because of its pretraining, and the fact that this doesn't happen is slightly worrying. Incidentally, the approach taken in Question 6 reminds me of Peng et al (2019) who have a set of policies and attempt to learn weights with which to compose them.\n\nIn line with my concern in the theoretical setting, the method here was tested on a single domain that has these nice subgoal properties, but another domain would go a long way to convincing me how applicable the notion of independent features/policies is. What would happen, for instance, if we were in a classic four-rooms domain, and the policies were to get to the doorways and to get to the centre of the rooms? In this case, there's no way to get to the centre of a room without passing through a doorway, and so would things break down here? My main concern again is just how widely applicable these definitions are. \n\n**Clarifying questions and minor comments:**\n\n  1. I realise space is an issue, but it would be better not to direct the reader to a different paper to try find details of the environment setup (which is actually only in the supplementary material of that paper). Please include the description of the domain in the appendix. Incidentally, I could not locate the statement that describes what the feature function is (is it 0 everywhere and 1 when a particular object is picked up?). \n  2. What is meant by normalised rewards? Is this just scaling the rewards to be in 0-1? Another thing that could be done here is instead to train optimal value functions, and then show the difference between the returns of the composed policies compared to the optimal returns. \n  3. At present, Figure 2 shows that the independent policies are the best, but there's no indication of how far from optimal they are\n  4. Typos: \"wee\" (bottom page 3), missing \"to\" at top of page 8\n\n**References**\n\n  1. Abel, David, et al. \"Policy and value transfer in lifelong reinforcement learning.\" International Conference on Machine Learning. PMLR, 2018.\n  2. Van Niekerk, Benjamin, et al. \"Composing value functions in reinforcement learning.\" International Conference on Machine Learning. PMLR, 2019.\n  3. Tirinzoni, Andrea, Rafael Rodríguez-Sánchez, and Marcello Restelli. \"Transfer of Value Functions via Variational Methods.\" NeurIPS. 2018.\n  4. Fernández, Fernando, and Manuela Veloso. \"Probabilistic policy reuse in a reinforcement learning agent.\" Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems. 2006.\n  5. Thrun, Sebastian, and Anton Schwartz. \"Finding structure in reinforcement learning.\" Advances in neural information processing systems (1995): 385-392.\n  6. Nemecek, Mark W., and Ron Parr. \"Policy Caches with Successor Features.\" International Conference on Machine Learning. PMLR, 2021.\n  7. Pickett, Marc, and Andrew G. Barto. \"Policyblocks: An algorithm for creating useful macro-actions in reinforcement learning.\" ICML. Vol. 19. 2002.\n  8. Nangue Tasse, Geraud , Steven James, and Benjamin Rosman. \"A Boolean Task Algebra for Reinforcement Learning.\" Advances in neural information processing systems (2020a).\n  9. Nangue Tasse, Geraud , Steven James, and Benjamin Rosman. \"Logical Composition in Lifelong Reinforcement Learning.\" Lifelong Machine Learning Workshop at ICML (2020b).\n  10. Peng, Xue Bin, et al. \"MCP: Learning Composable Hierarchical Control with Multiplicative Compositional Policies.\" Advances in Neural Information Processing Systems 32 (2019): 3686-3697.", "summary_of_the_paper": "The paper extends the successor features framework to answer the following question: which policies should we learn and store so that, when presented with a new task, we achieve the best performance possible? The paper defines the notion of independent policies (forming a kind of basis over policy space), which can then be combined to solve new tasks (whose rewards are expressible as a linear combination of features) immediately. Experimental results support the theoretical results and show that it is best to learn these independent policies if we wish to maximise performance on downstream tasks.", "summary_of_the_review": "While the ideas presented here are sound and backed by theoretical and empirical results, the lack of context with respect to prior approaches makes it hard to judge the impact and novelty of the work. The experiments, in particular the lifelong learning one, could benefit from more appropriate baselines. Furthermore, I have concerns about whether the assumptions and definitions are too restrictive, reducing the applicability of the approach more generally, especially compared to more recent work (Nemeck and Parr 2021). I am, of course, open to having this score upgraded based on future discussions and changes.\n\n******************************\nPOST-REBUTTAL\n******************************\n\nThe paper has been significantly strengthened during the rebuttal period, and as such I am increasing my score. One important point to clarify is the setting - the \"unsupervised RL\" setting is a bit ambiguous and could lead to confusion, since it could mean the reward-free RL (see Jin et al 2020) and is separate from the lifelong setting. Clarifying this in the paper is important. \n\nThe main improvement that can still be made is extending it to the lifelong learning setting, where the agent doesn't get to pick its task/reward function. Such an agent would be fully autonomous and would be able to discover and store a library of policies on the fly. This would be much more in line with existing work, and make comparisons to other work (Abel et al, Nemeck and Parr) apples-to-apples. It would also make Algorithm 1 far more interesting than it currently stands. Nonetheless, I feel there is enough here as it is to vote for acceptance", "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": {}}]

Author rebuttal:

Meta-review: This work extends the successor feature framework by focusing on the question of which policies should be learned in order to get the best generalization performance. The reviewers all agree that the question being addressed is interesting and important. One concern raised by two of the reviewers is that the work is rather incremental, providing a relatively small extension from the work of Barreto et al. Nevertheless, the authors have provided a convincing rebuttal, resulting in an increase in score of two of the reviewers. Hence, I recommend acceptance. I do want to ask the authors to carefully read the post-rebuttal point mentioned by reviewer 3QcK about clarifying the unsupervised RL setting.
Decision: Accept (Poster)