Proto-Value Networks: Scaling Representation Learning with Auxiliary Tasks
Authors: Jesse Farebrother
Joshua Greaves
Rishabh Agarwal
Charline Le Lan
Ross Goroshin
Pablo Samuel Castro
Marc G Bellemare
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning
representation learning

Abstract: Auxiliary tasks improve the representations learned by deep reinforcement learning agents. Analytically, their effect is reasonably well-understood; in practice, how-ever, their primary use remains in support of a main learning objective, rather than as a method for learning representations. This is perhaps surprising given that many auxiliary tasks are defined procedurally, and hence can be treated as an essentially infinite source of information about the environment. Based on this observation, we study the effectiveness of auxiliary tasks for learning rich representations, focusing on the setting where the number of tasks and the size of the agent’s network are simultaneously increased. For this purpose, we derive a new family of auxiliary tasks based on the successor measure. These tasks are easy to implement and have appealing theoretical properties. Combined with a suitable off-policy learning rule, the result is a representation learning algorithm that can be understood as extending Mahadevan & Maggioni (2007)’s proto-value functions to deep reinforcement learning – accordingly, we call the resulting object proto-value networks. Through a series of experiments on the Arcade Learning Environment, we demonstrate that proto-value networks produce rich features that may be used to obtain performance comparable to established algorithms, using only linear approximation and a small number (~4M) of interactions with the environment’s reward function.

Published as a conference paper at ICLR 2023
PROTO- VALUE NETWORKS: SCALING REPRESENTA- TION LEARNING WITH AUXILIARY TASKS
Jesse Farebrother 1135 Joshua Greaves" "5, Rishabh Agarwal 235,, Charline Le Lan" Ross Goroshin 5 Pablo Samuel Castro s, Marc G. Bellemare i 35
ABSTRACT
Auxiliary tasks improve the representations learned by deep reinforcement learning agents. Analytically, their effect is reasonably well-understood; in practice, how- ever, their primary use remains support of a main learning objective, rather than as a method for learning representations. This is perhaps surprising given that many auxiliary tasks are defined procedurally, and hence can be treated as an essentially infinite source of information about the environment. Based on this observation, we study the effectiveness of auxiliary tasks for learning rich representations, focusing the setting where the number of tasks and the size of the agent's ss network are simultaneously increased. For this purpose, we derive new family of auxiliary tasks based on the successor measure. These tasks easy to implement and have appealing theoretical properties. Combined with a suitable off- off-policy learning rule, the result is representation learning algorithm that be understood extending Mahadevan & Maggioni] (2007)'s proto-value functions to deep reinforcement learning - accordingly, we call the resulting object proto-value networks. Through a series of experiments on the Arcade Learning Environment, we demonstrate that proto-value networks produce rich features that may be used to obtain performance comparable to established algorithms, using only linear approximation and small number (-4M) of interactions with the environment's reward function.
INTRODUCTION
In deep reinforcement learning (RL), an agent maps observations to a policy or return prediction by means of neural network. The role of this network is transform observations into series of successively refined features, which are linearly combined by the final layer into the desired prediction. A common perspective treats this transformation and the intermediate features produces as the agent's representation of its current state. Under this lens, the learning agent performs two tasks simultaneously: representation learning, the discovery of useful state features; and credit assignment, the mapping from these features to accurate predictions.
Although end- and-to-end RL has been shown to obtain good performance in a wide variety of prob- lems (Mnih al. 2015 Levine et al.) 2016 Bellemare et al. 2020), modern RL methods typically incorporate additional machinery that incentivizes the learning of good state representations: for example, predicting immediate rewards (Jaderberg et al.) 2017). future states (Schwarzer et al. [202 or observations (Gelada et al.) 2019);; encoding a similarity metric (Castro) 2020; Agarwal et al. 2021a Zhang al. [221); and data augmentation (Laskin et al. 2020). In fact, it is often possible, and desirable, to first learn a sufficiently rich representation with which credit assignment can then be efficiently performed; in that sense, representation learning has been
aspect of RL from 1996 Ratitch & Precup 2004; Mahadevan &
its early days (Sutton & Whitehead 1993; Sutton.
Maggioni 2007: et al. 2008 Konidaris al. 2011 Sutton al. 2011).
An effective method for learning state representations is to have the network predict a collection of auxiliary tasks associated with each state (Caruana [997] Jaderberg et al. [017 Chung et al. 2019).
In an idcalized setting, auxiliary tasks can be shown to induce a set of features that correspond to
Conresonndence to: Jesse Farebrother <jfarebro@cs .ttptssmmm..lll.. 1ig.l.1..0 ca> McGill University." Université de Montréal, 3 Mila - Québec Al Institute, University of Oxford Google Research Brain Team," Equal contribution, CIFAR Fellow.

---

Published as a conference paper at ICLR 2023
the principal components of what is called the auxiliary task matrix (Bellemare et al. 2019 Lyle
jet al. 2021|000 Le Lan et al. (2022)). This makes it possible to analyze the theoretical approximation
error (Petrik [007]] Parr et al.] 2008), generalization (Le Lan et al. 2022b), and stability (Ghosh & Bellemare 2020 of the learned representation. Perhaps surprisingly. there is comparatively little that is known about their empirical behaviour larger-scale environments. In partieular, the scaling properties of representation learning from auxiliary tasks i..., the effect of using more tasks, or increasing network capacity - remain poorly understood. This paper aims to fill this knowledge gap.
Our approach is to construct a family of auxiliary rewards that can be sampled and subsequently. Specifically, we implement the successor measure (Blier et al. 2021] Touati & Ollivier| 2021), which extends the successor representation (Dayan 1993) by replacing state- quutteeguliity with set-inclusion. In our case, these sets are defined implicitly by a family of binary functions over states. We conduct most of our studies on binary functions derived from andomly-initialle as random cumulants has already been demonstrated (Dabney et al., 202T).
networks, whose effectiveness
Although our results may hold for other types of auxiliary rewards, our method has a number of benefits: can be trivially scaled by sampling more random networks to serve as auxiliary tasks, directly relates to the binary reward functions common of deep RL benchmarks, and can to some extent be theoretically understood. The actual auxiliary tasks consist in predicting the expected return of the random policy for their corresponding auxiliary rewards; in the tabular setting, this corresponds to proto-value functions (Mahadevan & Maggioni 2007 Stachenfeld et al., 2014 Machado et al. 2018). Consequently, we call our method proto-value networks (PVN).
We study the effectiveness of this method on the Arcade Learning Environment (ALE) (Bellemare) jet al. 2013). Overall, find that PVN produces state features that are rich enough to support linear value approximations that are comparable to those of DQN (Mnih et al., 2015) on a number of games, while only requiring a fraction of interactions with the environment reward function. We explore the features learned by PVN and show that they capture the temporal structure of the environment, which we hypothesize contributes to their utility when used with linear function approximation.
In an ablation study, we find that increasing the value network's 's capacity improves the performance of our linear agents substantially, and that larger networks can accommodate more tasks. Perhaps surprisingly, we also find that our method performs best with what might seem like small number of auxiliary tasks: the smallest networks we study produce their best representations from 10 or fewer tasks, and the largest, from 50 to 100 tasks. In sense, this finding corroborates the result of Lyle ct al. (202T, Fig. 5), where optimal performance (on a small set of Atari 2600 games and with the standard DQN network) was obtained with single auxiliary task. From this finding hypothesize that individual tasks may produce much richer representations than expected, and the effect of any particular task fixed-size networks (rather than the idealized, infinite-capacii setting studied in the literature) remains incompletely understood.
2 RELATED WORK
Deep RL algorithms have employed auxiliary prediction tasks to learn representations with various emergent properties (Schaul et al. 2015 Jaderberg et al., 2017: Machado et al., 2018 Bellemare et al. 2019 Gelada et al. 2019 Fedus et al. [019 Dabney et al. 2021 Lyle et al. (202). While most of these papers optimize auxiliary tasks in support of reward maximization from online interactions, our work investigates learning representations solely from auxiliary tasks on offline datasets. Closely related to our work is the study of random cumulants (Dabney et al., 2021 Lyle et al. 2021).
both of which identify random cumulant auxiliary tasks as being especially useful in sparse-reward environments. Our work differs from these prior works in both motivation and implementation.
Notably absent in prior work on random cumulants is the study of representational capacity as function of the number of tasks.
Another body of related work on decoupling representation learning from RL primarily revolves around the use of contrastive learning (Anand et al.) 2019 Wu et al. 2019: Stooke et al. 1021 Schwarzer et al. 202 Erraqabi et al., 2022). Anand et al. (219)) proposed ST-DIM, a collection of temporal contrastive losses operating on image patches from environmental observations. Although the representations learned by ST-DIM are able to predict annotated state-variable variiabes in Atari 2600 games, their pretraining method was never evaluated for control. SSooke et al. (202I) uses contrastive learning for learning the temporal dynamics, resulting in minor improvements in online control from
2

