Continual Auxiliary Task Learning
Year: 2022

Abstract:
Learning auxiliary tasks, such as multiple predictions about the world, can provide many benefits to reinforcement learning systems. A variety of off-policy learning algorithms have been developed to learn such predictions, but as yet there is little work on how to adapt the behavior to gather useful data for those off-policy predictions. In this work, we investigate a reinforcement learning system designed to learn a collection of auxiliary tasks, with a behavior policy learning to take actions to improve those auxiliary predictions. We highlight the inherent non-stationarity in this continual auxiliary task learning problem, for both prediction learners and the behavior learner. We develop an algorithm based on successor features that facilitates tracking under non-stationary rewards, and prove the separation into learning successor features and rewards provides convergence rate improvements. We conduct an in-depth study into the resulting multi-prediction learning system.

heading: 1 Introduction
text: In never-ending learning systems, the agent often faces long periods of time when the external reward is uninformative. A smart agent should use this time to practice reaching subgoals, learning new skills, and refining model predictions. Later, the agent should use this prior learning to efficiently maximize external reward. The agent engages in this self-directed learning during times when the primary drives of the agent (e.g., hunger) are satisfied. Other times, the agent might have to trade-off directly acting towards internal auxiliary learning objectives and taking actions that maximize reward.
In this paper we investigate how an agent should select actions to balance the needs of several auxiliary learning objectives in a no-reward setting where no external reward is present. In particular, we assume the agent’s auxiliary objectives are to learn a diverse set of value functions corresponding to a set of fixed policies. Our solution at a high-level is straightforward. Each auxiliary value function is learned in parallel and off-policy, and the behavior selects actions to maximize learning progress. Prior work investigated similar questions in a state-less bandit like setting, where both off-policy learning and function approximation are not required [Linke et al., 2020].
Otherwise, the majority of prior work has focused on how the agent could make use of auxiliary learning objectives, not how behavior could be used to improve auxiliary task learning. Some work has looked at defining (predictive) features, such as successor features and a basis of policies [Barreto et al., 2018, Borsa et al., 2019, Barreto et al., 2020, 2019]; universal value function approximators [Schaul et al., 2015]; and features based on value predictions [Schaul and Ring, 2013, Schlegel et al., 2021]. The other focus has been exploration, using auxiliary learning objectives to generate bonuses to aid exploration on the main task [Pathak et al., 2017, Stadie et al., 2015, Badia et al., 2020, Burda et al., 2019]; using a given set of policies in a call-return fashion for scheduled auxiliary control
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
[Riedmiller et al., 2018]; and discovering subgoals in environments where it is difficult for the agent to reach particular parts of the state-action space [Machado et al., 2017, Colas et al., 2019, Zhang et al., 2020, Andrychowicz et al., 2017, Pong et al., 2019]. In all of these works, the behavior was either fixed or optimized for the main task.
The problem of adapting the behavior to optimize many auxiliary predictions in the absence of external reward is sufficiently complex to merit study in isolation. It involves several inter-dependent learning mechanisms, multiple sources of non-stationarity, and high-variance due to off-policy updating. If we cannot design learning systems that efficiently learn their auxiliary objectives in isolation, then the agent is unlikely to learn its auxiliary tasks while additionally balancing external reward maximization.
Further, understanding how to efficiently learn a collection of auxiliary objectives is complementary to the goals of using those auxiliary objectives. It could amplify the auxiliary task effect in UNREAL [Jaderberg et al., 2017], improve the efficiency and accuracy of learning successor features and universal value function approximators, and improve the quality of the sub-policies used in scheduled auxiliary control. It can also benefit the numerous systems that discover options, skills, and subgoals [Gregor et al., 2017, Eysenbach et al., 2019a, Veeriah et al., 2019, Pitis et al., 2020, Nair et al., 2020, Pertsch et al., 2020, Colas et al., 2019, Eysenbach et al., 2019b], by providing improved algorithms to learn the resulting auxiliary tasks. For example, for multiple discovered subgoals, the agent can adapt its behavior to efficiently learn policies to reach each subgoal.
In this paper we introduce an architecture for parallel auxiliary task learning. As the first such work to tackle this question in reinforcement learning with function approximation, numerous algorithmic challenges arise. We first formalize the problem of learning multiple predictions as a reinforcement learning problem, and highlight that the rewards for the behavior policy are inherently non-stationary due to changes in learning progress over time. We develop a strategy to use successor features to exploit the stationarity of the dynamics, whilst allowing for fast tracking of changes in the rewards, and prove that this separation provides a faster convergence rate than standard value function algorithms like temporal difference learning. We empirically show that this separation facilitates tracking both for prediction learners with non-stationary targets as well as the behavior.

heading: 2 Problem Formulation
text: We consider the multi-prediction problem, in which an agent continually interacts with an environment to obtain accurate predictions. This interaction is formalized as a Markov decision process (MDP), defined by a set of states S , a set of actions A, and a transition probability function P(s, a, s0). The agent’s goal, when taking actions, is to gather data that is useful for learning N predictions, where each prediction corresponds to a general value function (GVF) [Sutton et al., 2011].
A GVF question is formalized as a three tuple (⇡, , c), where the target is the expected return of the cumulant, defined by c : S ⇥A⇥ S ! R, when following policy ⇡ : S ⇥A! [0, 1], discounted by : S ⇥A⇥ S ! [0, 1]. More precisely, the target is the action-value
Q(s, a) def = E⇡ [Gt|St = s, At = a] for Gt def = Ct+1 + t+1Gt+1
where Ct+1 def = c(St, At, St+1) and t+1 def = (St, At, St+1). The extension of to transitions allows for a broader class of problems, including easily specifying termination, without complicating the theory [White, 2017]. The expectation is under policy ⇡, with transitions according to P . The prediction targets could also be state-value functions; we assume the targets are action-values in this work to provide a unified discussion of successor features for both the GVF and behavior learners.
At each time step, the agent produces N predictions, a Q̂(j)t (St, At) for prediction j with true targets Q(j)t (St, At). We assume the GVF question can change over time, and so Q can change with time. The goal is to have low error in the prediction, in terms of the root mean-squared value error (RMSVE), under state-action weighting d : S ⇥A! R:
RMSVE(Q̂, Q) def= sX
s2S
X a2A d(s, a)(Q̂(s, a) Q(s, a))2 (1)
The total error up to time step t, across all predictions, is TE def= Pt
i=1 PN j=1 RMSVE(Q̂ (j) i , Q (j) i ).
Behavior
Task 1 Task 2 Task N
Intrinsic Reward Weight Change
St at
e/ O
bs er
va tio
n
Agent
(S t+
1 )
<latexit sha1_base64="OjSwn01Y1y62YFQEFg9u2D/6H18=">AAAB8HicbVBNSwMxEJ2tX7V+VT16CRahIpRdqeix6MVjRfsh7VKyabYNTbJLkhXK0l/hxYMiXv053vw3pu0etPXBwOO9GWbmBTFn2rjut5NbWV1b38hvFra2d3b3ivsHTR0litAGiXik2gHWlDNJG4YZTtuxolgEnLaC0c3Ubz1RpVkkH8w4pr7AA8lCRrCx0mP5vpeaM29y2iuW3Io7A1omXkZKkKHeK351+xFJBJWGcKx1x3Nj46dYGUY4nRS6iaYxJiM8oB1LJRZU++ns4Ak6sUofhZGyJQ2aqb8nUiy0HovAdgpshnrRm4r/eZ3EhFd+ymScGCrJfFGYcGQiNP0e9ZmixPCxJZgoZm9FZIgVJsZmVLAheIsvL5PmecWrVi7uqqXadRZHHo7gGMrgwSXU4Bbq0AACAp7hFd4c5bw4787HvDXnZDOH8AfO5w+hlo+n</latexit>
Rt+1
<latexit sha1_base64="V1A7ppgGUup3oxpxVAu7QIY7BKo=">AAAB7nicbVBNS8NAEJ34WetX1aOXxSIIQkmkoseiF49V7Ae0oWy2m3bpZhN2J0IJ/RFePCji1d/jzX/jts1BWx8MPN6bYWZekEhh0HW/nZXVtfWNzcJWcXtnd2+/dHDYNHGqGW+wWMa6HVDDpVC8gQIlbyea0yiQvBWMbqd+64lrI2L1iOOE+xEdKBEKRtFKrYdehufepFcquxV3BrJMvJyUIUe9V/rq9mOWRlwhk9SYjucm6GdUo2CST4rd1PCEshEd8I6likbc+Nns3Ak5tUqfhLG2pZDM1N8TGY2MGUeB7YwoDs2iNxX/8zophtd+JlSSIldsvihMJcGYTH8nfaE5Qzm2hDIt7K2EDammDG1CRRuCt/jyMmleVLxq5fK+Wq7d5HEU4BhO4Aw8uIIa3EEdGsBgBM/wCm9O4rw4787HvHXFyWeO4A+czx/XnY9B</latexit>
At+1
<latexit sha1_base64="kReBLeP7qxIcNi6r2Ca46gqAW68=">AAAB7nicbVBNS8NAEJ34WetX1aOXxSIIQkmkoseqF48V7Ae0oWy2m3bpZhN2J0IJ/RFePCji1d/jzX/jts1BWx8MPN6bYWZekEhh0HW/nZXVtfWNzcJWcXtnd2+/dHDYNHGqGW+wWMa6HVDDpVC8gQIlbyea0yiQvBWM7qZ+64lrI2L1iOOE+xEdKBEKRtFKrZtehufepFcquxV3BrJMvJyUIUe9V/rq9mOWRlwhk9SYjucm6GdUo2CST4rd1PCEshEd8I6likbc+Nns3Ak5tUqfhLG2pZDM1N8TGY2MGUeB7YwoDs2iNxX/8zophtd+JlSSIldsvihMJcGYTH8nfaE5Qzm2hDIt7K2EDammDG1CRRuCt/jyMmleVLxq5fKhWq7d5nEU4BhO4Aw8uIIa3EMdGsBgBM/wCm9O4rw4787HvHXFyWeO4A+czx+9c48w</latexit>
EnvironmentThe agent’s goal is to gather data and update its predictions to make TE small. This goal can itself be formalized as a reinforcement learning problem, by defining rewards for the behavior policy that depend on the agent’s predictions. Such rewards are often called intrinsic rewards. For example, if we could directly measure the RMSVE, one potential intrinsic reward would be the decrease in the RMSVE after taking action At from state St and transitioning to St+1. This reflects the agent’s learning progress—how much it was able to learn—due to that new experience. The reward is high if the action generated data that resulted in substantial learning. While the RMSVE is the most direct measure of learning progress, it cannot be calculated without the true values.
Algorithm 1 Multi-Prediction Learning System Input: N GVF questions
Initialize behavior policy parameters ✓0 and GVF learners w(1)0 , . . . , w (N) 0 Obtain initial observation S0 for t = 0, 1, . . . do
Choose action At according to ⇡✓t(·|St) Observe next state vector St+1 and t+1 // Update predictions with new data for j = 1 to N do
c c(j)(St, At, St+1) (j)(St, At, St+1) Update w(j)t with (St, At, c, St+1, )
// Compute intrinsic reward, update behavior Rt+1 PN j=1 kw (j) t+1 w (j) t k1
Update ✓t with (St, At, Rt+1, St+1, t+1)
Many intrinsic rewards have been considered to estimate the learning progress of predictions. A recent work provided a thorough survey of different options, as well as an empirical study [Linke et al., 2020]. Their conclusion was that, for reasonable prediction learners, simple learning progress measures—like the change in weights—were effective for producing effective data gathering. We rely on this conclusion here, and formalize the problem using the `1 norm on the change in weights. Other intrinsic rewards could be swapped into the framework; but, because our focus is on the non-stationarity in the system and because empirically we found this weight-change intrinsic reward to be effective, we opt for this simple choice upfront.
We provide the generic pseudocode for a multiprediction reinforcement learning system, in Algorithm 1. Note that the behavior agent also has a separate transition-based , which enables us to encode both continuing and episodic problems. For example, the pseudo-termination for a GVF could be a particular state in the environment, such as a doorway. The discount for the GVF would be zero in that state, even though it is not a true terminal state; the behavior discount t+1 would not be zero.

heading: 3 Non-stationarity Induced by Learning
text: On the surface, the multi-prediction problem outlined in the previous section is a relatively straightforward reinforcement learning problem. The behavior policy learns to maximize cumulative reward, and simultaneously learns predictions about its environment. Many RL systems incorporate prediction learning, either as auxiliary tasks or to learn a model. However, unlike standard RL problems, the rewards for the behavior are non-stationary when using intrinsic rewards, even under stationary dynamics. Further, the prediction problems themselves are non-stationary due to a changing behavior.
To understand this more deeply, consider first the behavior rewards. On each time step, the predictions are updated. Progressively, they get more and more accurate. Imagine a scenario where they can become perfectly accurate, such as in the tabular setting with stationary cumulants. The behavior rewards are high in early learning, when predictions are inaccurate. As predictions become more and more accurate, the change in weights gets smaller until eventually the behavior rewards are near zero. This means that when the behavior revisits a state, the reward distribution has actually changed. More generally, in the function approximation setting, the behavior rewards will continue to change with time, not necessarily decay to zero.
The prediction problems are also non-stationary for two reasons. First, the cumulants themselves might be non-stationary, even if the transition dynamics are stationary. For example, the cumulant could correspond to the amount of food in a location in the environment, that slowly gets depleted. Or, the cumulant could depend on a hidden variable, that makes the outcome appear non-stationary. Even with a stationary cumulant, the prediction learning problem can be non-stationary due to a changing behavior policy. As the behavior policy changes, the state distribution changes. Implicitly,
when learning off-policy, the predictions are minimizing an objective weighted by the state visitation under the behavior policy. As the behavior changes, the underlying objective is actually changing, resulting in a non-stationary prediction problem.
Though there has been some work on learning under non-stationarity in RL and bandits, none to our knowledge has addressed the multi-prediction setting in MDPs. There has been some work developing reinforcement learning algorithms for non-stationary MDPs, but largely for the tabular setting [Sutton and Barto, 2018, Da Silva et al., 2006, Abdallah and Kaisers, 2016, Cheung et al., 2020] or assuming periodic shifts [Chandak et al., 2020a,b, Padakandla et al., 2020]. There has also been some work in the non-stationary multi-armed bandit setting [Garivier and Moulines, 2008, Koulouriotis and Xanthopoulos, 2008, Besbes et al., 2014]. The non-stationary rewards for the behavior, that decay over time, have been considered for the bandit setting, under rotting bandits [Levine et al., 2017, Seznec et al., 2019]; these algorithms do not obviously extend to the RL setting.

heading: 4 Handling the Non-Stationarity in a Multi-prediction System
text: In this section, we describe a unified approach to handle non-stationarity in both the GVF and behavior learners, using successor features. We first discuss how to use successor features to learn under non-stationary cumulants, for prediction. Then we discuss using successor features for control, allows us to leverage this approach for non-stationary rewards for the behavior. We then discuss state-reweightings, and how to mitigate non-stationarity due to a changing behavior.

heading: 4.1 Successor Features for Non-stationary Rewards
text: Successor features provide an elegant way to learn value functions under non-stationarity. The separation of learning stationary successor features and rewards enables more effective tracking of non-stationary rewards, as we explain in this section and formally prove in Section 5.
Assume that there is a weight vector w⇤ 2 Rd and features x(s, a) 2 Rd for each state and action (s, a) such that r(s, a) = hx(s, a),w⇤i. Recursively define
(s, a) = E⇡[x(St, At) + t+1 (St+1, At+1)|St = s, At = a]
(s, a) is called the successor features, the discounted cumulative sum of feature vectors, if we follow policy ⇡. For t def = (St, At) and xt def = x(St, At), we can see Q(s, a) = h (s, a),w⇤i
h (s, a),w⇤i = E⇡[hxt,w⇤i|St = s, At = a] + E⇡[ t+1h t+1,w⇤i|St = s, At = a] = r(s, a) + E⇡[ t+1hxt+1,w⇤i|St = s, At = a] + E⇡[ t+1 t+2h t+2,w⇤i|St = s, At = a] = r(s, a) + E⇡[ t+1rt+1|St = s, At = a] + E⇡[ t+1 t+2h t+2,w⇤i|St = s, At = a] = . . . = E⇡[r(s, a) + t+1rt+1 + t+1 t+2rt+2 + . . . |St = s, At = a] = Q(s, a).
If we have features x(s, a) 2 Rd which allow us to represent the immediate reward, then successor features provide a good representation to approximate the GVF. We simply learn another set of parameters wc 2 Rd that predict the immediate cumulant (or reward): c(s, a) ⇡ hx(s, a),wci. These parameters wc are updated using a standard regression update, and Q(s, a) ⇡ h (s, a),wci . The successor features (s, a) themselves, however, also need to be approximated. In most cases, we cannot explicitly maintain a separate (s, a) for each (s, a), outside of the tabular setting. Notice that each element in (s, a) corresponds to a true expected return: the cumulative discounted sum of a reward feature into the future. Therefore, (s, a) can be approximated using any value function approximation method, such as temporal difference (TD) learning. We learn parameters w for the approximation  ̂(s, a;w ) = [ ̂1(s, a;w ), ...,  ̂d(s, a;w )]> 2 Rd where  ̂m(s, a;w ) ⇡ m(s, a). We can use any function approximator for  ̂(s, a;w ), such as linear function approximation with tile coding with w , linearly weighting the tile coding features to produce  ̂(s, a;w ), or neural networks, where w are the parameters of the neural network.
We summarize the algorithm using successor features for non-stationary rewards/cumulants, called SF-NR, in Algorithm 2. We provide an update formula for the approximate SF using Expected Sarsa for prediction [Sutton and Barto, 2018] for simplicity, but note that any value learning algorithm can be used here. In our experiments, we use Tree-Backup [Precup, 2000] because it reduces variance
from off-policy learning; we provide the pseudocode in Appendix D. Algorithm 2 assumes that the reward features x(s, a) are given, but of course these can be learned as well. Ideally, we would learn a compact set of reward features that provide accurate estimates as a linear function of these reward features. A compact (smaller) set of reward features is preferred because it makes the SF more computationally efficient to learn.
Algorithm 2 Successor Features for Non-stationary Rewards (SF-NR) Input:(St,At,St+1,Ct+1, t+1),⇡,w ,wc x x(St, At)  ̂  ̂(St, At;w )  ̂0 P a0 ⇡(a
0|St+1) ̂(St+1, a0;w ) 0 for m = 1 to d do m xm + t+1 ̂0m  ̂m + mr ̂m
w w + ↵ wc wc + ↵(Ct+1 hx,wci)x There are two key advantages from the separation into learning successor features and immediate cumulant estimates. First, it easily allows different or changing cumulants to be used, for the same policy, using the same successor features. The transition dynamics summarized in the stationary successor features can be learned slowly to high accuracy and re-used. This re-use property is why these representations have been used for transfer [Barreto et al., 2017, 2018, 2020]. This property is pertinent for us, because it allows us to more easily track changes in the cumulant. The regression updates can quickly update the parameters wc, and exploit the already learned successor features to more quickly track value estimates. Small changes in the rewards can result in large changes in the values; without the separation, therefore, it can be more difficult to directly track the value estimates.
Second, the separation allows us to take advantage of online regression algorithms with strong convergence guarantees. Many optimizers and accelerations are designed for a supervised setting, rather than for temporal difference algorithms. Once the successor features are learned, the prediction problem reduces to a supervised learning problem. We can therefore even further improve tracking by leveraging these algorithms to learn and track the immediate cumulant. We formalize the convergence rate improvements, from this separation, in Section 5.

heading: 4.2 GPI with Successor Features for Control
text: In this section we outline a control algorithm under non-stationary rewards. SF-NR provides a method for updating the value estimate due to changing rewards. The behavior for the multi-prediction problem has changing rewards, and so could benefit from SF-NR. But SF-NR only provides a mechanism to efficiently track action-values for a fixed policy, not for a changing policy. Instead, we turn to the idea of constraining the behavior to act greedily with respect to the values for a set of policies, introduced as Generalized Policy Improvement (GPI) Barreto et al. [2018, 2020].
For our system, this is particularly natural, as we are already learning successor features for a collection of policies. Let us start there, where we assume our set of policies is ⇧ = {⇡1, . . . ,⇡N}. Assume also that we have learned the successor features for these policies,  ̂(s, a;w(j) ), and that we have weights ✓r 2 Rd such that hx(s, a), ✓ri ⇡ E[Rt+1|St = s, At = a] for behavior reward Rt+1. Then on each step, the behavior policy takes the following greedy action
µ(s) = argmax a max j2{1,...,N}
Q̂ (j) r (s, a) = argmax
a max j2{1,...,N} h ̂(s, a;w(j) ), ✓ri
The resulting policy is guaranteed to be an improvement: in every state the new policy has a value at least as good as any of the policies in the set [Barreto et al., 2017, Theorem 1]. Later work also showed sampled efficiency of GPI when combining known reward weights to solve novel tasks [Barreto et al., 2020].
The use of successor features has similar benefits as discussed above, because the estimates can adapt more rapidly as the rewards change, due to learning progress changing over time. The separation is even more critical here, as we know the rewards are constantly drifting, and tracking quickly is even more critical. We could even more aggressively adapt to these non-stationary rewards, by anticipating trends. For example, instead of a regression update, we can model the trend (up or down) in the reward for a state and action. If the reward has been decreasing over time, then likely it will continue to decrease. Stochastic gradient descent will put more weight on recent points, but would likely predict a higher expected reward than is actually observed. For simplicity here, we still choose to use stochastic gradient descent, as it is a reasonably effective tracking algorithm, but note that performance improvements could likely be obtained by exploiting this structure in this problem.
We can consider a different set of policies for GVFs and behavior. However, the two are naturally coupled. First, the GPI theory shows that greedifying over a larger collection of policies provides better policies. It is sensible then to at least include the GVF policies into the set for the behavior. Second, the behavior needs to learn the successor features for the additional policies. Arguably, it should try to gather data to learn these well, so as to facilitate its own policy improvement. It should therefore also incorporate the learning progress for these successor features, into the intrinsic reward. For this work, therefore, we assume that the behavior uses the set of GVF policies. Note that the weight change intrinsic reward uses the concatenation of w and wc.

heading: 4.3 Interest and prior corrections for the changing state distribution
text: The final source of non-stationarity is in the state distribution. As the behavior µ changes, the state-action visitation distribution dµt : S ⇥ A ! [0, 1] changes. The state distribution implicitly weights the relative importance of states in the GVF objective, called the projected Bellman error (PBE). Correspondingly, the optimal SF solution could be changing, since the objective is changing. The impact of a changing state-weighting depends on function approximation capacity, because the weighting indicates how to trade-off function approximation error across states. When approximation error is low or zero—such as in the tabular setting—the weighting has little impact on the solution. Generally, however, we expect some approximation error and so a non-negligible impact.
We can completely remove this source of non-stationary by using prior corrections. These are products of importance sampling ratios, that reweight the trajectory to match the probability of seeing that trajectory under the target policy ⇡. Namely, it modifies the state weighting to d⇡, the state-action visitation distribution under ⇡. We explicitly show this in Appendix C. Unfortunately, prior corrections can be highly problematic in a system where the behavior policy takes exploratory actions and target policies are nearly deterministic. It is likely that these corrections will often either be zero, or near zero, resulting in almost no learning.
To overcome this inherent difficulty, we restrict which states are important for each predictive question. Likely, when creating a GVF, the agent is interested in predictions for that GVF only in certain parts of the space. This is similar to the idea of initiation sets for options, where an option is only executed from a small set of relevant states. We can ask: what is the GVF answer, from this smaller set of states of interest? This can be encoded with a non-negative interest function, i(s, a), where some (or even many) states have an interest of zero. This interest is incorporated into the state-weighting in the objective, so the agent can focus function approximation resources on states of interest.
When using interest, it is sensible to use emphatic weights [Sutton et al., 2016]. Emphatic weightings are a prior correction method, used under the excursions model [Patterson et al., 2021]. They reweight to a discounted state-action visitation under ⇡ when starting from states proportionally to dµ. Further, they ensure states inherit the interest of any states that bootstrap off of them. Even if a state has an interest of zero, we want to accurately estimate its value if an important states bootstraps off of its value. The combination of interest and emphatic weightings—which shift state-action weighting to visitation under ⇡—means that we mitigate much of the non-stationarity in the state-action weighting. We provide the pseudocode for this Emphatic TB (ETB) algorithm in Appendix D.

heading: 5 Sample Efficiency of SF-NR
text: As suggested in Section 4.1, the use of successor features makes SF-NR particularly well-suited to our multi-prediction problem setting. The reason for this is simple: given access to an accurate SF matrix, value function estimation reduces to a fundamentally simpler linear prediction problem. Indeed, access to an accurate SF enables one to sidestep known lower-bounds on PBE estimation.
For simplicity, we prove the result for value functions; the result easily extends to action-values. Denote by v⇡ 2 R|S| the vector with entries v⇡(s), r⇡ 2 R|S| the vector of expected immediate rewards in each state, and P 2 R|S|⇥|S| the matrix of transition probabilities. The following lemma, proven in Appendix A.1, relates mean squared value error (VE) to one-step reward prediction error.
Lemma 1 Assume there exists a w⇤ 2 Rd such that r⇡ = Xw⇤. Let r̂ def= Xw for some w 2 Rd, and let D = Diag({d(s)}s2S) for distribution d fully supported on S , with k · kD the weighted norm under D. Then the value estimate v̂ def
= w satisfies 12kv ⇡ v̂k2D  kr⇡ r̂k2D 2(1 )2 .
Thus we can ensure that VE(v⇡, v̂)  " by ensuring that kr⇡ r̂k2D  "(1 )2. This is promising, as this latter expression is readily expressed as the objective of a linear regression problem. To illustrate the utility of this, let’s look at a concrete example: suppose the agent has an accurate SF matrix and that the reward function changes at some point in the agent’s deployment. Suppose access to a batch of transitions D def= {St, At, S0t, rt, ⇢t}Tt=1 with which we can correct our estimate of v⇡ , where each (s, a, s0, ⇢) 2 D is such that s ⇠ dµ for some known behavior policy µ, At ⇠ ⇡(·|s), s0 ⇠ P (·|s, a) and r = r(s, a, s0). Assume for simplicity that ⇢t  ⇢max , k (St)k1  L, rt  Rmax for some finite ⇢max , Rmax , L 2 R+. Then we can get the following result, proven in Appendix A.2, that is a straightforward application of Orabona [2019, Theorem 7.26]. Proposition 1 Define `t(w) def = ⇢t2 (rt hx(St), wi) 2 . Suppose we apply a basic recursive leastsquares estimator to minimize regret on this loss sequence, producing a sequence of iterates wt. Let wT def = 1T PT t=1 wt denote the average iterate. For v̂(s) = h (s), wT i, we have that
kv⇡ v̂k2D  O
d⇢maxR 2 max log 1 + ⇢max L2T
(1 )2T
! . (2)
In contrast, without the SF we are faced with minimizing a harder objective: the PBE. It can be shown that minimizing the PBE is equivalent to a stochastic saddle-point problem, and the convergence to the saddle-point of this problem has an unimprovable rate of O ⇣ ⌧
T 2 + (1+ )⇢max L 2d T + p T
⌘ where ⌧ is
the maximum eigenvalue of the covariance matrix and bounds gradient stochasticity, and this convergence rate translates into the performance bound 12kv ⇡ v̂k2D  O ⇣q ⌧ T 2 + (1+ )⇢max L2d T + p T ⌘ [Liu et al., 2018a, Proposition 5]. Comparing with Equation 2, we observe an additional dependence of O( p ⌧/T ) as well as the worse dependence of at least O(1/ p T ) (log (T ) /T ) on all other quantities of interest, reinforcing the intuition that access to the SF enables us to more efficiently re-evaluate the value function.

heading: 6 A First Experiment Testing the Multi-prediction System

heading: Utility of SF-NR for a Fixed Behavior Policy
text: We start by testing the utility of SF-NR for GVF learning, under a fixed policy that provides good data coverage for every GVF. The Fixed-Behavior Policy is started from random states in the TMaze, and moves towards the closest goal, with a 50/50 chance of going either direction if there is a tie. This policy is like a round robin policy, in that one of the GVF policies is executed each episode and, in expectation, all four policies are executed the same number of times.
We compare an agent that uses SF-NR and one that learns the approximate GVFs using Tree Back-Up (TB). TB is an off-policy temporal difference (TD) algorithm, that reduces variance in the eligibility trace. We also use TB to learn the successor features in SF-NR. Both use = 0.9 and a stepsize method called Auto [Mahmood et al., 2012] designed for online learning. We sweep the initial stepsize and meta stepsizes for Auto. For further details about the agents and optimizer, see Appendix D. We additionally compare to least squares TD (LSTD), with = 0.9, particularly as it computes a matrix similar to the SF, but does not separate out cumulant learning (see Appendix B for this connection).
In Figure 2a, we can see SF-NR allows for much more effective learning, particularly later in learning when it more effectively tracks the non-stationary signals. LSTD performs much more poorly, likely because it corresponds to a closed-form batch solution, which uses old cumulants that are no longer reflective of the current cumulant distribution.

heading: Investigating GPI for Learning the Behavior
text: Next we investigate if SF-NR improves learning of the whole system, both for the GVFs and for the behavior policy. We use SF-NR and TB for the GVF learners, and Expected Sarsa (Sarsa) and GPI for the behavior. The GPI agent uses the GVF policies for its set of policies. The reward features for the behavior are likely different than those for the GVF learners, because the cumulants are zero in most states whereas intrinsic rewards are likely non-zero in most states. The GPI agent, therefore, learns its own SFs for each policy, also using TB. The reward weights that estimate the (changing) intrinsic rewards are learned using Auto, as are the SFs. Note that the behavior and GVF learners all share the same meta-step size—namely only one shared parameter is swept.
The results highlight that SF for the GVFs is critical for effective learning, though GPI and Sarsa perform similarly, as shown in Figure 3b. The utility of SF is even greater here, with TB GVF learners inducing much worse performance than SF GVF learners. GPI and Sarsa are similar, which is likely due to the fact that Sarsa uses traces with tabular features, which allow states along the trajectory to the drifter goal to update quickly. In following sections, we find a bigger distinction between the two.
We visualize the goal visitation of GPI in Figure 2c. Once the GVF learners have a good estimate for the constant cumulant signals and the distractor cumulant signal, the agent behavior should switch to visiting only the drifter cumulant as that is the only goal where visiting would improve the GVF prediction. When using SF GVF learners, this behavior emerges, but under TB GVF learners the agent incorrectly focuses on the distractor. This is even more pronounced for Sarsa (see Appendix F.2).

heading: 7 Experiments under Function Approximation
text: We evaluate our system in a similar fashion to the last section, but now under function approximation. We use a benchmark problem at the end of this section, but start with experiments in the TMaze modified to be a continuous environment, with full details described in Appendix E.1. The environment observation ot 2 R2 corresponds to the xy coordinates of the agent. We use tile coded features of 2 tilings of 8 tiles for the state representation, both for TB and to learn the SF.
The reward features for the GVF learners can be much simpler than the state-action features because they only need to estimate the cumulants, which are zero in every state except the goals. The reward features are a one-hot encoding indicating if s0 in the tuple of (s, a, s0) is in the pseudo-termination goals of the GVFs. For the Continuous TMaze, this gives a 4 dimensional vector. The reward features for GPI is state aggregation applied along the one dimensional line components. Appendix E.1 contains more details on the reward features for the GVF and behavior learners.

heading: Results for a Fixed Behavior and Learned Behaviors
text: Under function approximation, SF-NR continues to enable more effective tracking of the cumulants than the other methods. For control, GPI is notably better than Sarsa, potentially because under
function approximation eligibility traces are not as effective at sweeping back changes in behavior rewards and so the separation is more important. We include visitations plots in Appendix F.1, which are similar to the tabular setting.
Note that the efficacy of SF-NR and GPI relied on having reward features that did not overly generalize. The SF learns the expected feature vector when following the target policy. For the GVF learners, if states on the trajectory share features with states near the goal, then the value estimates will likely be higher for those states. The rewards are learned using squared error, which unlike other losses, is likely only to bring cumulant estimates to near zero. These small non-zero cumulant estimates are accumulated by the SF for the entire trajectory, resulting in higher error than TB. We demonstrate this in Appendix F.3. We designed reward features to avoid this problem for our experiments, knowing that effective reward features can and have been learned for SF [Barreto et al., 2020].

heading: Results using Replay
text: The above results uses completely online learning, with eligibility traces. A natural question is if the more modern approach of using replay could significantly change the results. In fact, early versions of the system included replay but had surprisingly negative results, which we later realized was due to the inherent non-stationarity in the system. Replaying old cumulants and rewards, that have become outdated, actually harms performance of the system. Once we have the separation with the SF, however, we can actually benefit from replay for this stationary component.
We demonstrate this result in Figure 3c. We use = 0 for this result, because we use replay. The settings are otherwise the same as above, and we resweep hyperparameters for this experiment. SF-NR benefits from replay, because it only uses it for its stationary component: the SF. TB, on the other hand, actually performs more poorly with replay. As before, LSTD which similarly uses old cumulants, also performs poorly.
Incorporating Interest
To study the effects of interest, a more open world environment is needed. The Open 2D World is used to analyze this problem as described in Appendix E.2. At the start of each episode, the agent begins in the center of the environment. The interest for each GVF in the states is one if the state is in the same quadrant as the GVF’s respective goal, and zero otherwise. This enables the GVFs to focus their learning on a subset of the entire space and thus use the function approximation resources more wisely and give a better weight change profile as an intrinsic reward to the behavior learner. Each GVF prediction i is evaluated under
state-action weighting induced by running ⇡i, with results in Figure 4.
Both TB with interest and ETB reweight states to focus more on state visitation under the policy. Both significantly improve performance over not using interest, both allowing faster learning and reaching a lower error. The reweighting under ETB more closely matches state visitation under the policy, and accounts for the impacts of bootstrapping. We find that ETB does provide some initial learning benefits. The original ETD algorithm is known to suffer from variance issues; we may find with variance reduction that the utility of ETB is even more pronounced.

heading: Validation of the Multi-Prediction System in a Standard Benchmark Problem
text: Finally, we investigate multi-prediction learning in an environment not obviously designed for this setting: Mountain Car. The goal here is to show that multi-prediction learning is natural in many problem settings, and to show results in a standard benchmark not designed for our setting that has more complex transition dynamics. In the usual formulation the agent must learn to rock back and forth building up momentum to reach the top of the hill on the right—a classic cost to goal problem. This is a hard exploration task where a random agent requires thousands of steps to reach the top of the hill from the bottom of the valley. Here we use Mountain Car to see if our approach can learn about more than just getting out of the valley quickly. We specified a GVF whose termination and policy focuses on reaching top of the left hill, and a second GVF about reaching the top of the other side. The full details of the GVFs and setup of this task can be found in the Appendix E.3.
Figure 5a shows how GPI and Sarsa compare against a baseline random policy. GPI provides much better data for GVF learning than the random policy and Sarsa, significantly reducing the RMSE of the learned GVFs. The goal visitation plots show GPI explores the domain and visits both GVFs goal far more often than random, and more effectively than Sarsa.

heading: 8 Conclusion
text: In this work, we take the first few steps towards building an effective multi-prediction learning system. We highlight the inherent non-stationarity in the problem and design algorithms based on successor features (SF) to better adapt to this non-stationarity. We show that (1) temporally consistent behavior emerges from optimizing the amount of learning across diverse GVF questions; (2) successor features are useful for tracking nonstationary rewards and cumulants, both in theory and empirically; (3) replay is well suited for learning the stationary components successor features while meta-learning works well for the non-stationary components; and (4) interest functions can improve the performance of the entire system, by focusing learning to a subset of states for each prediction.
Our work also highlights several critical open questions. (1) The utility of SFs is tied to the quality of the reward features; better understanding of how to learn these reward features is essential. (2) Continual Auxiliary Task Learning is an RL problem, and requires effective exploration approaches to find and maximize intrinsic rewards—the intrinsic rewards do not provide a solution to exploration. Never-ending exploration is needed. (3) The interaction between discovering predictive questions and learning them effectively remains largely unexplored. In this work, we focused on learning, for a given set of GVFs. Other work has focused on discovering useful GVFs [Veeriah et al., 2019, 2021, Nair et al., 2020, Zahavy et al., 2021]. The interaction between the two is likely to introduce additional complexity in learning behavior, including producing automatic curricula observed in previous work [Oudeyer et al., 2007, Chentanez et al., 2005].
This work demonstrates the utility of several new ideas in RL that are conceptually compelling, but not widely used in RL systems, namely SF and GVFs, GPI with SF for control, meta-descent step-size adaption, and interest functions. The trials and tribulations that lead to this work involved many failures using classic algorithms in RL, like replay; and, in the end, providing evidence for utility in these newer ideas. Our journey highlights the importance of building and analyzing complete RL systems, where the interacting parts—with different timescales of learning and complex interdependencies—necessitate incorporating these conceptually important ideas. Solving these integration problems represents the next big step for RL research.

heading: Acknowledgments and Disclosure of Funding
text: This work was supported by NSERC Discovery, IVADO, CIFAR through CCAI Chair funding and by the Alberta Machine Intelligence Institute (Amii).

Review summaries:
This paper considers the setting where an RL agent has to learn to make auxiliary predictions, and captures each prediction task as an RL task. In particular, the goal is to maximize the learning progress for each prediction task. Specifically, this is measured by the l1-norm of the change in weights and introduced as an intrinsic reward.  However, this multi-prediction problem is difficult because of multiple sources of non-stationarity, i.e., from the changing rewards (which shrink as the agent makes better predictions) and from the changing agent behavior. To address this non-stationarity, the successor features framework is leveraged. That is, they can use learned successor features to efficiently track the non-stationary rewards and to correct state distribution changes by importance sampling.

This work addresses the multi-prediction problem in MDPs, with key focus on how to generate and adapt the behavior to optimize auxiliary predictions in the absence of task rewards.  They show that the rewards for the behavior have inherent non-stationarity. The proposed method approximates successor features (via expected SARSA and Tree Backup) and then uses them to learn value predictions (via regression updates). This specific separation allows for a faster convergence rate as proved by the authors.

The paper proposes a framework for continually learning multiple generalized value functions, where each value function is learned off-policy and the behaviour policy learns to maximize the learning progress. The paper identifies the non-stationarity of the action value function during the process of maximizing learning progress and proposes an algorithm that separately learns the immediate reward and the successor feature. The experimental results show that the proposed algorithm significantly improves sample efficiency and perfroms well with the use of replay.