XI-LEARNING: SUCCESSOR FEATURE TRANSFER LEARNING FOR GENERAL REWARD FUNCTIONS
Year: 2021

Abstract:
Transfer in Reinforcement Learning aims to improve learning performance on target tasks using knowledge from experienced source tasks. Successor features (SF) are a prominent transfer mechanism in domains where the reward function changes between tasks. They reevaluate the expected return of previously learned policies in a new target task and to transfer their knowledge. A limiting factor of the SF framework is its assumption that rewards linearly decompose into successor features and a reward weight vector. We propose a novel SF mechanism, ξlearning, based on learning the cumulative discounted probability of successor features. Crucially, ξ-learning allows to reevaluate the expected return of policies for general reward functions. We introduce two ξ-learning variations, prove its convergence, and provide a guarantee on its transfer performance. Experimental evaluations based on ξ-learning with function approximation demonstrate the prominent advantage of ξ-learning over available mechanisms not only for general reward functions, but also in the case of linearly decomposable reward functions.

heading: 1 INTRODUCTION
text: Reinforcement Learning (RL) successfully addressed many complex problems such as playing computer games, chess, and even Go with superhuman performance (Mnih et al., 2015; Silver et al., 2018). These impressive results are possible thanks to a vast amount of interactions of the RL agent with its environment/task. Such strategy is unsuitable in settings where the agent has to perform and learn at the same time. Consider, for example, a care giver robot in a hospital that has to learn a new task, such as a new route to deliver meals. In such a setting, the agent can not collect a vast amount of training samples but has to adapt quickly instead. Transfer learning aims to provide mechanisms quickly to adapt agents in such settings (Taylor and Stone, 2009; Lazaric, 2012; Zhu et al., 2020). The rationale is to use knowledge from previously encountered source tasks for a new target task to improve the learning performance on the target task. The previous knowledge can help reducing the amount of interactions required to learn the new optimal behavior. For example, the care giver robot could reuse knowledge about the layout of the hospital it learned in previous source tasks (e.g. guiding a person) to learn to deliver meals.
The Successor Feature (SF) and General Policy Improvement (GPI) framework (Barreto et al., 2020) is a prominent transfer learning mechanism for tasks where only the reward function differs. Its basic premise is that the rewards which the RL agent tries to maximize are defined based on a lowdimensional feature descriptor φ ∈ Rn. For our care-giver robot this could be ID’s of beds or rooms that it is visiting, in difference to its high-dimensional visual state input from a camera. The rewards are then computed not based on its visual input but on the ID’s of the beds or rooms that it visits. The expected cumulative discounted successor features (ψ) are learned for each behavior that the robot learned in the past. It represents the dynamics in the feature space that the agent experiences for a behavior. This corresponds to the rooms or beds the care-giver agent would visit if using the behavior. This representation of feature dynamics is independent from the reward function. A behavior learned in a previous task and described by this SF representation can be directly re-evaluated for a different reward function. In a new task, i.e. for a new reward function, the GPI procedure re-evaluates the behaviors learned in previous tasks for it. It then selects at each state the behavior of a previous task if it improves the expected reward. This allows to reuse behaviors learned in previous source tasks
Source code at https://tinyurl.com/3xuzxff3
for a new target task. A similar transfer strategy can also be observed in the behavior of humans (Momennejad et al., 2017; Momennejad, 2020; Tomov et al., 2021) .
The classical SF&GPI framework (Barreto et al., 2017; 2018) makes the assumption that rewards r are a linear composition of the features φ ∈ Rn via a reward weight vector wi ∈ Rn that depends on the task i: ri = φ>wi. This assumption allows to effectively separate the feature dynamics of a behavior from the rewards and thus to re-evaluate previous behaviors given a new reward function, i.e. a new weight vector wj . Nonetheless, this assumption also restricts successful application of SF&GPI only to problems where such a linear decomposition is possible. We investigate the application of the SF&GPI framework to general reward functions: ri = Ri(φ) over the feature space. We propose to learn the cumulative discounted probability over the successor features, named ξ-function, and refer to the proposed framework as ξ-learning. Our work is related to Janner et al. (2020); Touati and Ollivier (2021), and brings two important additional contributions. First, we provide mathematical proof of the convergence of ξ-learning. Second, we demonstrate how ξ-learning can be used for meta-RL, using the ξ-function to re-evaluate behaviors learned in previous tasks for a new reward function Rj . Furthermore, ξ-learning can also be used to transfer knowledge to new tasks using GPI.
The contribution of our paper is three-fold:
• We introduce a new RL algorithm, ξ-learning, based on a cumulative discounted probability of successor features, and two variants of its update operator.
• We provide theoretical proofs of the convergence of ξ-learning to the optimal policy and for a guarantee of its transfer learning performance under the GPI procedure.
• We experimentally compare ξ-learning in tasks with linear and general reward functions, and for tasks with discrete and continuous features to standard Q-learning and the classical SF framework, demonstrating the interest and advantage of ξ-learning.

heading: 2 BACKGROUND

heading: 2.1 REINFORCEMENT LEARNING
text: RL investigates algorithms to solve multi-step decision problems, aiming to maximize the sum over future rewards (Sutton and Barto, 2018). RL problems are modeled as Markov Decision Processes (MDPs) which are defined as a tuple M ≡ (S,A, p, R, γ), where S and A are the state and action set. An agent transitions from a state st to another state st+1 using action at at time point t collecting a reward rt: st
at,rt−−−→ st+1. This process is stochastic and the transition probability p(st+1|st, at) describes which state st+1 is reached. The reward function R defines the scalar reward rt = R(st, at, st+1) ∈ R for the transition. The goal in an MDP is to maximize the expected return Gt = E [∑∞ k=0 γ kRt+k ] , where Rt = R(St, At, St+1). The discount factor γ ∈ [0, 1) weights collected rewards by discounting future rewards stronger. RL provides algorithms to learn a policy π : S → A defining which action to take in which state to maximise Gt. Value-based RL methods use the concept of value functions to learn the optimal policy. The stateaction value function, called Q-function, is defined as the expected future return taking action at in st and then following policy π:
Qπ(st, at) = Eπ { rt + γrt+1 + γ 2rt+2 + . . . } = Eπ { rt + γmax
at+1 Qπ(St+1, at+1)
} . (1)
The Q-function can be recursively defined following the Bellman equation such that the current Q-value Qπ(st, at) depends on the maximum Q-value of the next state Qπ(st+1, at+1). The optimal policy for an MDP can then be expressed based on the Q-function, by taking at every step the maximum action: π∗(s) ∈ argmaxaQ∗(s, a). The optimal Q-function can be learned using a temporal difference method such as Q-learning (Watkins and Dayan, 1992). Given a transition (st, at, rt, st+1), the Q-value is updated according to:
Qk+1(st, at) = Qk(st, at) + αk ( rt + max
at+1 Qk(st+1, at+1)−Qk(st, at)
) , (2)
where αk ∈ (0, 1] is the learning rate at iteration k.

heading: 2.2 TRANSFER LEARNING AND THE SF&GPI FRAMEWORK
text: We are interested in the transfer learning setting where the agent has to solve a set of tasksM = {M1,M2, . . . ,Mm}, that in our case differ only in their reward function. The Successor Feature (SF) framework provides a principled way to perform transfer learning (Barreto et al., 2017; 2018). SF assumes that the reward function can be decomposed into a linear combination of features φ ∈ Φ ⊂ Rn and a reward weight vector wi ∈ Rn that is defined for a task Mi:
ri(st, at, st+1) ≡ φ(st, at, st+1)>wi . (3)
We refer to such reward functions as linear reward functions. Since the various tasks differ only in their reward functions, the features are the same for all tasks inM. Given the decomposition above, it is also possible to rewrite the Q-function into an expected discounted sum over future features ψπi(s, a) and the reward weight vector wi:
Qπii (s, a) = E { rt + γ 1rt+1 + γ 2rt+2 + . . . } = E { φ>t wi + γ 1φ>t+1wi + γ 2φ>t+2wi + . . . } = E {∑∞ k=0 γ kφt+k }>
wi ≡ ψπi(s, a)>wi . (4)
This decouples the dynamics of the policy πi in the feature space of the MDP from the expected rewards for such features. Thus, it is now possible to evaluate the policy πi in a different taskMj using a simple multiplication of the weight vector wj with the ψ-function: Qπij (s, a) = ψ
πi(s, a)>wj . Interestingly, the ψ function also follows the Bellman equation:
ψπ(s, a) = E {φt+1 + γψπ(st+1, π(st+1))|st, at} , (5)
and can therefore be learned with conventional RL methods. Moreover, (Lehnert and Littman, 2019) showed the equivalence of SF-learning to Q-learning.
Being in a new task Mj the Generalized Policy Improvement (GPI) can be used to select the action over all policies learned so far that behaves best:
π(s) ∈ argmax a max i Qπij (s, a) = argmax a max i ψπi(s, a)>wj . (6)
(Barreto et al., 2018) proved that under the appropriate conditions for optimal policy approximates, the policy constructed in (6) is close to the optimal one, and their difference is upper-bounded:
||Q∗ −Qπ||∞ ≤ 2
1− γ
( ||r − ri||∞ + min
j ||ri − rj ||∞ +
) , (7)
where ‖f − g‖∞ = maxs,a |f(s, a)− g(s, a)|. For an arbitrary reward function r the result can be interpreted in the following manner. Given the arbitrary task M , we identify the theoretically closest possible linear reward task Mi with ri. For this theoretically closest task, we search the linear task Mj in our set of taskM (from which we also construct the GPI optimal policy (6)) which is closest to it. The upper bound between Q∗ and Q is then defined by 1) the difference between task M and the theoretically closest possible linear task Mi: ||r− ri||∞; and by 2) the difference between theoretical task Mi and the closest task Mj : minj ||ri − rj ||∞. If our new task M is also linear then r = ri and the first term in (7) would vanish.
Very importantly, this result shows that the SF framework will only provide a good approximation of the true Q-function if the reward function in a task can be represented using a linear decomposition. If this is not the case then the error in the approximation increases with the distance between the true reward function r and the best linear approximation of it ri as stated by ||r − ri||∞.
3 METHOD: ξ-LEARNING
3.1 DEFINITION AND FOUNDATIONS OF ξ-LEARNING
The goal of this paper is to investigate the application of SF&GPI to tasks with general reward functions R : Φ 7→ R over state features φ ∈ Φ:
r(st, at, st+1) ≡ R(φ(st, at, st+1)) = R(φt) , (8)
where we define φt ≡ φ(st, at, st+1). Under this assumption the Q-function can not be linearly decomposed into a part that describes feature dynamics and one that describes the rewards as in the linear SF framework (4). To overcome this issue, we propose to define the expected cumulative discounted probability of successor features or ξ-function, which is going to be the central mathematical object of the paper, as:
ξπ(s, a, φ) = ∞∑ k=0 γkp(φt+k = φ|st = s, at = a;π) , (9)
where p(φt+k = φ|st = s, at = a;π), or in short p(φt+k = φ|st, at;π), is the probability density function of the features at time t+ k, following policy π and conditioned to s and a being the state and action at time t respectively. Note that ξπ depends not only on the policy π but also on the state transition (constant through the paper). With the definition of the ξ-function, the Q-function rewrites (this is compatible with SFQL in the linear reward case, see Appendix A.6):
Qπ(st, at) = ∞∑ k=0 γkEp(φt+k|st,at;π) {R(φt+k)} = ∞∑ k=0 γk ∫ Φ p(φt+k = φ|st, at;π)R(φ)dφ
= ∫ Φ R(φ) ∞∑ k=0 γkp(φt+k = φ|st, at;π)dφ = ∫ Φ R(φ)ξπ(st, at, φ)dφ .
(10)
Depending on the reward function R, there are several ξ-functions that correspond to the same Q function. Formally, this is an equivalence relationship, and the quotient space has a one-to-one correspondence with the Q-function space. Proposition 1. (Equivalence between functions ξ and Q) Let Q = {Q : S ×A → R s.t. ‖Q‖∞ < ∞}. Let ∼ be defined as ξ1 ∼ ξ2 ⇔ ∫ Φ Rξ1 = ∫ Φ Rξ2. Then, ∼ is an equivalence relationship, and there is a bijective correspondence between the quotient space Ξ∼ and Q. Corollary 1. The bijection between Ξ∼ and Q allows to induce a norm ‖ · ‖∼ into Ξ∼ from the supremum norm in Q, with which Ξ∼ is a Banach space (since Q is Banach with ‖ · ‖∞):
‖ξ‖∼ = sup s,a ∣∣∣∣∫ Φ R(φ)ξ(s, a, φ)dφ ∣∣∣∣ = sup s,a |Q(s, a)| = ‖Q‖∞ . (11)
Similar to the Bellman equation for the Q-function, we can define a Bellman operator for the ξ-function, denoted by Tξ, as:
Tξ(ξ π) = p(φt = φ|st, at) + γEp(st+1,at+1|st,at;π) {ξ π(st+1, at+1, φ)} . (12)
As in the case of the Q-function, we can use Tξ to construct a contractive operator: Proposition 2. (ξ-learning has a fixed point) The operator Tξ is well-defined w.r.t. the equivalence ∼, and therefore induces an operator T∼ defined over Ξ∼. T∼ is contractive w.r.t. ‖ · ‖∼. Since Ξ∼ is Banach, T∼ has a unique fixed point and iterating T∼ starting anywhere converges to that point.
In other words, successive applications of the operator T∼ converge towards the class of optimal ξ functions [ξ∗] or equivalently to an optimal ξ function defined up to an additive function k satisfying∫
Φ k(s, a, φ)R(φ)dφ = 0,∀(s, a) ∈ S ×A (i.e. k ∈ Ker(ξ → ∫ Φ Rξ)).
While these two results state (see Appendix A for the proofs) the theoretical links to standard Q-learning formulations, the Tξ operator defined in (12) is not usable in practice, because of the expectation. In the next section, we define the optimisation iterate, prove its convergence, and provide two variants to perform the ξ updates.
3.2 ξ-LEARNING ALGORITHMS
In order to learn the ξ-function, we introduce the ξ-learning update operator, which is an offpolicy temporal difference method analogous to Q-learning. Given a transition (st, at, st+1, φt) the ξ-learning update operator is defined as:
ξπk+1(st, at, φ)← ξπk (st, at, φ) + αk [p(φt = φ|st, at) + γξπk (st+1, āt+1, φ)− ξπk (st, at, φ)] , (13) where āt+1 = argmaxa ∫ Φ R(φ)ξπ(st+1, a, φ)dφ.
The following is one of the main results of the manuscript, stating the convergence of ξ-learning:
Theorem 1. (Convergence of ξ-learning) For a sequence of state-action-feature {st, at, st+1, φt}∞t=0 consider the ξ-learning update given in (13). If the sequence of state-action-feature triples visits each state, action infinitely often, and if the learning rate αk is an adapted sequence satisfying the Robbins-Monro conditions:
∞∑ k=1 αk =∞, ∞∑ k=1 α2k <∞ (14)
then the sequence of function classes corresponding to the iterates converges to the optimum, which corresponds to the optimal Q-function to which standard Q-learning updates would converge to:
[ξn]→ [ξ∗] with Q∗(s, a) = ∫
Φ
R(φ)ξ∗(s, a, φ)dφ. (15)
The proof is provided in Appendix A and follows the same flow as for Q-learning.
The previous theorem provides convergence guarantees under the assumption that either p(φt = φ|st, at;π) is known, or an unbiased estimate can be constructed. We propose two different ways to approximate p(φt = φ|st, at;π) from a given transition (st, at, st+1, φt) so as to perform the ξ-update (13). The first instance is a model-free version and detailed in the following section. A second instance uses a one-step SF model, called One-Step Model-based (MB) ξ-learning, which is further described in Sec. B.
Model-free (MF) ξ-Learning: MF ξ-learning uses the same principle as standard model-free temporal difference learning methods. The update assumes for a given transition (st, at, st+1, φt) that the probability for the observed feature is p(φ = φt|st, at) = 1. Whereas for all other features (∀φ′ ∈ Φ, φ′ 6= φt) the probability is p(φ′ = φt|st, at) = 0, see Appendix D for continuous features. The resulting updates are:
φ = φt : ξ π(st, at, φ) ← (1− α)ξπ(st, at, φ) + α (1 + γξπ(st+1, āt+1, φ))
φ′ 6= φt : ξπ(st, at, φ′) ← (1− α)ξπ(st, at, φ′) + αγξπ(st+1, āt+1, φ′) . (16)
Due to the stochastic update of the ξ-function and if the learning rate α ∈ (0, 1] discounts over time, the ξ-update will learn the true probability of p(φ = φt|st, at). A potential problem with the MF procedure is that it might induce a high variance when the true feature probabilities are not binary.
3.3 META ξ-LEARNING
After discussing ξ-learning on a single task and showing its theoretical convergence, we can now investigate how it can be applied in transfer learning. Similar to the linear SF framework the ξ-function allows to reevaluate a policy learned for task Mi, ξπi , in a new environment Mj :
Qπij (s, a) = ∫ Φ Rj(φ)ξ πi(s, a, φ)dφ. (17)
This allows us to apply GPI in (6) for arbitrary reward functions in a similar manner to what was proposed for linear reward functions in (Barreto et al., 2018). We extend the GPI result to the ξ-learning framework as follows: Theorem 2. (Generalised policy improvement in ξ-learning) LetM be the set of tasks, each one associated to a (possibly different) weighting function Ri ∈ L1(Φ). Let ξπ ∗ i be a representative of the optimal class of ξ-functions for task Mi, i ∈ {1, . . . , I}, and let ξ̃πi be an approximation to the optimal ξ-function, ‖ξπ∗i − ξ̃πi‖Ri ≤ ε,∀i. Then, for another task M with weighting function R, the policy defined as:
π(s) = arg max a max i ∫ Φ R(φ)ξ̃πi(s, a, φ)dφ, (18)
satisfies:
‖ξ∗ − ξπ‖R ≤ 2
1− γ (min i ‖R−Ri‖p(φ|s,a) + ε), (19) where ‖f‖g = sups,a ∫ Φ |f · g| dφ.
The proof is provided in Appendix A.

heading: 4 EXPERIMENTS
text: We evaluated ξ-learning in two environments. The first has discrete features. It is a modified version of the object collection task by Barreto et al. (2017) having more complex features to allow general reward functions. See Appendix E.1 for experimental results in the original environment. The second environment, the racer environment, evaluates the agents in tasks with continuous features.

heading: 4.1 DISCRETE FEATURES - OBJECT COLLECTION ENVIRONMENT
text: Environment: The environment consist of 4 rooms (Fig. 1 - a). The agent starts an episode in position S and has to learn to reach the goal position G. During an episode, the agent can collect objects to gain further rewards. Each object has 2 properties: 1) color: orange or blue, and 2) form: box or triangle. The state space is a high-dimensional vector s ∈ R112. It encodes the agent’s position using a 10 × 10 grid of two-dimensional Gaussian radial basis functions. Moreover, it includes a memory about which object has been already collected. Agents can move in 4 directions. The features φ ∈ Φ = {0, 1}5 are binary vectors. The first 2 dimensions encode if an orange or a blue object was picked up. The 2 following dimensions encode the form. The last dimension encodes if the agent reached goal G. For example, φ> = [1, 0, 1, 0, 0] encodes that the agent picked up an orange box.
Tasks: Each agent learns sequentially 300 tasks which differ in their reward for collecting objects. We compared agents in two settings: either in tasks with linear or general reward functions. For each linear taskMi, the rewards r = φ>wi are defined by a linear combination of features and a weight vector wi ∈ R5. The weightswi,k for the first 4 dimensions define the rewards for collecting an object with a specific property. They are randomly sampled from a uniform distribution: wi,k ∼ U(−1, 1). The final weight defines the reward for reaching the goal position which is wi,5 = 1 for each task. The general reward functions are sampled by assigning a different reward to each possible combination of object properties φj ∈ Φ using uniform sampling: Ri(φj) ∼ U(−1, 1), such that picking up an orange box might result in a reward of Ri(φ> = [1, 0, 1, 0, 0]) = 0.23.
Agents: We compared ξ-learning to Q-learning (QL), and classical SF Q-learning (SFQL) (Barreto et al., 2017). All agents use function approximation for their state-action functions (Q, ψ, or ξfunction). An independent linear mapping is used to map the values from the state for each of the 4 actions. As the features are discrete, the ξ-function and p̂φ-model are approximated by an independent mapping for each action and possible feature φ ∈ Φ. The Q-value Q(s, a) for the ξ-agents (Eq. 10) is computed by: Qπ(s, a) = ∑ φ∈ΦR(φ)ξ
π(s, a, φ). The reward functions of each task are given to the ξ-agents. For SFQL, the sampled reward weights wi were given in tasks with linear reward functions. For general reward functions, a linear model r = φ>w̃i approximating the rewards was learned for each task and its weights w̃i given to SFQL (see Appendix C.3 for details). Each tasks was executed for 20, 000 steps, and the average performance over 10 runs per algorithm was measured. We performed a grid-search over the parameters of each agent, reporting here the performance of the parameters with the highest total reward over all tasks.
Results: ξ-learning outperformed SFQL and QL for tasks with linear and general reward functions (Fig. 1 - b; d). MF showed a slight advantage over MB ξ-learning in both settings. We further studied the effect non-linearity of general reward functions on the performance of classical SF compared to ξ-learning by evaluating them in tasks with different levels of non-linearity. We sampled general reward functions that resulted in different levels of mean absolute model error if they are linearly approximated with minw̃ |r(φ) − φ>w̃|. We trained SFQL and MF ξ-learning in each of these conditions on 300 tasks and measured the ratio between the total return of SFQL and MF ξ (Fig. 1). The relative performance of SFQL compared to MF ξ reduces with higher non-linearity of the reward functions. For reward functions that are nearly linear (mean error of 0.125), both have a similar performance. Whereas, for reward functions that are difficult to model with a linear relation (mean error of 1.625) SFQL reaches only less than 50% of the performance of ξ-learning. This follows SFQL’s theoretical limitation in (7) and shows the advantage of ξ learning over SFQL in non-linear reward tasks.

heading: 4.2 CONTINUOUS FEATURES - RACER ENVIRONMENT
text: Environment and Tasks: We further evaluated the agents in an environment with continuous features (Fig. 2 - a). The agent is randomly placed in the environment and has to drive around for 200 timesteps before the episode ends. Similar to a car, the agent has an orientation and momentum, so that it can only drive straight, or in a right or left curve. The agent reappears on the opposite side if it exits one side. The distance to 3 markers are provided as features φ ∈ R3. Rewards depend on the distances r = ∑3 k=1 rkφk, where each component rk has 1 or 2 preferred distances defined by Gaussian functions. For each of the 37 tasks, the number of Gaussians and their properties (µ, σ) are randomly sampled for each feature dimension. Fig. 2 (a) shows a reward function with dark areas depicting higher rewards. The agent has to learn to drive around in such a way as to maximize its trajectory over positions with high rewards. The state space is a high-dimensional vector s ∈ R120 encoding the agent’s position and orientation. As before, the 2D position is encoded using a 10× 10 grid of two-dimensional Gaussian radial basis functions. Similarly, the orientation is also encoded using 20 Gaussian radial basis functions.
Agents: We introduce a MF ξ-agent for continuous features (CMF ξ) (Appendix D.2.3). CMF ξ discretizes each feature dimension φk ∈ [0, 1] in 11 bins with the bin centers: X = {0.0, 0.1, . . . , 1.0}. It learns for each dimension k and bin i the ξ-value ξπk (s, a,Xi). Q-values (Eq. 10) are computed by: Qπ(s, a) = ∑3 k=1 ∑11 i=1 rk(Xi)ξ π k (s, a,Xi). SFQL learns ψ for the continuous, non-discretized feature space. It received an approximated weight vector w̃i that was trained before the task started on several uniformly sampled features and rewards.
Results: ξ-learning reached the highest performance of all agents (Fig. 2 - b) outperforming QL and SFQL. SFQL reaches only a low performance below QL, because it is not able to sufficiently well approximate the general reward functions with its linear reward model. This shows the advantage of ξ-learning over SFQL in environments with general reward functions.

heading: 5 DISCUSSION
text: Performance of ξ-learning compared to classical SF&GPI: ξ-learning allows to disentangle the dynamics of policies in the feature space of a task from the associated reward, see (10). The experimental evaluation in tasks with general reward functions (Fig. 1 - d, and Fig. 2) shows that ξ-learning can therefore successfully apply GPI to transfer knowledge from learned tasks to new ones. Given a general reward function it can re-evaluate successfully learned policies for knowledge transfer. Instead, classical SFQL based on a linear decomposition (3) can not be directly applied given a general reward function. In this case a linear approximation has to be learned which shows inferior performance to ξ-learning that directly uses the true reward function.
ξ-learning also shows an increased performance over SFQL in environments with linear reward functions (Fig. 1 - a). This effect can not be attributed to differences in their computation of a policy’s expected return as both are correct (Appendix A.6). A possible explanation is that ξ-learning reduces the complexity for the function approximation of the ξ-function compared to the ψ-function in SFQL.
Continuous Feature Spaces: For tasks with continuous features (racer environment), ξ-learning used successfully a discretization of each feature dimension, and learned the ξ-values independently for each dimension. This strategy is viable for reward functions that are cumulative over the feature dimensions: r(φ) = ∑ k rkφk. The Q-value can be computed by summing over the independent
dimensions and the bins X: Qπ(s, a) = ∑ k ∑ x∈X rk(x)ξ
π(s, a, x). For more general reward functions, the space of all feature combinations would need to be discretized, which grows exponentially with each new dimension. As a solution the ξ-function could be directly defined over the continuous feature space, but this yields some problems. First, the computation of the expected return requires an integral Q(s, a) = ∫ φ∈ΦR(φ)ξ(s, a, φ) over features instead of a sum, which is a priori intractable. Second, the representation and training of the ξ-function, which would be defined over a continuum thus increasing the difficulty of approximating the function. Janner et al. (2020) and Touati and Ollivier (2021) propose methods that might allow to represent a continuous ξ-function, but it is unclear if they converge and if they can be used for transfer learning.
Learning of Features: In principle, classical SF&GPI can also optimize general reward functions if features and reward weights are learned. This is possible if the learned features describe the non-linear effects in the reward functions. Nonetheless, learning of features adds further challenges and shows to reduce performance. Barreto et al. (2017) learns features from observations sampled from several tasks before the SF&GPI starts. Therefore, novel non-linearities potentially introduced at later tasks are not well represent by the learned features. If instead features are learned alongside the SF&GPI procedure, the problem on how to coordinate both learning processes needs to be investigated. Importantly, ψ-functions for older tasks would become unusable for the GPI procedure on newer task, because the feature representation changed between them.
Moreover, our replication (Sec. E.1) of the object collection task from Barreto et al. (2017) shows the performance of learned features is below the performance of given features. MF Xi reaches a final average reward per task of 850 with given features and reward functions. The best performance of SFQL with learned features only reaches a final performance of 575 (Fig. 2 in (Barreto et al., 2017)).
In summary, if features and reward functions are known then ξ-learning outperforms SFQL. And using given features and reward functions is natural for many applications as these are often known, for example in robotic tasks where they are usually manually designed (Akalin and Loutfi, 2021).
Computational Complexity: The improved performance of SFQL and ξ-learning over QL in the transfer learning setting comes at the cost of an increased computational complexity. The GPI procedure (6) of both approaches requires to evaluate at each step the ψπi-function or ξπi-function over all previous experienced tasks inM. As a consequence, the computational complexity increases linearly with each new environment that is added. A solution is to apply GPI only over a subset of learned policies. Nonetheless, an open question is still how to optimally select this subset.

heading: 6 RELATED WORK
text: Transfer Learning: Transfer methods in RL can be generally categorized according to the type of tasks between which transfer is possible and the type of transferred knowledge (Taylor and Stone, 2009; Lazaric, 2012; Zhu et al., 2020). In the case of SF&GPI which ξ-learning is part of, tasks only differ in their reward functions. The type of knowledge that is transferred are policies learned in source tasks which are re-evaluated in the target task and recombined using the GPI procedure. A natural use-case for ξ-learning are continual problems (Khetarpal et al., 2020) where an agent has continually adapt to changing tasks, which are in our setting different reward functions.
Successor Features: SF are based on the concept of successor representations (Dayan, 1993; Momennejad, 2020). Successor representations predict the future occurrence of all states for a policy in the same manner as SF for features. Their application is restricted to low-dimensional state spaces using tabular representations. SF extended them to domains with high-dimensional state spaces (Kulkarni et al., 2016; Zhang et al., 2017; Barreto et al., 2017; 2018), by predicting the future occurrence of low-dimensional features that are relevant to define the return. Several extensions to the SF framework have been proposed. One direction aims to learn appropriate features from data such as by optimally reconstruct rewards (Barreto et al., 2017), using the concept of mutual information (Hansen et al., 2019), or the grouping of temporal similar states (Madjiheurem and Toni, 2019). Another direction is the generalization of the ψ-function over policies (Borsa et al., 2018) analogous to universal value function approximation (Schaul et al., 2015). Similar approaches use successor maps (Madarasz, 2019), goal-conditioned policies (Ma et al., 2020), or successor feature sets (Brantley et al., 2021). Other directions include their application to POMDPs (Vértes and Sahani, 2019), combination with max-entropy principles (Vertes, 2020), or hierarchical RL (Barreto et al., 2021). In difference to ξ-learning all these approaches build on the assumption of linear reward functions, whereas ξ-learning allows the SF&GPI framework to be used with general reward functions. Nonetheless, most of the extensions for linear SF can be combined with ξ-learning.
Model-based RL: SF represent the dynamics of a policy in the feature space that is decoupled from the rewards allowing to reevaluate them under different reward functions. It shares therefore similar properties with model-based RL (Lehnert and Littman, 2019). In general, model-based RL methods learn a one-step model of the environment dynamics p(st+1|st, at). Given a policy and an arbitrary reward function, rollouts can be performed using the learned model to evaluate the return. In practice, the rollouts have a high variance for long-term predictions rendering them ineffective. Recently, (Janner et al., 2020) proposed the γ-model framework that learns to represent ξ-values in continuous domains. Nonetheless, the application to transfer learning is not discussed and no convergence is proven as for ξ-learning. This is the same case for the forward-backward MPD representation proposed in Touati and Ollivier (2021). (Tang et al., 2021) also proposes to decouple the dynamics in the state space from the rewards, but learn an internal representation of the rewards. This does not allow to reevaluate an policy to a new reward function without relearning the mapping.

heading: 7 CONCLUSION
text: The introduced ξ-learning framework learns the expected cumulative discounted probability of successor features which disentangles the dynamics of a policy in the feature space of a task from the expected rewards. This allows ξ-learning to reevaluate the expected return of learned policies for general reward functions and to use it for transfer learning utilizing GPI. We proved that ξ-learning converges to the optimal policy, and showed experimentally its improved performance over Q-learning and the classical SF framework for tasks with linear and general reward functions.

heading: ETHICS STATEMENT
text: ξ-learning and its associated optimization algorithms represent general RL procedures similar to Q-learning. Their potential negative societal impact depends on their application domains which range over all possible societal areas in a similar manner as for other general RL procedures.
Beyond the topic of the paper, we did our best to cite the relevant literature and to fairly compare with previous ideas, concepts and methods. To that aim, all agents are trained and evaluated within the same software environment, and under the very same experimental settings.

heading: REPRODUCIBILITY STATEMENT
text: In order to ensure high changes of reproducibility we provided lots of details of the method and experiments associated to the paper. In particular, we have provided the proofs for all mathematical results announced in the main paper (see Appendix A). These constitute the theoretical foundation of the proposed ξ-learning methodology. Secondly, we have provided all experimental details (methods, and environments) required for reproducing our experiments, namely: appendix C for the object collection and D for the racer environment respectively. In addition, we provide additional results in appendix E, to completely illustrate the interest of the proposed method. Finally, we provided an anonymous link to the source code, so that reviewers can run it if necessary.

heading: A THEORETICAL PROOFS

heading: A.1 PROOF OF PROPOSITION 1
text: Let us start by recalling the original statement in the main paper.
Proposition 1. (Equivalence between functions ξ and Q) Let Q = {Q : S ×A → R s.t. ‖Q‖∞ < ∞}. Let ∼ be defined as ξ1 ∼ ξ2 ⇔ ∫ Φ Rξ1 = ∫ Φ Rξ2. Then, ∼ is an equivalence relationship, and there is a bijective correspondence between the quotient space Ξ∼ and Q.
Proof. We will proof the statements sequentially.
∼ is an equivalence relationship: To prove this we need to demonstrate that ∼ is symmetric, reciprocal and transitive. The three are quite straightforward since: ξ ∼ ξ,∀ξ, ξ ∼ η ⇔ η ∼ ξ,∀ξ, η and ξ ∼ η, η ∼ ν ⇒ ξ ∼ ν.
Bijective correspondence: To prove the bijectivity, we will first prove that it is injective, then surjective. Regarding the injectivity: [ξ] 6= [η]⇒ Qξ 6= Qη , we prove it by contrapositive:
Qξ = Qη ⇒ ∫
Φ
R(φ)ξ(s, a, φ)dφ = ∫
Φ
R(φ)η(s, a, φ)dφ⇒ [ξ] = [η]. (20)
In order to prove the surjectivity, we start from a function Q ∈ Q and select an arbitrary ξ ∈ Ξ, then the following function:
ξQ(s, a, φ) = Q(s, a)∫
Φ R(φ̄)ξ(s, a, φ̄)dφ̄
ξ(s, a, φ) (21)
satisfies that ξQ ∈ Ξ and that ∫ Φ R(φ)ξQ(s, a, φ)dφ = Q(s, a),∀(s, a) ∈ S ×A. We conclude that there is a bijective correspondence between the elements of Ξ∼ and of Q.

heading: A.2 PROOF OF COROLLARY 1
text: Let us recall the result:
Corollary 1. The bijection between Ξ∼ and Q allows to induce a norm ‖ · ‖∼ into Ξ∼ from the supremum norm in Q, with which Ξ∼ is a Banach space (since Q is Banach with ‖ · ‖∞):
‖ξ‖∼ = sup s,a ∣∣∣∣∫ Φ R(φ)ξ(s, a, φ)dφ ∣∣∣∣ = sup s,a |Q(s, a)| = ‖Q‖∞ , (22)
Proof. The norm induced in the quotient space is defined from the correspondence between Ξ∼ and Q and is naturally defined as in the previous equation. The norm is well defined since it does not depend on the class representative. Therefore, all the metric properties are transferred, and Ξ∼ is immediately Banach with the norm ‖ · ‖∼.

heading: A.3 PROOF OF PROPOSITION 2
text: Let’s restate the result:
Proposition 2. (ξ-learning has a fixed point) The operator Tξ is well-defined w.r.t. the equivalence ∼, and therefore induces an operator T∼ defined over Ξ∼. T∼ is contractive w.r.t. ‖ · ‖∼. Since Ξ∼ is Banach, T∼ has a unique fixed point and iterating T∼ starting anywhere converges to that point.
Proof. We prove the statements above one by one:
The operator T∼ is well defined: Let us first recall the definition of the operator Tξ in (12), where we removed the dependency on π for simplicity:
Tξ(ξ) = p(φt = φ|st, at) + γEp(st+1,at+1|st,at) {ξ(st+1, at+1, φ)}
Let ξ1, ξ2 ∈ [ξ] two different representatives of class [ξ], we can write:∫ Φ R(φ)(Tξ(ξ1)(s, a, φ)− Tξ(ξ2)(s, a, φ))dφ
= ∫ Φ R(φ) ∫ S p(s′, a′|s, a)γ(ξ1(s′, a′, φ)− ξ2(s′, a′, φ))ds′dφ
= γ ∫ S p(s′, a′|s, a) ∫ Φ R(φ)(ξ1(s ′, a′, φ)− ξ2(s′, a′, φ))dφds′
= 0
(23)
because ξ1, ξ2 ∈ [ξ]. Therefore the operator T∼([ξ]) = Tξ(ξ) is well defined in the quotient space, since the image of class does not depend on the function chosen to represent the class.
Contractive operator T∼: The contractiveness of T∼ can be proven directly:
‖T∼([ξ])− T∼([η])‖∼ = sup s,a ∣∣∣∣∣ ∫
Φ
R(φ) ( p(φ|s, a) + γEp(s′,a′|s,a){ξ(s′, a′, φ)}
−p(φ|s, a)− γEp(s′,a′|s,a){η(s′, a′, φ)} ) dφ ∣∣∣∣∣ =γ sup
s,a ∣∣∣∣∫ Φ R(φ)Ep(s′,a′|s,a){ξ(s′, a′, φ)− η(s′, a′, φ)}dφ ∣∣∣∣
=γ sup s,a Ep(s′,a′|s,a) {∣∣∣∣∫ Φ R(φ)(ξ(s′, a′, φ)− η(s′, a′, φ))dφ ∣∣∣∣}
≤γ sup s′,a′ ∣∣∣∣∫ Φ R(φ)(ξ(s′, a′, φ)− η(s′, a′, φ))dφ ∣∣∣∣
=γ‖[ξ]− [η]‖∼
(24)
The contractiveness of T∼ can also be understood as being inherited from the standard Bellmann operator on Q. Indeed, given a ξ function, one can easily see that applying the standard Bellman operator to the Q function corresponding to ξ leads to the Q function corresponding to T∼([ξ]).
Fixed point of T∼: To conclude the proof, we use the fact that any contractive operator on a Banach space, in our case: T∼ : Ξ∼ → Ξ∼ has a unique fixed point [ξ∗], and that for any starting point [ξ0], the sequence [ξn] = T∼([ξn−1]) converges to [ξ∗] w.r.t. to the corresponding norm ‖[ξ]‖∼.

heading: A.4 PROOF OF THEOREM 1
text: These two propositions will be useful to prove that the ξ learning iterates converge in Ξ∼. Let us restate the definition of the operator from (13):
ξπk+1(st, at, φ)← ξπk (st, at, φ) + αk [p(φt = φ|st, at;π) + γξπk (st+1, āt+1, φ)− ξπk (st, at, φ)]
and the theoretical result:
Theorem 1. (Convergence of ξ-learning) For a sequence of state-action-feature {st, at, st+1, φt}∞t=0 consider the ξ-learning update given in (13). If the sequence of state-action-feature triples visits each state, action infinitely often, and if the learning rate αk is an adapted sequence satisfying the Robbins-Monro conditions:
∞∑ k=1 αk =∞, ∞∑ k=1 α2k <∞ (25)
then the sequence of function classes corresponding to the iterates converges to the optimum, which corresponds to the optimal Q-function to which standard Q-learning updates would converge to:
[ξn]→ [ξ∗] with Q∗(s, a) = ∫
Φ
R(φ)ξ∗(s, a, x)dφ. (26)
Proof. The proof re-uses the flow of the proof used for Q-learning (Tsitsiklis, 1994). Indeed, we rewrite the operator above as:
ξπk+1(st, at, φ)← ξπk (st, at, φ) + αk [Tξ(ξπk )(st, at, φ)− ξπk (st, at, φ) + ε(st, at, φ)] with ε defined as:
ε(st, at, φ) = p(φt = φ|st, at;π) + γξπk (st+1, āt+1, φ) −E {p(φt = φ|st, at;π) + γξπk (st+1, āt+1, φ)} .
Obviously ε satisfies E{ε} = 0, which, together with the contractiveness of T∼, is sufficient to demonstrate the convergence of the iterative procedure as done for Q-learning. In our case, the optimal function ξ∗ is defined up to an additive kernel function κ ∈ Ker. The correspondence with the optimal Q learning function is a direct application of the correspondence between the ξ- and Q-learning problems.

heading: A.5 PROOF OF THEOREM 2
text: Let us restate the result. Theorem 2. (Generalised policy improvement in ξ-learning) LetM be the set of tasks, each one associated to a (possibly different) weighting function Ri ∈ L1(Φ). Let ξπ ∗ i be a representative of the optimal class of ξ-functions for task Mi, i ∈ {1, . . . , I}, and let ξ̃πi be an approximation to the optimal ξ-function, ‖ξπ∗i − ξ̃πi‖Ri ≤ ε,∀i. Then, for another task M with weighting function R, the policy defined as:
π(s) = arg max a max i ∫ Φ R(φ)ξ̃πi(s, a, φ)dφ, (27)
satisfies:
‖ξ∗ − ξπ‖R ≤ 2
1− γ (min i ‖R−Ri‖p(φ|s,a) + ε), (28) where ‖f‖g = sups,a ∫ Φ |f · g| dφ.
Proof. The proof is stated in two steps. First, we exploit the proof of Proposition 1 of (Barreto et al., 2017), and in particular (13) that states:
‖Q∗ −Qπ‖∞ ≤ 2
1− γ ( sup s,a |r(s, a)− ri(s, a)|+ ε ) , ∀i ∈ {1, . . . , I}, (29)
where Q∗ and Qπ are the Q-functions associated to the optimal and π policies in the environment R. The conditions on the Q functions required in the original proposition are satisfied because the ξ-functions satisfy them, and there is an isometry between Q and ξ functions.
Because the above inequality is true for all training environments i, we can rewrite as:
‖Q∗ −Qπ‖∞ ≤ 2
1− γ ( min i sup s,a |r(s, a)− ri(s, a)|+ ε ) . (30)
We now realise that, in the case of ξ-learning, the reward functions rewrite as:
r(s, a) = ∫ Φ R(φ)p(φ|s, a)dφ ri(s, a) = ∫ Φ Ri(φ)p(φ|s, a)dφ, (31)
and therefore we have:
sup s,a |r(s, a)− ri(s, a)| = sup s,a ∣∣∣∣∫ Φ (R(φ)−Ri(φ))p(φ|s, a)dφ ∣∣∣∣
≤ sup s,a ∫ Φ |R(φ)−Ri(φ)| p(φ|s, a)dφ
= ‖R−Ri‖p(φ|s,a)
(32)
Similarly, due to the isometry between ξ and Q-learning, i.e. Proposition 2, we can write that:
‖ξ∗ − ξπ‖R = ‖[ξ∗]− [ξπ]‖∼ = ‖Q∗ −Qπ‖∞
≤ 2 1− γ ( min i sup s,a |r(s, a)− ri(s, a)|+ ε ) ≤ 2
1− γ (min i ‖R−Ri‖p(φ|s,a) + ε),
(33)
which proves the generalised policy improvement for ξ-learning.
A.6 RELATION BETWEEN CLASSICAL SF AND ξ-LEARNING FOR LINEAR REWARD FUNCTIONS
In the case of linear reward functions, i.e. where assumption (3) holds, it is possible to show that ξlearning can be reduced to classical SF. Classical SF represents therefore a specific case of ξ-learning under this assumption. Theorem 3. (Equality of classical SF and ξ-learning for linear reward functions) Given the assumption that reward functions are linearily decomposable with
ri(st, at, st+1) ≡ φ(st, at, st+1)>wi , where φ ∈ Rn are features for a transition and wi ∈ Rn are the reward weight vector of task mi ∈M, then the classical SF and ξ-learning framework are equivalent.
Proof. We start with the definition of the Q-value according to ξ-learning from (10). After replacing the reward function Ri with our linear assumption, the definition of the Q-function according to classical SF with the ψ-function can be recovered:
Qi(s, a) = ∫ Φ ξπ(st, at, φ)Ri(φ)dφ
= ∫ Φ ξπ(st, at, φ)φ >widφ
= w>i ∫ Φ ∞∑ k=0 γkp(φt+k = φ|st = s, at = a;π)φ dφ
= w>i ∞∑ k=0 γk ∫ Φ p(φt+k = φ|st = s, at = a;π)φ dφ
= w>i ∞∑ k=0 γkE {φt+k}
= E { ∞∑ k=0 γkφt+k }> wi = ψ(s, a) >wi .
Please note, although both methods are equal in terms of their computed values, how these are represented and learned differs between them. Thus, it is possible to see a performance difference of the methods in the experimental results where ξ-learning outperforms SFQL in our environments.
B ONE-STEP SF MODEL-BASED (MB) ξ-LEARNING
Besides the MF ξ-learning update operator (16), we introduce a second ξ-learning procedure called One-step SF Model-based (MB) ξ-Learning that attempts to reduce the variance of the update. To do so, MB ξ-learning estimates the distribution over the successor features over time. Let p̃(φt = φ|st, at;π) denote the current estimate of the feature distribution. Given a transition (st, at, st+1, φt) the model is updated according to:
φ = φt : p̃φ(φ|st, at;π) ← p̃φ(φ|st, at;π) + β (1− p̃φ(φ|st, at;π)) φ′ 6= φt : p̃φ(φ′|st, at;π) ← p̃φ(φ′|st, at;π)− βp̃φ(φ′|st, at;π) ,
where β ∈ [0, 1] is the learning rate. After updating the model p̃φ, it can be used for the ξ-update as defined in (13). Since the learned model p̃φ is independent from the reward function and from the policy, it can be learned and used over all tasks.

heading: C EXPERIMENTAL DETAILS: OBJECT COLLECTION ENVIRONMENT
text: The object collection environment (Fig. 1 - a) was briefly introduced in Section 4.1. This section provides a formal description.

heading: C.1 ENVIRONMENT
text: The environment is a continuous two-dimensional area in which the agent moves. The position of the agent is a point in the 2D space: (x, y) ∈ [0, 1]2. The action space of the agent consists of four movement directions: A = {up, down, left, right}. Each action changes the position of the agent in a certain direction and is stochastic by adding a Gaussian noise. For example, the action for going right updates the position according to xt+1 = xt +N (µ = 0.05, σ = 0.005). If the new position ends in a wall (black areas in Fig. 1 - a) that have a width of 0.04) or outside the environment, the agent is set back to its current position. Each environment has 12 objects. Each object has two properties with two possible values: color (orange, blue) and shape (box, triangle). If the agent reaches an object, it collects the object which then disappears. The objects occupy a circular area with radius 0.04. At the beginning of an episode the agent starts at location S with (x, y)S = (0.05, 0.05). An episode ends if the agent reaches the goal area G which is at position (x, y)G = (0.86, 0.86) and has a circular shape with radius 0.1. After an episode the agent is reset to the start position S and all collected objects reappear.
The state space of the agents consist of their position in the environment and the information about which objects they already collected during an episode. Following (Barreto et al., 2017), the position is encoded using a radial basis function approach. This upscales the agent’s (x, y) position to a high-dimensional vector spos ∈ R100 providing a better signal for the function approximation of the different functions such as the ψ or ξ-function. The vector spos is composed of the activation of two-dimensional Gaussian functions based on the agents position (x, y):
spos = exp
( − (x− cj,1) 2 + (y − cj,2)2
σ
) , (34)
where cj ∈ R2 is the center of the jth Gaussian. The centers are laid out on a regular 10× 10 grid over the area of the environment. The state also encodes the memory about the objects that the agent has already collected using a binary vector smem ∈ {0, 1}12. The jth dimension encodes if the jth object has been taken (smem,j = 1) or not (smem,j = 0). An additional constant term was added to the state to aid the function approximation. As a result, the state received by the agents is a column vector with s = [s>pos, s > mem, 1] > ∈ R113.
The features φ(st, at, st+1) ∈ {0, 1}5 in the environment describe the type of object that was collected by an agent during a step or if it reached the goal position. The first four feature dimensions encode binary the properties of a collected object and the last dimension if the goal area was reached. In total |Φ| = 6 possible features exists: φ1 = [0, 0, 0, 0, 0]>- standard observation, φ2 = [1, 0, 1, 0, 0]>- collected an orange box, φ3 = [1, 0, 0, 1, 0]>- collected an orange triangle, φ4 = [0, 1, 1, 0, 0]>- collected a blue box, φ5 = [0, 1, 0, 1, 0]>- collected a blue triangle, and φ6 = [0, 0, 0, 0, 1]>- reached the goal area.
Two types of tasks were evaluated in this environment that have either 1) linear or 2) general reward functions. 300 tasks, i.e. reward functions, were sampled for each type. For linear tasks, the rewards r = φ>wi are defined by a linear combination of discrete features φ ∈ N5 and a weight vector wi ∈ R5. The first four dimensions in wi define the reward that the agent receives for collecting objects having specific properties, e.g. being blue or being a box. The weights for each of the four dimensions are randomly sampled from a uniform distribution: wk∈[1,2,3,4] ∼ U(−1, 1) for each task. The final weight defines the reward for reaching the goal state which is w5 = 1 for each task. For training agents in general reward tasks, general reward functions Ri for each task Mi were sampled. These reward functions define for each of the four features (φ2, . . . , φ5) that represent the collection of a specific object type an individual reward. Their rewards were sampled from a uniform
distribution: Ri(φk∈{2,...,5}) ∼ U(−1, 1). The reward for collecting no object is Ri(φ1) = 0 and for reaching the goal area is Ri(φ6) = 1 for all tasks. Reward functions of this form can not be linearly decomposed in features and a weight vector.

heading: C.2 ALGORITHMS
text: This section introduces the details of each evaluated algorithm. First the common elements are discussed before introducing their specific implementations.
All agents experience the tasks M ∈ M of an environment sequentially. They are informed when a new task starts. All algorithms receive the features φ(s, a, s′) of the environment. For the action selection and exploration, all agents use a -greedy strategy. With probability ∈ [0, 1] the agent performs a random action. Otherwise it selects the action that maximizes the expected return.
As the state space (s ∈ R113) of the environments is high-dimensional and continuous, all agents use an approximation of their respective functions such as for the Q-function (Q̃(s, a) ≈ Q(s, a)) or the ξ-function (ξ̃(s, a, φ) ≈ ξ(s, a, φ)). We describe the general function approximation procedure on the example of ξ-functions. If not otherwise mentioned, all functions are approximated by a single linear mapping from the states to the function values. The parameters θξ ∈ R113×|A|×|Φ| of the mapping have independent components θξa,φ ∈ R113 for each action a ∈ A and feature φ ∈ Φ:
ξ̃(s, a, φ; θξ) = s>θξa,φ (35)
To learn ξ̃ we update the parameters θξ using stochastic gradient descent following the gradients ∇θξLξ(θξ) of the loss based on the ξ-learning update (13):
∀φ ∈ Φ : Lξ(θξ) = E {( p(φt = φ|st, at) + γξ̃(st+1, āt+1, φ; θ̄ξ)− ξ̃(st, at, φ; θξ) )2}
with āt+1 = argmax a ∑ φ∈Φ R(φ)ξ̃(st+1, a, φ; θ̄ ξ) , (36)
where θ̄ξ = θξ but θ̄ξ is treated as a constant for the purpose of calculating the gradients∇θξLξ(θξ). We used PyTorch2 for the computation of gradients and its stochastic gradient decent procedure (SGD) for updating the parameters.
C.2.1 QL
The Q-learning (QL) agent (Algorithm 1) represents standard Q-learning (Watkins and Dayan, 1992). The Q-function is approximated and updated using the following loss after each observed transition:
LQ(θQ) = E {( r(st, at, st+1) + γmax
at+1 Q̃(st+1, at+1; θ̄
Q)− Q̃(st, at; θQ) )2}
(37)
where θ̄Q = θQ but θ̄Q is treated as a constant for the purpose of optimization, i.e no gradients flow through it. Following (Barreto et al., 2017) the parameters θQ are reinitialized for each new task.
C.2.2 SFQL
The classical successor feature algorithm (SFQL) is based on a linear decomposition of rewards in features and reward weights (Barreto et al., 2017) (Algorithm 2). If the agent is learning the reward weights w̃i for a task Mi then they are randomly initialized at the beginning of a task. For the case of general reward functions and where the reward weights are given to the agents, the weights are learned to approximate a linear reward function before the task. See Section C.3 for a description of the training procedure. After each transition the weights are updated by minimizing the error between the predicted rewards φ(st, at, st+1)>w̃i and the observed reward rt:
Lwi(w̃i) = E {( r(s, a, s′)− φ(st, at, st+1)>w̃i )2} . (38)
2PyTorch v1.4: https://pytorch.org
Algorithm 1: Q-learning (QL) Input : exploration rate:
learning rate for the Q-function: α
for i← 1 to num_tasks do initialize Q̃: θQ ← small random initial values new_episode← true for t← 1 to num_steps do
if new_episode then new_episode← false st ← initial state
With probability select a random action at, otherwise at ← argmaxa Q̃(st, a) Take action at and observe reward rt and next state st+1 if st+1 is a terminal state then
new_episode← true γt ← 0
else γt ← γ
y ← rt + γt maxat+1 Q̃(st+1, at+1) Update θQ using SGD(α) with LQ = (y − Q̃(st, at))2 st ← st+1
SFQL learns an approximated ψ̃i-function for each task Mi. The parameters of the ψ̃-function for the first task θψ1 are randomly initialized. For consecutive tasks, they are initialized by copying them from the previous task (θψi ← θ ψ i−1). The ψ̃i-function of the current task Mi is updated after each observed transition with the loss based on (5):
Lψ(θψi ) = E {( φ(st, at, st+1) + γψ̃i(st+1, āt+1; θ̄ ψ i )− ψ̃i(st, at; θ ψ i ) )2}
with āt+1 = argmax a max k∈{1,2,...,i}
ψ̃k(st+1, a; θ̄ ψ k ) >w̃i ,
(39)
where θ̄ψi = θ ψ i but θ̄ ψ i is treated as a constant for the purpose of optimization, i.e no gradients flow through it. Besides the current ψ̃i-function, SFQL also updates the ψ̃c-function which provided the GPI optimal action for the current transition: c = argmaxk∈{1,2,...,i}maxb ψ̃k(s, b)
>w̃i. The update uses the same loss as for the update of the active ψ̃i-function (39), but instead of using the GPI optimal action as next action, it uses the optimal action according to its own policy: āt+1 = argmaxa ψ̃c(st+1, a) >w̃c
C.2.3 ξ-LEARNING
The ξ-learning agents (Algorithms 3, 4) allow to reevaluate policies in tasks with general reward functions. If the reward function is not given, an approximation R̃i of the reward function for each task Mi is learned. The parameters for the approximation are randomly initialized at the beginning of each task. After each observed transition the approximation is updated according to the following loss:
LR(θRi ) = E {( r(st, at, st+1)− R̃i(φ(st, at, st+1); θRi ) )2}
(40)
In the case of tasks with linear reward functions the reward approximation becomes R̃i(φ(st, at, st+1); θ R i ) = φ(st, at, st+1) >θRi . Thus with θ R i = w̃i we recover the same procedure as for SFQL (38). For non-linear, general reward functions we represented R̃ with a neural network. The input of the network is the feature φ(st, at, st+1). The network has one hidden layer with 10 neurons having ReLu activations. The output is a linear mapping to the scalar reward rt ∈ R.
All ξ-learning agents learn an approximation of the ξ̃i-function for each task Mi. Analogous to SFQL, the parameters of the ξ̃-function for the first task θξ1 are randomly initialized. For con-
Algorithm 2: Classical SF Q-learning (SFQL) (Barreto et al., 2017) Input : exploration rate:
learning rate for ψ-functions: α learning rate for reward weights w: αw features φ optional: reward weights for tasks: {w̃1, w̃2, . . . , w̃num_tasks}
for i← 1 to num_tasks do if w̃i not provided then w̃i ← small random initial values if i = 1 then initialize ψ̃i: θψi ← small random initial values else θ ψ i ← θ ψ i−1
new_episode← true for t← 1 to num_steps do
if new_episode then new_episode← false st ← initial state c← argmaxk∈{1,2,...,i}maxa ψ̃k(st, a)>w̃i // GPI optimal policy With probability select a random action at, otherwise at ← argmaxa ψ̃c(st, a)>w̃i Take action at and observe reward rt and next state st+1 Update w̃i using SGD(αw) with Lw = (rt − φ(st, at, st+1)>w̃i)2 if st+1 is a terminal state then
new_episode← true γt ← 0
else γt ← γ
// GPI optimal next action for task i āt+1 ← argmaxa argk∈{1,2,...,i} ψ̃k(st+1, a)>w̃i y ← φ(st, at, st+1) + γtψ̃i(st+1, āt+1) Update θψi using SGD(α) with Lψ = (y − ψ̃i(st, at))2 if c 6= i then
āt+1 ← argmaxa ψ̃c(st+1, a)>w̃c // optimal next action for task c
y ← φ(st, at, st+1) + γtψ̃c(st+1, āt+1) Update θψc using SGD(α) with Lψ = (y − ψ̃c(st, at))2
st ← st+1
secutive tasks, they are initialized by copying them from the previous task (θξi ← θ ξ i−1). The ξ̃i-function of the current task Mi is updated after each observed transition with the loss given in (46). The ξ-learning agents differ in their setting for p(φt = φ|st, at) in the updates which is described in the upcoming sections. Besides the current ξ̃i-function, the ξ-learning agents also update the ξ̃c-function which provided the GPI optimal action for the current transition: c = argmaxk∈{1,2,...,i}maxat ∑ φ∈Φ ξ̃k(st, at, φ)R̃i(φ). The update uses the same loss as for
the update of the active ξ̃i-function (46), but instead of using the GPI optimal action as next action, it uses the optimal action according to its own policy: āt+1 = maxa ∑ φ∈Φ ξ̃c(st+1, a, φ)R̃c(φ).
MF ξ-learning: The model-free ξ-learning agent (Algorithm 3) uses a stochastic update for the ξ̃functions. Given a transition, we set p(φt = φ|st, at) ≡ 1 for the observed feature φ = φ(st, at, st+1) and p(φt = φ|st, at) ≡ 0 for all other features φ 6= φ(st, at, st+1).
MB ξ-learning: The one-step SF model-based ξ-learning agent (Algorithm 4) uses an approximated model p̃ to predict p(φt = φ|st, at) to reduce the variance of the ξ-function update. The model is by
a linear mapping for each action. It uses a softmax activation to produce a valid distribution over Φ:
p̃(s, a, φ; θp) = exp(s>θpa,φ)∑
φ′∈Φ exp(s >θpa,φ′)
(41)
where θpa,φ ∈ R113. As p̃ is valid for each task inM, its weights θp are only randomly initialized at the beginning of the first task. For each observed transition, the model is updated using the following loss:
∀φ ∈ Φ : Lp(θpi ) = E { (p(φt = φ|st, at)− p̃(st, at, φ; θpi )) 2 } , (42)
where we set p(φt = φ|st, at) ≡ 1 for the observed feature φ = φ(st, at, st+1) and p(φt = φ|st, at) ≡ 0 for all other features φ 6= φ(st, at, st+1).

heading: C.3 EXPERIMENTAL PROCEDURE
text: All agents were evaluated in both task types (linear or general reward function) on 300 tasks. The agents experienced the tasks sequentially, each for 20.000 steps. The agents had knowledge when a task change happened. Each agent was evaluated for 10 repetitions to measure their average performance. Each repetition used a different random seed that impacted the following elements: a) the sampling of the tasks, b) the random initialization of function approximator parameters, c) the stochastic behavior of the environments when taking steps, and d) the -greedy action selection of the agents. The tasks, i.e. the reward functions, were different between the repetitions of a particular agent, but identical to the same repetition of a different agent. Thus, all algorithms were evaluated over the same tasks.
The SF agents (SFQL, ξ-learning) were evaluated under two conditions. First, that they have to learn the reward weights or the reward function online during the training (indicated by (O) in figures). Second, the reward weights or the reward function is given to them. As the SFQL does not support general reward functions, it is not possible to provide the SFQL agent with the reward function in the second condition. As a solution, before the agent was trained on a new taskMi, a linear model of the reward Ri(φ) = φ>w̃i was fitted. The initial approximation w̃i was randomly initialized and then fitted for 10.000 iterations using a gradient descent procedure based on the absolute mean error (L1 norm):
∆w̃i = η 1 |Φ| ∑ φ∈Φ Ri(φ)− φ>w̃i , (43)
with a learning rate of η = 1.0 that yielded the best results tested over several learning rates.
Hyperparameters: The hyperparameters of the algorithms were set to the same values as in (Barreto et al., 2017). A grid search over the learning rates of all algorithms was performed. Each learning rate was evaluated for three different settings which are listed in Table 1. If algorithms had several learning rates, then all possible combinations were evaluated. This resulted in a different number of evaluations per algorithm and condition: QL - 3, SFQL (O) - 9, MF Xi (O) - 9, MB Xi (O) - 27, SFQL - 3, MF Xi - 3, MB Xi - 9. In total, 63 parameter combinations were evaluated. The reported performances in the figures are for the parameter combination that resulted in the highest cumulative total reward averaged over all 10 repetitions in the respective environment. Please note, the learning rates α and αw are set to half of the rates defined in (Barreto et al., 2017). This is necessary due to the differences in calculating the loss and the gradients in the current paper. We use mean squared error loss formulations, whereas (Barreto et al., 2017) uses absolute error losses. The probability for random actions of the -Greedy action selection was set to = 0.15 and the discount rate to γ = 0.95. The initial weights θ for the function approximators were randomly sampled from a standard distribution with θinit ∼ N (µ = 0, σ = 0.01).
Computational Resources: Experiments were conducted on a cluster with a variety of node types (Xeon SKL Gold 6130 with 2.10GHz, Xeon SKL Gold 5218 with 2.30GHz, Xeon SKL Gold 6126 with 2.60GHz, Xeon SKL Gold 6244 with 3.60GHz, each with 192 GB Ram, no GPU). The time for evaluating one repetition of a certain parameter combination over the 300 tasks depended on the algorithm and the task type. Linear reward function tasks: QL ≈ 1h, SFQL (O) ≈ 4h, MF ξ (O) ≈ 42h, MB ξ (O) ≈ 43h, SFQL ≈ 4h, MF ξ ≈ 15h, and MB ξ ≈ 16h. General reward function
tasks: QL ≈ 1h, SFQL (O) ≈ 4h, MF ξ (O) ≈ 68h, MB ξ (O) ≈ 67h, SFQL ≈ 5h, MF ξ ≈ 14h, and MB ξ ≈ 18h. Please note, the reported times do not represent well the computational complexity of the algorithms, as the algorithms were not optimized for speed, and some use different software packages (numpy or pytorch) for their individual computations.

heading: C.4 EFFECT OF INCREASING NON-LINEARITY IN GENERAL REWARD TASK
text: We further studied the effect of general reward functions on the performance of classical SF compared to ξ-learning (Fig. 1 - c). We evaluated the agents in tasks with different levels of difficulty in relation to how well their reward functions can be approximated by a linear model. Seven difficulty levels have been evaluated. For each level, the agents were trained sequentially on 300 tasks as for the experiments with general reward functions. The reward functions for each level were sampled with the following procedure. Several general reward functions were randomly sampled as previously described. For each reward function, a linear model of a reward weight vector w̃ was fitted using the same gradient descent procedure as in Eq. 43. The final average absolute model error after 10.000 iterations was measured. Each of the seven difficulty levels defines a range of model errors its tasks have with the following increasing ranges: {[0.0, 0.25], [0.25, 0.5], . . . , [1.5, 1.75]}. For each difficulty level, 300 reward functions were selected that yield a linear model are in the respective range of the level.
Q-Learning, SFQL, and MF Xi-learning were each trained on 300 tasks, i.e. reward functions, on each difficulty level. As hyperparameters were the best performing parameters from the previous general reward task experiments used. We measured the ratio between the total return over 300 tasks of QL and MF Xi-learning (QL/MF Xi), and SFQL and MF Xi-learning (SFQL/MF Xi). Fig. 1 - c shows the results, using as x-axis the mean average absolute model error defined by the bracket of each difficulty level. The results show that the relative performance of SFQL compared to MF Xi reduces with higher non-linearity of the reward functions. For reward functions that are nearly linear (mean error of 0.125), both have a similar performance. Whereas, for reward functions that are difficult to model with a linear relation (mean error of 1.625) SFQL reaches only less than 50% of the performance of MF Xi-learning.
Algorithm 3: Model-free ξ-learning (MF ξ) Input : exploration rate:
learning rate for ξ-functions: α learning rate for reward models R: αR features φ optional: reward functions for tasks: {R̃1, R̃2, . . . , R̃num_tasks}
for i← 1 to num_tasks do if R̃i not provided then initialize R̃i: θRi ← small random initial values if i = 1 then initialize ξ̃i: θξi ← small random initial values else θ ξ i ← θ ξ i−1
new_episode← true for t← 1 to num_steps do
if new_episode then new_episode← false st ← initial state
c← argmaxk∈{1,2,...,i}maxa ∑ φ ξ̃k(st, a, φ)R̃i(φ) // GPI optimal policy With probability select a random action at, otherwise at ← argmaxa ∑ φ ξ̃c(st, a, φ)R̃i(φ) Take action at and observe reward rt and next state st+1 if R̃i not provided then
Update θRi using SGD(αR) with LR = (rt − R̃i(φ(st, at, st+1))2
if st+1 is a terminal state then new_episode← true γt ← 0
else γt ← γ
// GPI optimal next action for task i āt+1 ← argmaxa argk∈{1,2,...,i} ∑ φ ξ̃k(st+1, a, φ)R̃i(φ) foreach φ ∈ Φ do if φ = φ(st, at, st+1) then yφ ← 1 + γtξ̃i(st+1, āt+1, φ) else yφ ← γtξ̃i(st+1, āt+1, φ)
Update θξi using SGD(α) with Lξ = ∑ φ(yφ − ξ̃i(st, at, φ))2 if c 6= i then // optimal next action for task c
āt+1 ← argmaxa ∑ φ ξ̃c(st+1, a, φ)R̃c(φ) foreach φ ∈ Φ do if φ = φ(st, at, st+1) then yφ ← 1 + γtξ̃c(st+1, āt+1, φ) else yφ ← γtξ̃c(st+1, āt+1, φ)
Update θξc using SGD(α) with Lξ = ∑ φ(yφ − ξ̃c(st, at, φ))2
st ← st+1
Algorithm 4: One Step SF-Model ξ-learning (MB ξ) Input : exploration rate:
learning rate for ξ-functions: α learning rate for reward models R: αR learning rate for the one-step SF model p̃: β features φ optional: reward functions for tasks: {R̃1, R̃2, . . . , R̃num_tasks}
initialize p̃: θp ← small random initial values for i← 1 to num_tasks do
if R̃i not provided then initialize R̃i: θRi ← small random initial values if i = 1 then initialize ξ̃i: θξi ← small random initial values else θ ξ i ← θ ξ i−1 new_episode← true for t← 1 to num_steps do
if new_episode then new_episode← false st ← initial state
c← argmaxk∈{1,2,...,i}maxa ∑ φ ξ̃k(st, a, φ)R̃i(φ) // GPI optimal policy With probability select a random action at, otherwise at ← argmaxa ∑ φ ξ̃c(st, a, φ)R̃i(φ) Take action at and observe reward rt and next state st+1 if R̃i not provided then
Update θRi using SGD(αR) with LR = (rt − R̃i(φ(st, at, st+1))2
foreach φ ∈ Φ do if φ = φ(st, at, st+1) then yφ ← 1 else yφ ← 0
Update θp using SGD(β) with Lp = ∑ φ(yφ − p̃(st, at, φ))2 if st+1 is a terminal state then new_episode← true γt ← 0
else γt ← γ
// GPI optimal next action for task i āt+1 ← argmaxa argk∈{1,2,...,i} ∑ φ ξ̃k(st+1, a, φ)R̃i(φ) foreach φ ∈ Φ do yφ ← p̃(st, at, φ) + γtξ̃i(st+1, āt+1, φ)
Update θξi using SGD(α) with Lξ = ∑ φ(yφ − ξ̃i(st, at, φ))2 if c 6= i then // optimal next action for task c
āt+1 ← argmaxa ∑ φ ξ̃c(st+1, a, φ)R̃c(φ) foreach φ ∈ Φ do yφ ← p̃(st, at, φ) + γtξ̃c(st+1, āt+1, φ)
Update θξc using SGD(α) with Lξ = ∑ φ(yφ − ξ̃c(st, at, φ))2
st ← st+1

heading: D EXPERIMENTAL DETAILS: RACER ENVIRONMENT
text: This section extends the brief introduction to the racer environment (Fig. 2 - a) given in Section 4.2.

heading: D.1 ENVIRONMENT
text: The environment is a continuous two-dimensional area in which the agent drives similar to a car. The position of the agent is a point in the 2D space: p = (x, y) ∈ [0, 1]2. Moreover, the agent has an orientation which it faces: θ ∈ [−π, π1]. The action space of the agent consists of three movement directions: A = {right, straight, left }. Each action changes the position of the agent depending on its current position and orientation. The action straight changes the agent’s position by 0.075 towards its orientation θ. The action right changes the orientation of the agent to θ + 17π and its position 0.06 towards this new direction, whereas left the direction to θ − 17π changes. The environment is stochastic by adding Gaussian noise with σ = 0.005 to the final position x, y, and orientation θ. If the agent drives outside the area (x, y) ∈ [0, 1]2, then it reappears on the other opposite side. The environment resembles therefore a torus (or donut). As a consequence, distances d(px, py) are also measure in this space, so that the positions px = (0.1, 0.5) and py = (0.9, 0.5) have not a distance of 0.8 but d(px, py) = 0.2. The environment has 3 markers at the positions m1 = (0.25, 0.75), m2 = (0.75, 0.25), and m3 = (0.75, 0.6). The features measure the distance of the agent to each marker: φ ∈ R3 with φk = d(p,mk). Each feature dimensions is normalized to be φk ∈ [0, 1]. At the beginning of an episode the agent is randomly placed and oriented in environment. An episode ends after 200 time steps.
The state space of the agents is similarly constructed as for the object collection environment. The agent’s position is encoded with a 10 × 10 radial basis functions spos ∈ R100 as defined in 34. In difference, that the distances are measure according to the torus shape. A similar radial basis function approach is also used to encode the orientation sori ∈ R20 of the agent using 20 equally distributed gaussian centers in [−π, π] and σ = 15π. Please note, π and −π are also connected in this space, i.e. d(π,−π) = 0. The combination of the position and orientation of the agent is the final state: s = [s>pos, s > ori] > ∈ R120.
The reward functions define preferred positions in the environment based on the features, i.e. the distance of the agent to the markers. A preference function rk exists for each distance. The functions are composed of a maximization over m Gaussian components that evaluate the agents distance:
R(φ) = 3∑ k=1 rk(φk) with ri = 1 3 max { exp ( − (φk − µj) 2 σj )}m j=1 . (44)
Reward functions are randomly generated by sampling the number of Gaussian components m to be 1 or 2. The properties of each component are sampled according to µj ∼ U(0.0, 0.7), and σj ∼ U(0.001, 0.01). Fig. 2 - a illustrates one such randomly sampled reward function where dark areas represent locations with high rewards.

heading: D.2 ALGORITHMS
text: We evaluated Q-learning, SFQL (O), SFQL, and MF ξ-learning (see Section C.2 for their full description) in the racer environment. In difference to their implementation for the object collection environment, they used a different neural network architecture to approximate their respective value functions.
D.2.1 QL
Q-learning uses a fully connected feedforward network with bias and a ReLU activation for hidden layers. It has 2 hidden layers with 20 neurons each.
D.2.2 SFQL
Q-learning uses a feedforward network with bias and a ReLU activation for hidden layers. It has for each of the three feature dimensions a separate fully connected subnetwork. Each subnetwork has 2 hidden layers with 20 neurons each.
D.2.3 CONTINUOUS MODEL-FREE ξ-LEARNING
The racer environment has continuous features φ ∈ R3. Therefore, the MF ξ-learning procedure (Alg. 3) can not be directly applied as it is designed for discrete feature spaces. We introduce here a MF ξ-learning procedure for continuous feature spaces (CMF ξ-learning). It is a feature dimension independent, and discretized version of ξ-learning. As the reward functions (44) are a sum over the individual feature dimensions, the Q-value can be computed as:
Qπ(s, a) = ∫ Φ R(φ)ξπ(s, a, φ)dφ = ∑ k ∫ Φk rk(φk)ξ π k (s, a, φk)dφk , (45)
where Φk is the feature space for each feature dimension which is Φk = [0, 1] in the racer environment. ξπk is a ξ-function for the feature dimension k. (45) shows that the ξ-function can be independently represented over each individual feature dimension φk, instead of over the full features φ. This reduces the complexity of the approximation.
Moreover, we introduce a discretization of the ξ-function that discretizes the space of each feature dimension k in U = 11 bins with the centers:
Xk = { φmink + j∆φk : 0 < j < U } , with ∆φk :=
φmaxk − φmink U − 1 ,
where ∆φk is the distance between the centers, and φmink = 0.0 is the lowest center, and φ max k = 1.0 the largest center. Given this discretization and the decomposition of the Q-function according to (45), the Q-values can be computed by:
Qπ(s, a) = ∑ k ∑ x∈Xk R(x)ξπ(s, a, x) .
Alg. 5 lists the complete CMF ξ-learning procedure with the update steps for the ξ-functions. Similar to the SFQL agent, the CMF Xi uses a feedforward network with bias and a ReLU activation for hidden layers. It has for each of the three feature dimensions a separate fully connected subnetwork. Each subnetwork has 2 hidden layers with 20 neurons each. The discretized outputs per feature dimension share the last hidden layer per subnetwork.
The ξ-function is updated according to the following procedure. Instead of providing a discrete learning signal to the model, we encode the observed feature using continuous activation functions around each bin center. Given the j’th bin center of dimension k, xk,j , its value is encoded to be 1.0 if the feature value of this dimension aligns with the center (φk = xk,j). Otherwise, the encoding for the bin decreases linearily based on the distance between the bin center and the value (|xk,j−φk|) and reaches 0 if the value is equal to a neighboring bin center, i.e. has a distance ≥ ∆φk. We represent this encoding for each feature dimension k by uk ∈ (0, 1)U with:
∀k∈{1,2,3} : ∀0<j<U : uk,j = max ( 0, (1− |xk,j − φk|)
∆φk
) .
To learn ξ̃ we update the parameters θξ using stochastic gradient descent following the gradients ∇θξLξ(θξ) of the loss based on the ξ-learning update (13):
∀φ ∈ Φ : Lξ(θξ) = E
{ 1
n 3∑ k=1 ( uk + γξ̃k(st+1, āt+1; θ̄ ξ)− ξ̃k(st, at; θξ) )2}
with āt+1 = argmax a ∑ k ∑ x∈Xk R(x)ξ̃(st+1, a, φ; θ̄ ξ) ,
(46)
where n = 3 is the number of feature dimensions and ξ̃k is the vector of the U discretized ξ-values for dimension k.

heading: D.3 EXPERIMENTAL PROCEDURE
text: All agents were evaluated on 37 tasks. The agents experienced the tasks sequentially, each for 1000 episodes (200, 000 steps per task). The agents had knowledge when a task change happened.
Each agent was evaluated for 10 repetitions to measure their average performance. Each repetition used a different random seed that impacted the following elements: a) the sampling of the tasks, b) the random initialization of function approximator parameters, c) the stochastic behavior of the environments when taking steps, and d) the -greedy action selection of the agents. The tasks, i.e. the reward functions, were different between the repetitions of a particular agent, but identical to the same repetition of a different agent. Thus, all algorithms were evaluated over the same tasks.
SFQL was evaluated under two conditions. First, by learning the reward weights online during the training (indicated by (O) in figures). Second, the reward weights were trained with the iterative gradient decent method in (43). The weights were trained for 10, 000 iterations with an learning rate of 1.0. At each iteration, 50 random points in the task were sampled and their features and rewards are used for the training step.
Hyperparameters A grid search over the learning rates of all algorithms was performed. Each learning rate was evaluated for three different settings which are listed in Table 2. If algorithms had several learning rates, then all possible combinations were evaluated. This resulted in a different number of evaluations per algorithm and condition: QL - 4, SFQL (O) - 12, SFQL - 4, CMF Xi 4. In total, 24 parameter combinations were evaluated. The reported performances in the figures are for the parameter combination that resulted in the highest cumulative total reward averaged over all 10 repetitions in the respective environment. The probability for random actions of the -Greedy action selection was set to = 0.15 and the discount rate to γ = 0.9. The initial weights and biases θ for the function approximators were initialized according to an uniform distribution with θi ∼ U(− √ k, √ k), where k = 1in_features .
Computational Resources: Experiments were conducted on the same cluster as for the object collection environment experiments. The time for evaluating one repetition of a certain parameter combination over the 37 tasks depended on the algorithm: QL ≈ 9h, SFQL (O) ≈ 70h, SFQL ξ ≈ 73h, and CMF ξ ≈ 88h. Please note, the reported times do not represent well the computational complexity of the algorithms, as the algorithms were not optimized for speed, and some use different software packages (numpy or pytorch) for their individual computations.
Algorithm 5: Model-free ξ-learning for Continuous Features (CMF ξ) Input : exploration rate:
learning rate for ξ-functions: α learning rate for reward models R: αR features φ ∈ Rn components of reward functions for tasks: {R1 = {r11, r12, ..., r1n}, R2, . . . , Rnum_tasks} discretization parameters: X , ∆φ
for i← 1 to num_tasks do if i = 1 then ∀k∈{1,...,n}: initialize ξ̃ik: θ ξ i,k ← small random values
else ∀k∈{1,...,n}: θξi,k ← θ ξ i−1,k new_episode← true for t← 1 to num_steps do
if new_episode then new_episode← false st ← initial state
c← argmaxj∈{1,2,...,i}maxa ∑n k=1 ∑ x∈Xk ξ̃ j k(st, a, x)r i k(x) // GPI policy With probability select a random action at, otherwise at ← argmaxa ∑n k=1 ∑ x∈Xk ξ̃ j k(st, a, x)r i k(x) Take action at and observe reward rt and next state st+1 if st+1 is a terminal state then
new_episode← true γt ← 0
else γt ← γ
// GPI optimal next action for task i āt+1 ← argmaxa argj∈{1,2,...,i} ∑n k=1 ∑ x∈Xk ξ̃ j k(st, a, x)r i k(x) φt ← φ(st, at, st+1) for k ← 1 to n do
foreach x ∈ Xk do yk,x ← max ( 0, 1− |x−φt,k|∆φ ) + γtξ̃ i k(st+1, āt+1, x)
Update θξi using SGD(α) with Lξ = ∑n k=1 ∑ x∈Xk(yk,x − ξ̃ i k(st, at, x)) 2 if c 6= i then // optimal next action for task c
āt+1 ← argmaxa ∑n k=1 ∑ x∈Xk ξ̃ c k(st, a, x)r c k(x) for k ← 1 to n do foreach x ∈ Xk do
yk,x ← max ( 0, 1− |x−φt,k|∆φ ) + γtξ̃ c k(st+1, āt+1, x)
Update θξc using SGD(α) with Lξ = ∑n k=1 ∑ x∈Xk(yk,x − ξ̃ c k(st, at, x)) 2
st ← st+1

heading: E ADDITIONAL EXPERIMENTAL RESULTS
text: This section reports additional results and experiments:
1. Report of the total return and the statistical significance of differences between agents for all experiments
2. Evaluation of the agents in the original object collection task by Barreto et al. (2017)

heading: E.1 OBJECT COLLECTION TASK BY BARRETO ET AL. (2017)
text: We additionally evaluated all agents in the original object collection task by Barreto et al. (2017).
Environment: The environment differs to the modified object collection task (Section. C) only in terms of the objects and features. The environment has 3 object types: orange, blue, and pink (Fig. 3). The feature encode if the agent has collected one of these object types or if it reached the goal area. The first three dimensions of the features φ(st, at, st+1) ∈ {0, 1}4 encode which object type is collected. The last dimension encodes if the goal area was reached. In total |Φ| = 5 possible features exists: φ1 = [0, 0, 0, 0]>- standard observation, φ2 = [1, 0, 0, 0]>- collected an orange object, φ3 = [0, 1, 0, 0]>- collected a blue object, φ4 = [0, 0, 1, 0]>- collected a pink object, and φ5 = [0, 0, 0, 1]>- reached the goal area.
The rewards r = φ>wi are defined by a linear combination of discrete features φ ∈ N4 and a weight vector w ∈ R4. The first three dimensions in w define the reward that the agent receives for
collecting one of the object types. The final weight defines the reward for reaching the goal state which is w4 = 1 for each task. All agents were trained in on 300 randomly generated linear reward functions with the same experimental procedure as described in Section. C. For each task the reward weights for the 3 objects are randomly sampled from a uniform distribution: wk∈{1,2,3} ∼ U(−1, 1).
Results: The results (Fig. 4) follow closely the results from the modified object collection task (Fig. 1 - b, and 5 - a). MF ξ reaches the highest performance outperforming SFQL in terms of learning speed and asymptotic performance. It is followed by MB ξ and SFQL which show no statistical significant difference between each other in their final performance. Nonetheless, MB Ξ has a higher learning speed during the initial 40 tasks. The results for the agents that learn the reward weights online (SFQL (O), MF ξ (O), and MB ξ (O)) follow the same trend with MF ξ (O) outperforming SFQL (O) slightly. Nonetheless, the ξ-agents have a much stronger learning speed during the initial 70 tasks compared to SFQL (O), due to the errors in the approximation of the weight vectors, especially at the beginning of a new task. All agents can clearly outperform standard Q-learning.

heading: E.2 TOTAL RETURN IN TRANSFER LEARNING EXPERIMENTS AND STATISTICAL SIGNIFICANT DIFFERENCES
text: Fig. 5 shows for each of the transfer learning experiments in the object collection and the racer environment the total return that each agent accumulated over all tasks. Each dot besides the boxplot shows the total return for each of the 10 repetitions. The box ranges from the upper to the lower quartile. The whiskers represent the upper and lower fence. The mean and standard deviation are indicated by the dashed line and the median by the solid line. The tables in Fig. 5 report the p-value of pairwise Mann–Whitney U test. A significant different total return can be expected if p < 0.05.
For the object collection environment (Fig.5 - a; b), ξ-learning outperforms SFQL in both conditions, in tasks with linear and general reward functions. However, the effect is stronger in tasks with general reward functions where SFQL has more problems to correctly approximate the reward function with its linear approach. For the condition, where the agents learn a reward model online (O), the difference between the algorithms in the general reward case is not as strong due the effect of their poor approximated reward models for all agents.
In the racer environment (Fig.5 - c) SFQL has a poor performance below standard Q-learning as it can not appropriately approximate the reward functions with a linear model. In difference CMF ξ-learning outperforms QL.

Review summaries:
This paper proposes a new successor feature learning algorithm, called \xi-learning. Previous SF assumes reward function is a linear composition of SF and reward weights, this paper extends previous SF to a setting with a general reward function over SF. Based on this, \xi-learning learns to estimate the cumulative discounted probability of SF, and provides two update operators, model-free \xi-learning and model-based \xi-learning. The convergence of \xi-learning is proved, and empirical results on environments with discrete and continuous state spaces show it outperforms previous SF methods.

The authors extend the successor features (SF) linear formulation to general non-linear formulation. The new method allows the reward to be arbitrary composition of features.   The propose method is based on learning cumulative discounted probability of SF rather than cumulative discounted sum of SF as in linear SF framework.  The authors provide theoretical proofs about convergence and propose two practical methods. Experiments are conducted in two toy environments. 

This paper addresses a limitation of the successor features (SF) which were introduced as a mechanism for transfer learning in reinforcement learning when the reward function changes across tasks. The authors claim that the original SF framework will only provide a good approximation of the true Q-function if the reward function in a task can be represented using a linear decomposition, and propose to address this linear decomposition of the reward function requirement by introducing a novel SF mechanism, Xi-learning, based on learning a cumulative discounted probability of successor features. The paper includes theoretical proofs of the convergence of xi-learning as well as transfer learning guarantees under generalized policy improvement (GPI). The authors compare the performance of their methods against standard Q-learning and SFQL in two different domains.