---

Published as a conference paper at ICLR 2023
fixed representation. Additionally, Schwarzer Schhaarre al. (2021b) augments next-state prediction with goal-conditioned RL and inverse dynamics modelling. enabling strong performance on Atari 100k benchmark (Kaiser et al., 2020). Our work is complementary to these prior works and investigates the utility of scaling auxiliary tasks for learning good representations, which in principle can be easily combined with existing approaches. Additionally, recent work using state-similarity metrics tackles the representation learning problem through the lens of behavioral similarity (Castro et al., 202T; Zhang et al., 202T; Agarwal al.
2021a). We note that, in contrast our method, the behavioral metrics used in these works are heavily based on the reward structure of the environment.
Related to our method, Touati & Ollivier (2021) consider representation learning with the successor measure (see also Touati 2021 Algorithm 7). Algorithnically, their approach differs from ours in a number of ways, including the use of learned state density function lieu of indicator functions, the decomposition of the successor measure into its so-called forward and backward representations, and a bespoke sampling procedure to generate sample trajectories from which the representation is learned. By comparison,
approach directly constructs a relevant set of auxiliary tasks, which results in a significantly simpler algorithm that is more easily scaled according to available computational resources and to the full gamut of Atari 2600 games,
will demonstrate.
Recently, there have also been efforts to cast the representation learning problem in RL as a min- max objective where you learn state features that can linearly represent specific class of value-functions (Bellemare et al. 2019) or the Bellman backup itself (Modi et al. 2021 Zhang et al. 2022). Although do not frame our method in terms of min-max formulation, we do seek to learn a representation that can linearly predict the value function of the random policy for any given reward function. These previous works are primarily theoretical in nature and often require specific assumptions about the underlying MDP. In contrast, our class of auxiliary prediction tasks allows us to learn representations in environments with large, high- sigh--imenssonal state- spaces, without any prior assumptions.
BACKGROUND
The RL problem can be modeled as a Markov Decision Process (MDP) defined by the 5-tuple M = (X', (X", scalar reward function, P X'x x + (X)) is transition function that maps state-action pairs to distribution over next states, and function that maps states to a distribution over actions.
..R. R, P. 7), in which X' is a set of states, A is set of actions, R. X x A + R is
[0, 1) is a discount factor. A policy π X + P (AA) is
The goal of an RL agent is to learn policy that maximizes the cumulative discounted rewards from the environment, also known as the discounted return. The state-action value function is defined as the expected discounted return when starting in a state and following the policy n:
Q" (z((z))== :=
E AP=R,P
Σ ''R(X,, Ab) Xo Ao -
In this paper, consider approximating the value function Q using linear combination of features. We call the map Φ X' + a k-dimensional state representation; ((x) is the feature vector for a state x E X. The value function approximant at (I. a) is
Q a) = x(x)] wa.
where wa E R is a weight vector associated with action a. In deep RL., the state representation is parameterized by a neural network. Often, the representation is learned end-to-end by optimizing the parameters to make more accurate predictions about the value function. Additional predictions that further shape the state representation we write T for the set of auxiliary tasks.
called auxiliary fasks (Jaderberg al. 2017). In this work,
The successor representation (SR; Dayan 1993) encodes the temporal structure of the MDP in terms of which states can be reached from any other state under a given policy. It is given by
20
S (x, a, F)
Σ r PPp( = x - x, Ag = a, Atzo-z).
convenient, recursive form expresses the SR terms of an indicator function, highlighting that for each ã. the SR is the value function associated with the reward function R(ar, a) = 1( T):
t (x, a, .)) 1 fx +}- + E, [viu (X', A', X x, = a].
3

---

Published as a conference paper at ICLR 2023
4 PROTO-VALUR NETWORKS
In this section, we derive our proto-value networks algorithm. At high level, this algorithm learns a state representation that approximates the singular vectors associated with the successor measure, the extension of the SR to continuous state spaces, We do this in order to derive an algorithm that is more suitably tailored to the large state spaces of deep RL domains, where many states encountered once or never at all, and some notion of distance between states must be accounted for.
To gain some understanding into this process, let consider how the method of auxiliary tasks (Jaderberg et al. 2017) can be used to obtain state representation that approximates the SR. In the tabular setting, where X' and are of finite sizes and m respectively, we write the feature matrix + E Raxd, so that each state is associated with a feature vector ((x) E R Given an auxiliary task matrix V E Ruxm the method of auxiliary tasks can be shown to be equivalent to minimizing the loss function
C W) = ||&W 11?
Σ (6(x) wi (x)))²
SEX,EET
jointly with respect to & and W. Here, W E _Rdx is a weight matrix with columns (w;) and (x(2)) is the entry of V corresponding to state x and task i. In the sequel, we will assume that near-optimal W can be obtained easily and simply consider the loss
((Φ) min L(Φ, W),
to be minimized over 4 It is known (e.g.. Bellemare et al. 2019) that any feature matrix that minimizes this loss function must have columns that lie in the subspace spanned by the top left singular vectors of V. In particular, when v/ is square and symmetric the auxiliary task method recovers the subspace spanned by its top d cigenvectors.
Here, interested in the setting in which Th is the SR matrix for the uniformly random policy. In the symmetric case, the eigenvectors of Th form what is called the proto-value functions of the MDP (Mahadevan & Maggioni] 2007) These eigenvectors are of special importance because they encode the spatial structure of the MDP in terms diffusion process, and have been shown to correlate with neural encodings of spatial location in mammals (Stachenfeld al. 2014).
4.1 EXTENSION TO THE RANDOM SUCCESSOR MEASURE
Let be a policy and Σ the power set of X' The successor measure 30 X' x x + R extends the SR to quantify the discounted visitation frequency of an agent, in expectation over trajectories and for various subsets of the state space (Blier et al. 202T). Given set S C X, we write
Sd (x =
S|x, x, As Arso 7}. /P((x,
As with the SR, this can be expressed in terms of an expectation over an indicator function, and further decomposed in a Bellman equation:
S) (T,
Σ Ex [1 ( x, Ao a, Ar ~ m]
1 E S
E. 1 (X', A', X = a=
The passage from state equality to set inclusion is particularly appealing in deep RL: first, because states rarely repeat along trajectory or between episodes, the indicator 1 = y is almost always zero. Second, set inclusion allows us to incorporate a notion of closeness to "े.T e.g. by focusing on subsets S that include semantically similar states. We will return to this point later in the section.
By analogy with the tabular setting, let us now define a loss function which, if suitably minimized, should produce useful state representation. For ease of exposition, continue to assume that X' is
Behzadian & Petrik (018)) gives the singular-vector extension for the asymmetric case. Because this extension is straightfforard and symmetry rarely holds, in this paper use the term proto-value networks to describe representations learned both the symmetric and asymmetric settings.
4

---

Published as a conference paper at ICLR 2023
finite, although perhaps very large; the reader interested in proper mathematical treatment of the full continuous-stee setting is invited to consult Blier et al. (2021) and Pfau et al. (2019).
Let & be distribution over subsets of states and E R=x= is diagonal matrix with entries (5(x) a E } on the diagonal. The Monte Carlo successor measure loss is
(MCSM( min E
Σ ZEX,aEA
(6(x)"us,, us,a - (2,
Wa.a ERd Sing
Theorem 1. O is feature matrix minimizing (MCSM( (D), then its column space spans the top d left singular vectors of the (infinite- (infinite-dimennte dimensional) successor measure matrix 1p" with respect to the inner product (x, y)= = y Ex. for all x: y. RR
In practice, samples of (x, a, S) (which must be estimated from complete trajectories) are not available; instead, it preferable learn an approximation by bootstrapping (Sutton & Barto 2018). The corresponding lemporal-iiffeenne difference successor measure loss is
min E
Σ
(1fx E 8} +> (>x'd(X)) WSSA = == o(x) wssa) (1)
WSS M ERd S
we will use this form in the derivations that follow.
4.2 A PRACTICAL IMPLEMENTATION
Our algorithm aims approximate the loss in Equation [ using tools from deep RL. We first approximate the expectation over by sampling collection of sets (S,) from Ş. These sets are kept fixed throughout learning. With this in mind, each set corresponds to an indicator function that
we treat as binary reward function ra():) 1 (xr E S.). The actual auxiliary task is then the value function of the random policy associated with this reward.
Denote by (x, a) the prediction made by our neural network for state æ, action a, and the set S.. Given sample transition (z,, a, x'), we define the sample target
(x) +
Σ "a'a'aaa) d'EA
[AI
Notice that the average over the next-action a' arises as a consequence of taking the policy т to be uniformly random. We then train the neural network by performing stochastic gradient descent on the loss derived from this sample target:
(r((x) +
- a))
Σ a'EA
A
Following common usage, the actual gradient estimate is obtained by aggregating multiple transitions into a minibatch and applying the Adam optimizer (Kingma & Ba, 2015).
Before explaining how the sets S, are defined, let us remark of these auxiliary tasks, when viewed from a deep RL perspective. First, the use of random policy means that learning usually proceeds in an off-policy manner. However, we expect this to be a relatively mild form of off-policy learning, one that is in general much more stable than one derived by maximization, as in Bellman optimality equation. Although one could also learn the value function associated with the current policy (as in SARSA (Rummery & Niranjan 1994)), this precludes the use of offline datasets for learning the representation, or least makes the learned representation strongly dependent on the behaviour policy. By contrast, the representation learned by PVN only depends on the availability of data. In effect, these auxiliary tasks depend only on the structure of the environment, and not the agent's 's behaviour.
number of appealing properties
We also expect binary reward functions to be easier to tune than, say, those derived from a distance function (dependent on getting the scale parameter correct) real-valued random rewards (dependent on the underlying distribution). Binary rewards are particularly appealing in domains where the reward function is itself binary ternary (i.e., Atari 2600 video games), in which case they can be adjusted to have similar statistics to the true reward function. We will demonstrate how to do this in the following section.
5

---

Published as a conference paper at ICLR 2023
(xex: x2)1)
fx (()=m)
91.8)
Indosks
(a) One-Honee Hot Encoding.
(b) Random Network Indicator.
Figure I: (a) State equality indicator implemented as a one-hot encoding over X, as in the Successor Representation, while (b) Random Network Indicators parameterize the sets S; in PVN. Each panel shows a grid world with a reward function rax) derived from the associated indicator. The transition arrow is the process of learning the value function from the preceding reward function.
4.3 GENERATING INDICATOR FUNCTIONS
Thus far we have described our algorithm as sampling sets of states (S.) which are then converted into reward function by means of an indicator. deep RL, this is inconvenient for two reasons: first, because it is not clear from what distribution of states should be sampled (how should one generate arbitrary video-game states?); second, because testing for inclusion may also be brittle, effectively reducing to repeated equality tests. Instead, we opt here for an implied set, defined directly by its indicator function.
Let F be family of functions mapping X' to {0. 1}. Then, for any function f E F, its implied set is
S fx E X f(x) =
Of course, this is equivalent to
(x) E Sy}.
Sampling functions from F according to some distribution & and using them in lieu of the indicator therefore equivalent to sampling sets states for some distribution & implied by Ey. The advantage that testing for inclusion in Sy only requires the evaluation of f at z, which for carefully-chosen functions can be done at little computational cost.
The simplest scenario occurs when the family F is parametrized by some weight vector 0, that the random function fo corresponds to a random set of states. In this paper we consider two such families of functions: universal hash functions and random network indicators. Both families are tunable, in the sense that they are parametrized so that the implied sets Sy each cover a desired fraction of the overall state space. probabilistic terms, tunable means that we can with minimal computation find parameters such that for any given state T,
P(r E
Here, the probabilistic statement is with respect to the draw of f from F. For universal hash functions, the tuning immediate from the algorithm, and so we describe first.
A Carter- Wegman family of hash functions Few (Carter & Wegman 1979) consists of functions mapping each integer æ N to the set (O..... ..... k 1}. with the property that
P(M(z) = i] I for i 0, O,..,,k-1
where the probabilistic statement over the random draw of h from Few. One may think of a CW family as deterministically assigning labels to integers (in the sense that is deterministic), but randomly (in the sense that f is random). See Appendix D.I for full implementation details.
We construct our tunable indicator function
f(x) 1(h(z) 0)
By construction, choosing = yields the desired tuning (up to integer rounding). In our setting, is high-dimensional observation (for example, image) rather than integer; yet will see that, perhaps surprisingly, encoding each image as unique integer is sufficient to produce better-than-rander state representations.

---

Published as a conference paper at ICLR 2023
One drawback of using universal hash functions define sets of interest is that they may assign different values to perceptually near identicll states (a single pixel difference suffices). Following common usage (Burda et al. 2019 Dabney et al., 202I), we may networks to map similar states to similar values. Specifically, let us view a randomly initialized, single-output DQN network function g X' - IR. We further decompose this function into map 91 X' + I2' and linear map from IR' + R:
randomly initialized neural
g(x) 91 (z) bb
where w is a parameter vector and E a bias term. With this in mind, we may simply construct the indicator function]
f(z) = l(g(z) > 0}.
The result, however, is not yet tunable: it is hard choose the right distribution of network weights
so that desired fraction of states satisfy f(x) = 1. However, for any E [O, 1] and any non-zero fixed wi gt, and distribution of states μu, there exists a bias term d' such that
P Pawy (a) w D' =P
Such bias term can accurately be determined from small number of online interactions using the method of quantile regression (Koencker 2005); the exact update rule is given in Appendix D.2 With this method, we obtain network-derived indicator functions that are tunable and are likely to assign similar values to perceptually similar states. We refer to this class of indicator functions as random network indicators (RNIs; Figure []. which we empirically evaluate in the following section.
5 EMPIRICAL ANALYSIS
To disentangle the contributions of the primary and auxiliary tasks the expressiveness of the learned features, we split our learning procedure in two parts; a representation pre- pre-training phase, and online RL phase. During the representation pre-training phase, we transition data from offline Atari datasets RL Unplugged (Agarwal et al.) [020]] Gulcehre et al.) (0220) and the procedure deseribed in [Section to train an encoder which acts feature extractor (see Appendix [D] for complete implementation details). Note that while this dataset contains environment rewards, none of the methods make use of the environment rewards unless explicitly stated. Following the pre-training phase, we fix the weights of the learned encoder and train an RL agent online directly from this "frozen" representation. Notably, we train for only 3.75 million agent steps, compared to the 50 million agent steps (200M Atari 2600 frames) that is standard in most Atari setups. Our agents are implemented using the Acme library (Hoffman et al. (020). Our hyperparameter choices for both phases of training can be found in Appendix D.5
5.1
SCALING CAPACITY WITH AUXILIARY TASKS
Prior work indicates that the optimal number of auxiliary tasks for representation learning is un- expectedly small, and that scaling up the number of auxiliary tasks can hurt performance (Lyle) et al. 2021 Fig. 5). We expect that the representational capacity of the neural network has strong effect on the number of auxiliary tasks we are able to learn with. To study this effect, we use the Impala-CNN network (Espeholt et al. 2018) and vary its effective width; that is, multiply the number of convolutional filters and the number of features in the penultimate layer. We select a width multiplier in the set {1, 2, 4, 8} and sweep the number of tasks from (0, 10, ..... 100). For this experiment, we use 5 games (ASTERIX, BEAM RIDER, PONG, QBERT, and SPACE INVADERS) with 3 seeds for pre-training, resulting in 15 encoders for each combination of width multiplier and number of auxiliary tasks. During the online phase, we train with 3 seeds per encoder, resulting in a total of 45 runs per sweep configuration. We evaluate for 100 episodes after 1M agent steps.
We summarize our results using Rliable (Agarwal et al. 20216). Figure 3 depicts the optimality gap (distance from human-level performance). We find that increasing the representational capacity of the network increases performance, even for very small number of tasks. This is perhaps surprising, since it indicates that we only need handful of tasks to train large-scale representations, corroborating results by Lyle et al. (202T). Though a small part of this performance gain might be obtained just by virtue of having more output features (following the lottery ticket hypothesis
This corresponds using a SIGN nonlinearity the end of the network.
7

---

seeds for Published as a conference paper at ICLR 2023
PVN (RMI)
PVN (Hash)
0.7
0.5
Environment Reward
Randem in halizattin
0.3
0.2
0.1
100
Number Tasks
Figure 2: MDS plots the features learned by PVN and other baseline methods. Each plotted point corresponds to a state in a single trajectory on the game CHOPPER COMMAND. The episode starts with the dark purple points and ends with the light yellow points, Environment Reward corre- sponds to features learned by optimizing the environment reward directly.
Figure 3: Performance of agents performing linear value approximation on top of learned PVN. Agents are trained for 4 million environment frames; the legend indicates the network size as capacity multiplier. Scal- ing network capacity with the number of auxiliary tasks leads to better performance. Larger networks support larger number of auxiliary tasks.
(Frankle Carbin 2019)). we can see that there marked improvement when we increase the number of auxiliary tasks from 0 for all network sizes.
We further find that as network capacity is increased, the algorithm can use more auxiliary tasks to improve its representation. For example, while the 2x network achieves maximal performance with 10 tasks, the 8x network performs best in the range of [50, 100] tasks. This gives evidence for the scalability of PVN an approach for learning rich state representations.
5.2 EVALUATING THE LEARNED REPRESENTATION
Using the insights gained from our scaling experiment, we evaluate a model with a large number of auxiliary tasks broader suite of Atari games. We use the 8x network and fix the number of auxiliary tasks to 100, which empirically performed well. We use the same training setup described in the previous section, though we all 46 games available in RL Unplugged. We
offline pre-training, and 3 additional seeds per encoder during online training. We train for 3.75M agent steps, and evaluate for 100 episodes. We compare against the following pre-training baselines:
Random Initialization: Randomly initialized features using the same network architecture. This simple baseline should confirm that the efficacy of our representations come from our pre-training procedure, and not merely because we use large encoder network.
Random Cumulants (RCs): Random reward functions introduced by Dabney al. (202) and later expanded upon by Lyle et al. (2021). This method is similar to ours, but uses random reward r. r1(x, s (f(x') f()) instead of the random indicator function, and replaces the average over next-state actions by maximization (off-policy learning of the optimal policy for each cumulant). Here, f is also given by random network.
Self-Predictive Representations (SPR): A contrastive-leaming method that directly optimizes for temporal consistency the learned representation (Schwarzer et al.) 2021a). It does so by learning a latent-space transition model and forcing subsequent states to have similar representations.
Behavior Cloning (BC): Behavior Cloning has been shown as strong baseline in Offline RI, especially when increasing the amount of pre-training data (Schwarzer et al.) 2021b Baker et al.) 2022). should give a strong indication of the performance that is possible when using large datasets.
For each of these methods, freeze the 8x encoder after the pre-training stage and use the previously- described online training scheme. Figure illlustrates that PVN outperforms these baselines in all aggregate metrics. We also note that PVN using linear function approximation (3.75M agent interactions) is competitive with DQN (50M agent interactions) in many games, as illustrated the per-game results found in Appendix
8

---

Published as a conference paper at ICLR 2023
IQM
Optimality Gap
PVN (RNI)
Random Cumulants SPR
Behavior Cloning
Initialization
0.00
0.15
0.30
0.450.00
0.15
0.30
0.450.0
0.5
1.0
1.5
0.60
0.75
0.90
1.05
Human Normalizedd Score
Figure 4: Performance of PVN RNI other methods described in Section seeds, aggregated across 46 Atari games.
5.2
Computed using 125
Median
1QM
Mean
Optimality Gap
PVN (RNI)
PVN (RNI Opt. Policy)
Random initializattin
0.00
0.15
0.30
0.450.00
0.15
0.30
0.450.0
0.5
1.0
1.5
0.60
0.75
0.90
1.05
Human Normalized Score
Figure 5:
PVN (Hash): PVN with hash indicator functions. PVN (RNI): PVN with random network indicators. A randomly initialized network with (8x) capacity plotted for comparison.
We visualize the learned representations from different methods using multidimensions. scaling (MDS) plots in Figure (with more games in Appendix [). These plots show that different methods clearly lead to representations with different structures. Notably, the representations learned by PVN (RNI) place temporally successiv states close together, and appears to capture information about the dynamics of the environment without requiring access to the environment reward.
5.3 ABLATIONS
We perform ablative experiments to verify the importance of the different PVN components. First, we validate our choice of indicator function by replacing RNIs with the hash indicator functions described in Section We compare their performance in Figure which shows that hash indicator functions perform poorly compared to RNIs; this indicates that the choice of indicator function an important design decision. We expect that the inductive biases in random convolutional networks allow RNIs to include a notion of state similarity the tasks they induce.
Next, we hypothesize that using the random policy the target policy is key contributor to PVN's performance. To verify this hypothesis, we ablate the TD-target our learning update to maximize over the next-state action-values, replaced with the max function the TD backup, PVN attempts to learn the optimal value function for each indicator function. rather than the value function of the random policy. The result of this experiment can be seen in Figure 5) Using the mean formulation has a much higher median human normalized score than the max formulation. This is likely due to instability that arises from max bias and state coverage due to the off-policy learning required for the optimal value function. Learning the value function of the random policy also requires off-policy learning; however, we predict that doesn't It have such a large effect, as we previously described in Section
per the Bellman optimality equation. When the mean function is
DISCUSSION
While our experiments have shed some light on the scalability of auxiliary tasks, there are a number of remaining open questions that represent exciting opportunities for further exploration. An exciting future direction to use insights from the literature on scaling models effectively (Tan & Le 2019 to further scale the auxiliary tasks we introduced here. Orthogonally. it may still be possible to train with more tasks without increasing the capacity of the network. It is surprising that with even a relatively large network with tens of millions of parameters, such as Impala (8 x), the network only supports handful tasks. It not clear why training with more tasks leads to worse performance, especially for smaller Impala architectures. Finally, in line with /ith//aarwal et al. (2022), our pre- mre-trained representations, (see Appendix(D D) which we hope will enable researchers to tackle credit assignment the ALE without needing re-learn such representations.
have open-sourced

---

Published as a conference paper at ICLR 2023
ACKNOW
We thank Nathan U. Rahn, Max Schwarzer, Harley Wiltzer, Wesley Chung, Adrien Ali Taiga, Pierluca D'Oro, David Meger, and Doina Precup for their useful feedback on this work. A special thanks to Wesley Chung for completing the tabular proof presented in Appendix C. This work was supported by the National Sciences and Engineering Research Council of Canada (NSERC) and the Canada CIFAR AI Chair program.
We also acknowledge the Python community whose contributions made this work possible. In particular, this work made extensive use of Jax (Bradbury et al. 2018), Flax (Heek et al., 2023), Optax (Babuschkin et al., 2020), Numpy (Harris et al. (020), Pandas (Wes McKinney| Matplotlib (unter (007), and Seaborn (Waskom, 2021).
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective offline reinforcement learning. In International Conference on Machine Learning (ICML), 2020.
Rishabh Agarwal, Marlos C Machado, Pablo Samuel Castro, and Marc G Bellemare. Contrastive behavioral similarity embeddings for generalization in reinforcement learning. In International Conference on Learning Representations (ICLR), 2021a.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Mare Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Neural Information Processing Systems (NeurIPS), 2021b.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro. Aaron Courville, and Marc G Bellemare. Beyond tabula rasa: Reincarnating reinforcement learning. Neural Information Processing Systems (NeurIPS), 2022.
Ankesh Anand, Evan Racah, Sherjil Ozair, Yoshua Bengio, Marc-Alexandre Côté, and R Devon Hjelm. Unsupervised state representation learning in atari. In Neural Information Processing Systems (NeurIPS). 2019.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurüi Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzie, Vladimir Mikulik, Tamara Norman, John Quan, George Papamakarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Luyu Wang, Wojeiech Stokowiec, and Fabio Viola. The DeepMind JAX Ecosystem, 2020.
Bowen Baker, Ilge Akkaya, Peter Zhokhov, Joost Huizinga, Jie Tang, Adrien Ecoffet, Brandon Houghton, Raul Sampedro, and Jeff Clune. Video pretraining (VPT): learning to act by watching unlabeled online videos. Neural Information Processing Systems (NeurIPS), 2022.
Bahram Behzadian and Marek Petrik. Feature selection by singular value decomposition for rein- forcement lcarning. In Proceedings of the ICML prediction and generative modeling workshop. 2018.
Marc G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research (JMLR), 47:253-279, June 2013.
Mare Bellemare, Will Dabney, Robert Dadashi, Adrien Ali Taiga, Pablo Samuel Castro, Nicolas Le Roux, Dale Schuurmans, Tor Lattimore, and Clare Lyle. A geometric perspective on optimal representations for reinforcement learning. In Neural Information Processing Systems (NeurIPS), 2019.
Mare G Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C Machado, Sub- hodeep Moitra, Sameera Ponda, and Ziyu Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77-82, 2020.
10

---

Published as a conference paper at ICLR 2023
Léonard Blier, Corentin Tallec, and Yann Ollivier. Learning successor states and goal-dependent values: A mathematical viewpoint. arXiv preprint arXiv:2101.07123, 2021.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL bttt::/ggituue www goom//ooole/jax
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 1979.
Rich Caruana. Multitask learning. Machine Learning, 28(1). 1997.
Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland. Mico: Improved representations via sampling-bass based state similarity for markov decision processes. In Neural Information Processing Systems (NeurIPS), 2021.
Wesley Chung, Somjit Nath, Ajin George Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. In International Conference on Learning Representations (ICLR), 2019.
Will Dabney, André Barreto, Mark Rowland, Robert Dadashi, John Quan, Mare G. Bellemare, and David Silver. The value-improvement path: Towards better representations for reinforcement learning. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 1993.
Carlos Diuk, Andre Cohen, and Michael L Littman. An object-oriented representation for efficient reinforcement learning. In International Conference on Machine learning (ICML), 2008.
Akram Erraqabi, Marlos C. Machado, Mingde Zhao, Sainbayar Sukhbaatar, Alessandro Lazaric, Ludovic Denoyer, and Yoshua Bengio. Temporal abstracttionsaugmmente temporally contrastive learning: An alternative to the laplacian in RL. arXiv, 2203. 1369, 2022.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learnet architectures. In International Conference on Machine Learning (ICML), 2018.
William Fedus, Carles Gelada, Yoshua Bengio, Mare G. Bellemare, and Hugo Larochelle. Hyperbolic discounting and learning over multiple horizons. arXiv, 1902.06865, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations (ICLR), 2019.
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G. Bellemare. DeepMDP: Learning continuous latent space models for representation learning. In International Conference on Machine Learning (ICML), 2019.
Dibya Ghosh and Marc G Bellemare. Representations for stable off-policy reinforcement learning. In International Conference on Machine Learning (ICML), 2020.
Caglar Gulcehre, Ziyu Wang, Alexander Novikov, Thomas Paine, Sergio Gómez, Konrad Zolna, Rishabh Agarwal, Josh S Merel, Daniel J Mankowitz, Cosmin Paduraru, et al. RI unplugged: A suite of benchmarks for offline reinforcement learning. Neural Information Processing Systems (NeurIPS), 2020.
11

---

Published as a conference paper at ICLR 2023
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-965 2020.
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Mare van Zee. Flax: A neural network library and ecosystem for JAX, 2023. URL.
http://github: com
www.goo...occoocoootooooo....o. gww. wwroogll//i. faax
Matthew W. Hoffman, Bobak Shahriari, John Aslanides, Gabriel Barth-Maron Nikola Momchev, Danila Sinopalnikov, Piotr Stańczyk, Sabela Ramos, Anton Raichuk, Damien Vincent, Léonard Hussenot, Robert Dadashi, Gabriel Dulac-Amold, Manu Orsini, Alexis Jacq, Johan Ferret, Nino Vieillard, Seyed Kamyar Seyed Ghasemipour, Sertan Girgin, Olivier Pietquin, Feryal Behbahani, Tamara Norman, Abbas Abdolmalcki, Albin Cassirer, Fan Yang, Kate Baumli, Sarah Henderson, Abe Friesen, Ruba Haroun, Alex Novikov, Sergio Gómez Colmenarejo, Serkan Cabi, Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Andrew Cowie, Ziyu Wang, Bilal Piot, and Nando de Freitas. Acme: A research framework for distributed reinforcement learning, arXiv preprint arXiv:2006.00999 2020.
D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science Engineering, 9()):
90-95, 2007.
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czamecki, Tom Schaul, Joel Z. Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. In International Conference on Learning Representations (ICLR), 2017.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blažej Osiński, Roy H Camphell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for atari. In International Conference Learning Representations (ICLR), 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.
Roger Koencker. Quantile Regression. Cambridge University Press, 2005.
George D. Konidaris, Sarah Osentoski, and Philip S. Thomas. Value function approximation in reinforcement learning using the fourier basis. In Proceedings of the 25th Conference on Artificial Intelligence, 2011.
Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Re- inforcement learning with augmented data. Neural Information Processing Systems (NeurIPS), 2020.
Charline Le Lan, Joshua Greaves, Jesse Farebrother, Mark Rowland, Fabian Pedregosa, Rishabh Agarwal, and Mare G Bellemare. A novel stochastic gradient descent algorithm for learning principal subspaces. arXiv preprint (/XXi:22/12.4025, 2022a.
Charline Le Lan, Stephen Tu, Adam Oberman, Rishabh Agarwal, and Mare Bellemare. On the generalization of representations in reinforcement learning. In International Conference Artificial Intelligence and Statistics (AISTATS), 2022b.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research (JMLR), 17(1), 2016.
Clare Lyle, Mark Rowland, Georg Ostrovski, and Will Dabney. On the effect of auxiliary tasks on representation dynamics. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Clare Lyle, Mark Rowland, and Will Dabney. Understanding and preventing capacity loss in reinforcement learning. In International Conference Learning Representations (ICLR), 2022.
12

---

Published as a conference paper at ICLR 2023
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. arXiv preprint arXiv:1710.11089 2017.
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference on Learning Representations (ICLR), 2018.
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learning representation and control in markov decision processes. Journal of Machine Learning Research (JMLR), 2007.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint
2021.
Ben O'Neill. The double-constant matrix, centering matrix and equicorrelation matrix: Theory and applications. arXiv preprint
2021.
Ronald Parr, Lihong Li, Gavin Taylor, Christopher Painter-Wakefice and Michael Littman. An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning. International Conference on Machine Learning (ICML), 2008
Marek Petrik. An analysis of Laplacian methods for value function approximation in MDPs. In Proceedings of the International Joint Conference on Artificial Intelligence, 2007.
David Pfau, Stig Petersen, Ashish Agarwal, David G. T. Barrett, and Kimberly L. Stachenfeld. Spectral inference networks: Unifying deep and spectral learning. In International Conference on Learning Representations (ICLR), 2019.
Bohdana Ratitch and Doina Precup. Sparse distributed memories for on-line value-based rein- forcement learning. In Proceedings of the 15th European Conference Machine Learning, 2004.
Gavin A. Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems. Techni- cal report, Cambridge University Engineering Department, 1994.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning (ICML), 2015.
Max Schwarzer, Ankesh Anand, Rishab Goel, R Devon Hjelm, Aaron Courville, and Philip Bach- man. Data-efficient reinforcement learning with self- predicceeietive representations. In International Conference Learning Representations (ICLR), 2021a.
Max Schwarzer, Nitarshan Rajkumar, Michael Noukhovitch, Ankesh Anand, Laurent Charlin, R De- von Hjelm, Philip Bachman, and Aaron C Courville. Pretraining representations for data-efficient reinforcement learning. In Neural Information Processing Systems (NeurIPS), 2021b.
Alec Solway, Carlos Diuk, Natalia Córdova, Debbie Yee, Andrew G Barto, Yael Niv, and Matthew M Botvinick. Optimal behavioral hierarchy. PLoS Computational Biology, 1003)7 aug 2014.
Kimberly L. Stachenfeld, Matthew Botvinick, and Samuel J. Gershman. Design principles of the hippocampal cognitive map. In Neural Information Processing Systems (NeurIPS), 2014.
Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling representation learning from reinforcement learning. In International Conference Machine Learning (ICMI.), 2021.
13

---

Published as a conference paper at ICLR 2023
Richard S. Sutton. Generalization in reinforcement learning:
Successful examples using sparse coarse coding. In Neural Information Processing Systems (NeurIPS), 1996.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S. Sutton and Steven D. Whitehead. Online learning with random representations. In International Conference on Machine Learning (ICML), 1993.
Richard S. Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M. Pilarski, Adam White, and Doina Precup. Horde: scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2011.
R.S. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112:181-211, 1999.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning (ICML), 2019.
Ahmed Touati. Large State Spaces and Self-supervision in Reinforcement Learning. PhD thesis, Université de Montréal, 2021.
Ahmed Touati and Yann Ollivier. Learning representation optimize all rewards. In Neural Information Processing Systems (NeurIPS), 2021.
Michael L. Waskom. seaborn: statistical data visualization. Journal of Open Source Software, 6(60):
3021, 2021.
Wes McKinney. Data Structures for Statistical Computing Python. In Proceedings of the 9th Python in Science Conference, pp. 56 61, 2010.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in RL: learning representations with efficient approximations. In International Conference on Learning Representations (ICLR), 2019.
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. International Conference on Learning Representations (ICLR), 2021.
Xuezhou Zhang, Yuda Song. Masatoshi Uchara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference Machine Learning, pp. 15517266447. PMLR, 2022.
14

---

Published as a conference paper at ICLR 2023
A BACKGROUND
A.I PROTO- FUNCTIONS
Proto-Value Functions Four-Room Grid
PVF
PVF
PVF 3
PVF4 4
Figure 6: First four proto-value functions (eigenvectors of y when the uniform random policy) on the Four Room grid world.
Proto- Value Functions (PVFs) are defined in terms of the graph Laplacian R=x" that
L A,
where D Rax= is the degree matrix and A RRxx is the adjacency matrix. The actual PVTs defined as the eigenvectors of the graph Laplacian, that is the non zero vectors v E R \ {()} verifying
= Ae.
where À E IR is the eigenvalue associated with the eigenvector c.
Individually, these eigenvectors correspond different time-scales of the diffusion process of random-walk over the state-space (Mahadevan & Maggioni] (007). Intuitively, PVFs can be thought shows an example of the first four PVFs on the Four-Room domain (Sutton et al., 1999; Solway el al. 2014) to give some intuition for their structure.
of capturing large-scale temporal properties of the environment. Figure (ggure
A.2 THE SUCCESSOR REPRESENTATION
Let pr _ be the transition matrix and nT the reward vector, both induced by the policy æ. We can now write the policy evaluation equation for the values v E IR" as:
where T the Successor Representation (SR). We can also write each element of the SR as the expected discounted future occupancy for state s' given you start in a state
(8, = Σ PPP(S = 8 =
1>0
= = b (S. = 5/} So
A.3 CONNECTION BETWEEN THE SR & PVFS
We can further connect the Successor Representation with Proto-Vale Functions under some as- sumptions.
Assumption 1.
The Successor Representation is defined with respect to the uniform random policy.
Assumption 2. The transition matrix ps is symmetric.
Under the above assumptions, have that the eigenvectors of T equivalent the PVFs (eigenvectors of L) (Machado et al. [0117] Sttachenfeld et al. 2014). This helps motivate the choice of the uniform random policy the target policy in the PVN TD update.
15

---

Published as a conference paper at ICLR 2023
B PROOFS FOR SECTION 4
Theorem 1. &f is a feature matrix minimizing LMCSM ( then its column space spans the top left singular vectors of the (infinite-dimen linfnittediimessinna)) successor measure matrix Tp" with respect the inner product (I, y)=
Ex, for all æ, E R=.
Proof. We consider the SVD of the successor measure to with respect to the weighted inner product E. In matrix form, we write
FEB
where Raxd E Radxd and RR satisfy
F 1F==1B''E 1, diag(o), oa)
and o are the singular values of V sorted in decreasing order.
arg min LMCSM( arg min min $ERuxd
[ Σ
(0(x) us.a [s, ax
#ERaxd Ws. S-E
*ENi,CA
arg min min [[ - -
arg
dERexd
W
arg min |1I 1 #ERoxd
where TT is the orthogonal projection onto span The above is equivalent saying that t must span the top d singular vectors of V
C TABULAR RESULTS
Define the Successor Representation (SR) as V = (1 7 gaxn and assume that p" is symmetric. Let GR E xx* (E) be the matrix containing all the binary vectors corresponding to all (?) subsets (i.e., its columns have all possible k-hot binary vectors). For example, given n = 4 we have,
1
07
1
0
0
0
G
0
1
0
0
0
1
0
1
In the tabular setting we seek to learn the successor measure with respect P3 by minimizing
C(2, W) = | - 1
We know that the optimal will span the principal components of VG (Bellemare al. 2019). Note that when & = 1 we have, VG = in which case the principal components are the PVTs Machado al. (2117) We want to characterize the principal subspace of & for n.
Claim: C. (v)))) (VG)) T has the same eigenvectors for all i fl,...,n 1).
Proof: We start by writing down the covariance matrix as
C (VGG) (WG&)
V.G.TTV TT
The matrix G.G.T double-constant matrix (O'Neill 2021). p. i.c., it has constant on the diagonal and a constant different from on the off-diagonal:
t
a
t
t
M₁ = 1.
b
t
t.
16

---

Published as a conference paper at ICLR 2023
In double-constant matrices, we have that the eigenvalues of M3 are Å = A A; = A = a for all i = 2...... n. The cigenvectors for Aee are Ves x 1 where is the vector of all ones. The eigenvectors for X are any non-zero vectors where v, 1 = 0, i... is orthogonal to the vector of all ones.
have (c-1) and (2-2) Furthermore,
another property of + n 1 and
Next, characterize the eigenspace of the matrix V We have,
= -
= -I- -11-9QAQ-1)
(Since p is symmetric, hence diagonalizable)
= =Q(1->A)---1
This means that the eigenvectors of 8 are the same the eigenvectors of p We will denote the eigenvalues pa be X; with associated eigenvectors Zi.- For simplicity, we denote the eigenvalues of T μ4 for i .,... Note that μ4, (1 7),) for i I....,
Furthermore, since p' a stochastic matrix, we have that 1 is an eigenvector with eigenvalue 1. We let T1 = 1 without loss of generality. Also, since p is assumed to be symmetric, the eigenvectors can be chosen to be orthogonal to each other.
Putting this all together. take rę to be the i-th eigenvector of T (and P*). We now have,
Cr: V Mg. T x2
V Mr Ver
(by symmetry) (r, an eigevector of v))
M.MM
Now there are two cases:
Case 1: If vr 1 (and i 1) we have,
Cs: a Mapaai
1
M17a./111
=
Case 2: If o; # (and i>>>> 1) know that z; is orthogonal to 1 (since pr is symmetric matrix) thus lies in the second eigenspace of Mg corresponding to the eigenvector v., Therefore, we have,
Cr, V Ma
V Di,4
Thus, have shown that C' MM T has the same eigenvectors V and are independent of k. The new eigenvalues are u² for the eigenvector and y² for all other eigenvectors 2; for i 2, n.
D IMPLEMENTATION DETAILS
We have released a reference implementation along with notebooks demonstrating how to download and use our pre-trained representaation at:
D.1 UNIVERSAL HASH FUNCTIONS
We define the set of multiply-shift universal hash functions
(Carter & Wegman
1979 as:
hz(x) = ag
+
aj 2z mod mod m,
==1
17

---

Published as a conference paper at ICLR 2023
where E R" is flattened vector of the environment's observation, a R" is randomly initialized vector that that parameterizes the hash function, p is a prime, which in our case is the Mersenne prime 2 - 1, and m allows function. We can now define the indicator function as follows:
control the activation proportion of the indicator
= - (()((())))))))))))))))())) =0.
D.2 QUANTILE REGRESSION
We quantile regression tune the proportion of states that trigger random network indicator functions. To do so, we use a tunable bias that we update with gradient descent. First, recall that the random network indicators apply the SIGN function to the network output, the proportion of states that map to is unlikely to match the target proportion p. Therefore, we first add bias term the output r' f() and then tune the bias to minimize the quantile regression loss
computed using random neural network f + R. If naively
Lou Ezexr'(r) (z) ((1 pp) (SSIG(((((x))
(2)
Once the bias has been tuned, the output of the random network indicator is = +
D.3 ALGORITHM
Algorithm gives pseudo-code for the method implemented with fixed replay memory.
Algorithm Proto-Value Networks
Require: Transition dataset D, Function approximator vh X m RNI networks fi : X - R, m RNI threshold bias vectors b, Polyak coefficient т, reward proportion p
1: for step I,... do
2: Sample mini-batch of n transitions {(1, a, x') C
4:
# Calculate random network indicators
5:
ry(x) fz)z) + bbj Vj I....,
6:
ry(x) + (IG)(r)(z))
7:
8:
Calculate PVN loss
LPvN(0)+ t To + E (15(0)) (((n))+ 7 EN'A 66 -66² (I ai)
9:
10:
11:
# Calculate quantile regression loss
12:
(bR + "E=r"(())) ((1-p) -el-pp) (z))()((x)))
13:
14:
Perform gradient step Update 0 1n 30
0
LPvx(0)
16:
Update b, + by 172 2b CbR(b;) Vj = 1....,m
17:
18:
# Polyak average target network parameters + T0 + (1-
19:
20:
end for
D.4 SELF-PREDICTIVE REPRESENTATIONS (SPR)
We implement an 8x version of SPR (Schwarzer et al. 2021a) using the same parameters as in, Schwarzer al. (202 except take the final fixed representation be the projection layer in addition to the convolutional encoder. This was done to maintain the number of features for all our pre-trained methods. We also train SPR for much longer than in the original paper, specifically, perform the same number of gradient steps as PVN.
18

---

Published as a conference paper at ICLR 2023
D.5 HYPERPAREMETERS
In the tables below we report all relevant hyperparameter choices for both our offline pre-training phase, and online learning phase.
We selected most of our hyperparameters based on best practices from previous work. We chose based on the estimated reward proportion from actual Atari games. We tuned our online hyperparam- eters using 5 tuning games, ASTERIX, BEAM RIDER, PONG, QBERT, and SPACE INVADERS.
Table 1: PVN Hyperparameters
Table 2: Online Hyperparameters
Hyperparameter
Value
Hyperparameter
Value
Number of auxiliary tasks
100
Update rule
DQN
Batch size
256
Number of layers
1 (linear)
Number of gradient steps
1,562,500
Number of agent steps
3.75M
Discount factor y
0.99
Frame skip
4
Target EMA coefficient
0.99
Total frames
15M
Reward proportion
0.01
Train
0.01
Quantile regression burn-in steps
62,500
Evaluation
0.001
Tasks per module
10
step
1
Optimizer
Adam
Discount factor Y
0.99
Adam Learning rate
le-4
Optimizer
Adam
Adam B1
0.9
Adam Learning rate
6.25e-5
Adam B2
0.999
Adam
1.5e-4
Adam
1.5e-4
Maximum gradient norm
10
Batch size
32
Minimum replay size
2,000
Maximum replay size
1,000,000
Gradient updates per agent step
19

---

Published as a conference paper at ICLR 2023
E
MDS PLOTS
Below selection of MDS plots for the methods discussed in the paper for each of the tuning games. These plots are generated using the representations learned during the pre-training phase, and expert trajectory is presented in each plot. Darker points correspond to states the beginning of the trajectory, and lighter points correspond to states at the end of the trajectory. These plots demonstrate that the representations learned by each method different properties. With these MDS explorations, we hope to gain some insight into the properties of each learnt representation. Motivated by PVFs, we expect good (general) representation to capture the structure of the underlying transition dynamics of the environment. We note that PVN captures the temporal structure of each episode relatively well. With PVN, states that near together in time have similar features, aligning with the properties of PVFs in the tabular case.
clearly different, and therefore have
PVN (Hash)
Environment Reward
Random Cumulants
Random Initislization
(a) Asterix
PVN (AN()
PVN (Hash)
Environment Reward
Randem Cumulants
Random Inftialization
BeamRider
PVN (RNI)
PVN (Hlsh)
Environment Reward
Random Cumulants
Random Initialization
(c) Pong
(Hash)
Environment Random Cumulants
Initialization
(d) Qbert
PVN (RNI)
PVN (Hash)
Environment Reward
Random Cumulants
Random Initialization
(e) SpaceInvaders
Figure 7: MDS plot for single trajectory.
20

---

Published as a conference paper at ICLR 2023
F PER-GAME RESULTS
Below, we report the per-game results for the methods discussed in the paper. In addition, we include DQN and the Environment Reward method, which trains an encoder using the environment reward during the pre-training phase, and then uses the fixed representation to train linear head in the same manner the compared methods. Note that Environment Reward acts kind of oracle in our setting it is the only method that has access to the environment reward during the pre-training phase. use offline seed and online seeds, and evaluation scores (averaged over
The results reported 100 evaluation runs) are reported after 3.75M agent steps. DQN's performance is reported after 50M agent steps.
Table 3: Per-Game Results on RLU Games
Method
Game
DQN
Environmnnt Rewand
Random Initialization
Behavior Cloning
SPR
Random Cumulants
PVN (RNT)
Amidar
7
43.8
50.2
46.8
43.8
63.6
Assullt
1.442.5
695.
193.2
452.9
293.0
494.5
1,100.7
Astorix
2,953.4
13,096.3 3
522.9
7.139.8
1.625.1
347.8
15,401.2
592,372.5
10,275.0
34,112.2
12,760.3
BankHeist
589.8
47.6
7.0
54.7
618.8
1,0364
456.
BatileZone
14,818.1 1
37,796. 3
1,547.4
12,545.5
2,360.1
6,492.2
13,228.7
BeamRider
4,569.7
10.660.3
411.8
3,862.2
1,111.5
5,447.1
8,646.0
Boxing
-2.8
Breakout
96.4
206.8
3.8
7.1
334.0
16.4
Camival
4,438.2
4,976.0
362.2
671.0
684.8
648.9
1,288.5
Centipede
2.358.9
1,176.9
3,534.5
1,688.6
4,300.3
1,0226
3.421.6
ChopperConmann
CazyClimber
100.15%
237.240.0
10,179.4
2.14.7
$1,999.3
133,411.2
19.259.1
DemonsAtack
4,427.9
101,850.7
123.1
14,426.7
421.8
2,407.8
78,6711
DoubleDunk
22.7
FishingDerby
-1.1
28.7
96.6
92.
-99.2
95.6
-72.5
Freeway
24.1
33.7
8.5
14.7
15.9
29,5
189
Prosibite
623.0
4,386
408.
Gopise
4,579.2
1,144.5
231.1
479.8
939.6
1,59,0
3,07000
Gravitar
214.4
1
42.7
310,0
72.8
77.6
164.3
Hero
12.348.1
9,9324
511.5
1,974,9
9,256,3
445.5
L,112.2
-7.3
Jamesbond
473.3
L,58.6
24.4
387.9
82.2
69.7
630.2
Kangaroo
8,653.0
9.6120
199.1
1818.0
78.7
L,033.1
L.2441
Krull
5,892.5
8,630.4
1,248.9
3.622.1
3,836.1
206.4
4,006.5
KungFuMaster
35.076.0
12.262.9
MaPaeman
2,880.5
5,797.
836.1
629.4
1,946.6
1,44
L.33399
ThisGamee
6,114.5
17.612.3
1,425
2,519.8
2,036.0
2.418.6
7218.7
Phoenix
4,761.3
34,50133
414.6
904.1
935.8
7,828.6
6,946.1
Pong
-20.8
Ponyan
3.114.5
L675.0
747.7
444.9
829.5
L,43.3
LA32.2
Qhert
8,309
14, 44,393.7
122.1
664.6
567.9
2,113
3
Riverraid
9,703.1
11,319.0
1,279.7
2,829.2
3,083.1
619.9
6,41.6
ReudRRnnner
36,386.9
37,417.8
2,543.2
939.2
3,932.6
6,975.3
Rohotank
39.2
75.
2.4
44.7
3.9
14.1
3,5
Seaquest
1,510.1
173.7
63.8
291.2
310.3
$1.6
1,40X
Spacelnsaders
18,799.0
TimePilot
2.613.8
11,205.9
2,409.2
1,860.5
1,842.7
1,08.7
2,418.6
UpNDown
8,289 8
17,629.3
1,174.4
2,307
541.2
11,018.7
9,193.7
VideoPinball
WicardOWWor
1,904.9
4,749.5
480.3
1,298.0
882.6
794.7
1,739,
YarsRevenge
20,520.1
47,218.7
3
10,056.0
10,047.2
768.4
21,253.5
Zasson
2,985.8
14,329.2
313.8
3,013.2
283.8
1.170.9
4,215,0
21

---

Published as a conference paper at ICLR 2023
G TRAINING CURVES
Figure presents training curves for all 46 games in RL. Unplugged. Each point corresponds to the average episodic return during training binned over 1M frames. The shaded region corresponds the 95% bootstrapped confidence interval for the mean over three runs. Note: These results will differ from Table 3 as we use separate evaluation phase with lower value of as standard in the ALE.
PVN (RNI)
SPR
Behavior Cloning
Random Cumulants
Average Episodic Return
1.00
1700
1.50
Iteration
Figure 8: Training curves for: PVN (RNI), SPR, and Random Cumulants on all 46 games in RL Unplugged. The shaded region corresponds to the 95% bootstrapped confidence interval for the mean over three runs. The dashed horizontal line corresponds to the average evaluation score for Behavioral Cloning over three runs.
22


Reviews:
[{"review_id": "vCtGOw7fYUj", "reviewer": "Reviewer_SdmH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the question of representation learning in deep RL by means of learning successor features for auxiliary tasks. It presents an approach to learn successor features with reward agnostic tasks which will learn features that can then be used to learn a linear action-value function for downstream tasks.\nThe features learned via this approach have connections to a previous approach for representation learning, proto-value functions.\n\nThese reward agnostic tasks are based on a set inclusion reward, where the paper proposes to generate sets using universal hash functions or random network indicators (RNIs) to ensure that the sets will cover the entire state space. The main technique used in the paper then utilizes this idea of learning successor features with sets generated using RNIs and tuned with quantile regression to learn a representation from offline Atari datasets. The representation is tested with some online interaction.", "summary_of_the_review": "The paper presents an analysis of a particular class of auxiliary tasks to learn successor features which can be connected to the proto-value functions and thus encode the spatial structure of the MDP. They present practical methods to generate these auxiliary tasks and show effectively that features learned via this method are useful for the downstream task.\nThe idea is straightforward, the proposed technique is interesting, and the results bear out the approach.", "strength_and_weaknesses": "### Strengths:\n* This paper presents a method to approximate proto-value functions using the idea of auxiliary tasks.\n* It presents an interesting workaround to the state equality problem by instead formulating it as a set inclusion reward\n\n### Shortcomings:\n* The paper states that the set inclusion reward is a relaxation of the state equality, and this relaxation allows the learning of features that relate to the proto-value functions. A toy experiment on a grid world to show how the set inclusion reward compares to the state equality reward would have been illuminating.\n* Some questions are raised (See below) that are not entirely answered by the paper.\n\n### Questions:\n* Is there an assumption that the dataset used to learn these representations have coverage? Since the learned representations be dependent on the transition structure of the environment, if the MDP has bottleneck states that a random policy that starts from a restricted set of start states might find hard to get through, will the learned representations be suboptimal?\n* How does the scaling of the Impala network's penultimate layer affect the number of parameters in the network? If the scaling does not change the number of parameters substantially, it might be a possible explanation of the saturation of the number of tasks that can be learned.\n* Can these features be used for purely offline RL? Or would that introduce some bias which required online learning to learn the task specific policy?\n* In the ablations, PVN is compared to a version that learns the successor features for the optimal policy for the auxiliary tasks. The reduced performance of this approach is attributed to the max operator needed for the Q-learning update. This conclusion seems preliminary. Is the reason that the greedy policy fails because of the max? Or because the representations no longer capture the environment dynamics alone (and also represent the policy)? What if the policy being evaluated here was the Boltzmann softmax policy with respect to the task, where the expected sarsa-type update for the successor features could still be performed, but the policy is not random?\n\n### Minor issues and typos:\n* In Section 3, it is unclear which policy the successor representation is being learned for. If it is implicitly the random policy, clarify.\n* In Section 3, for the indicator function formulation, is previous work that lays out this formulation different from the Dayan paper? If so, cite it.\n* Section 4.1 starts off by discussing $\\psi^\\pi$ but then proceeds to discuss $\\psi$. It is unclear why $\\psi$ has become policy agnostic.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ir4bLb7lN1", "reviewer": "Reviewer_PVaX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces an extension of learning successor feature that ensures that the learned feature could obey the bellman consistency on a set of the states. To empirically define which sets of states that the feature should operates on, the paper introduces two empirical surrogates: using random hash functions or random neural networks. Finally the experiments visualize that the learn feature may indeed show some meaningful semantics over the states.", "summary_of_the_review": "Overall this is a well-written paper and the paper provides some good insights, some specific aspect of the paper is interesting, but I am not convinced that the paper actually makes enough contribution and seems to overlook some previous methods. I would recommend a borderline reject. \n\n### Post-rebuttal\nThe authors make the paper more ready for publishing after the rebuttal thus I raised my score. See the discussion thread for more details.", "strength_and_weaknesses": "# Strength\n- The paper proposes an easy extension of successor features, and the two proposes state aggregation methods seem to provide meaningful results in practice. Also the state aggregation methods are interesting.\n- The paper is well-organized and easy to follow.\n\n# Weakness\n- One would naturally wonder why when we want to learn the value function $Q$, we should only learn a feature mapping $\\phi$ that only operates on states only (specifically, section 3). One example one could think of is where we have finitely many actions, then $\\phi(s)$ could be the $Q$ function for each action and $w_a$ is a one-hot encoder. But intuitively this formulation seems have its limitation on the generalizability against, for example, learning the state-action representation.\n\n- The paper does a good job showing that the learned representation are interpretable to human, but there seems to lack of a section that shows that learning representation this way is indeed useful. The paper should consider adding some baselines and try to at least show the performance is comparable, because the method also enjoys the advantage of having the offline data which may provide good coverage.\n\n- Introducing another function to learn a representation that obeys the bellman consistency on that function is actually not new even in representation in RL. For example, in MOFFLE [1] and BRIEE [2], the representation learning objective is to train a feature map that ensures the bellman consistency on the sequence of the most adversarial discriminator function. The idea of using many random network is the same: it ensures that it could cover the whole discriminator class and learn a feature map that works on all of them.\n\n- The usage of random policy still sounds heuristic to me. If you want to do distribution shift to arbitrary policy, you may still need to pay for exponential on $|\\mathcal{A}|$.\n\n- There are several confusions in the paper:\n1. Right above section 4.1: \" These eigenvectors are of special importance because they encode the spatial structure of the MDP in terms of a diffusion process\". I am very confused about what this claim, and it would be great if further explanation could be provided and show why this claim is relevant.\n\n2. Second to last paragraph in page 4: \" Second, set inclusion allows us to incorporate a notion of closeness to $\\psi$, ...\" Here the notion of closeness seems ambiguous, especially in the context of set notations. \n\n3. On the top of page 5: $\\xi$ here is a distribution, then the definition of the diagonal matrix seems weird. Is $\\xi$ just a $n$-dimensional simplex?\n\n[1] Modi, Aditya, et al. \"Model-free representation learning and exploration in low-rank mdps.\" arXiv preprint arXiv:2102.07035 (2021).\n\n[2] Zhang, Xuezhou, et al. \"Efficient reinforcement learning in block mdps: A model-free representation learning approach.\" International Conference on Machine Learning. PMLR, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "P2CHHwomvZ", "reviewer": "Reviewer_tzdq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the power of representation learning via auxiliary tasks in deep reinforcement learning. To be concrete, it focuses on find a good representation of the states that is capable of predicting the optimal value functions if followed by a linear predictor. Correspondingly, it proposes a method called the proto-value networks. The proto-value networks take advantage of the success measure over subsets of states to learn a good representation. Empirical studies show that these learned features combined with linear functions capture the optimal value functions in many Atari games. The evaluation rewards are comparable to that of the original version of DQN.", "summary_of_the_review": "Overall, I think this is a good paper, which is suitable for the conference.", "strength_and_weaknesses": "The paper has multi-level contributions: \n\n1. The problem studied is interesting and important in the field of deep RL. Most of the works in RL are based on the representation learning, so it is vital to understand the properties of these representations. \n2. To design such a representation, this work proposes to use the success measure as the learning objective of state representations. Further, they find that it is more effective to learn the success measure over subsets of states, instead of using the original success measure defined on a single state. Finally, they study how to choose such subsets of states as auxiliary tasks. They propose universal hashing functions and random network indicators to effectively help design the state representations.\n3. With the learned representations, they conduct systematic experiments on all the Atari games to verify the effectiveness of the representations. The results show that linear functions with regards to the representations are sufficient to learn optimal policies on many tasks, with comparable performance to the DQN algorithm. The experimental results also verify the scaling properties of the number of auxiliary tasks, and the importance of the indicator functions.\n\nOn the other hand, I also have several questions regarding to the paper:\n\n1. Could you provide some intuitions on why choosing the uniform random policy as the target policy in the pre-training stage? The performance degradation of the greedy policy (using the max operator instead of averaging) perhaps comes from the correlation of the target policy and current feature estimator. However, is there a more efficient target policy that incorporates the prior knowledge of the tasks?\n2. It seems that the learned features of the states at the end of the pre-training stage is the output of the last but one layer of the PVN, since the last layer is a linear prediction layer. How large is the dimension of such features? Is it possible to improve the performance with larger feature dimensions?\n3. The empirical results do not provide the comparison with the widely used policy gradient methods such as PPO. Is it possible for PVN to achieve comparable performance to these policy gradient algorithms?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1BBhzGZCRA", "reviewer": "Reviewer_ZQM9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies representations obtained due to using auxiliary tasks and larger networks. The main claim is that tasks derived from randomly initialized networks are sufficient to train strong representations.\n", "summary_of_the_review": "The paper studies relevant research questions: how the quality of representations depends on the number of auxiliary tasks and the size of the network. It suggests that it is beneficial to substantially increase the model size (e.g. 8x), while the number of auxiliary tasks needed is around $\\approx 10$ (depending on the model size).\n\nImportantly, the auxiliary tasks used in the paper are defined by a randomly initialised neural network, meaning that they are very cheap to obtain. The main finding is that these are enough to induce useful representations even when using random trajectories. \n\nMy main concern is about the evaluation protocol. The authors measure the quality of the representations by the performance of $3.75$M samples training. This seems quite arbitrary for at least two reasons. The first one, very down-to-earth, is why $3.75$M. Are the conclusions stable for other number of samples? Secondly, more philosophically, why to measure the quality of representation by online RL training? Clearly, I can see the practical motivation; however, I can also see some problems due to the fact that RL setup is complex. I can imagine, for example, that representations are good for performance but poor for exploration or vice versa. I do not know a canonical answer to these problems, and I am ready to be convinced in the discussion period.\n\nI would also appreciate some discussion about the games, for which random trajectories do not explore well the state space. \n\nQuestions:\n- Could you provide results for other number of samples?\n- Does it make sense to measure the quality of representation using some other metric. Simple and perhaps too crude would be if (how fast) the reward can be learned using the representation.\n- What would be the benefits for $16x$, i.e. when the improvements are saturated.", "strength_and_weaknesses": "The major strength of the work is the fact that it addresses an important problem of augmenting the RL training with unsupervised data. Moreover, the execution and clarity of the paper are very good.\n\nThe weakness, in my opinion, is that the presented evaluation protocol is unsatisfactory. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster