Our first observation is that eigendecomposition and SVD are equivalent for
symmetric matrices because any real symmetric matrix has an orthogonal
eigenbasis; this means that performing either decomposition yields the same
eigenvectors and easily related eigenvalues. Our second observation is that
when $P^{\pi}$ is not symmetric, its singular value decomposition and
eigendecomposition may diverge; further, the relationship between the SVD of
the resolvent matrix $\Psi=(I-\gamma P^{\pi})^{-1}$ and of $P^{\pi}$ is no
longer straightforward, despite the eigenspaces of the two matrices being
analogous. This means that analysis of the singular value decomposition of
$P^{\pi}$ does not immediately imply any results about the resolvent matrix.

Matrix | SVD | Eigendecomposition (ED)
---|---|---
$L_{G}$ | PVFs (Mahadevan and Maggioni, 2007) | Equivalent to SVD
$T$ | sometimes $\equiv$ ED($L_{G}$) (Machado et al., 2017) | not discussed
$L_{P^{\pi}}$ |  $\neq$ ED($L_{P^{\pi}}$) | Stachenfeld et al. (2014)
$(I-\gamma P^{\pi})^{-1}$ | RSBFs | $\equiv L_{P^{\pi}}$
$P^{\pi}$ | Behzadian and Petrik (2018) | $\equiv L_{P^{\pi}}$
Table 12.1: Summary of decompositions of various matrices associated with MDP
transition operators, and associated features.

Finally, we note that applying a uniform random walk policy may not be
sufficient to guarantee that $P^{\pi}$ will be symmetric, and that in general
it will not be possible to obtain a policy which will symmetrize the
transition matrix. For example: when $G$ is a connected, non-regular graph (as
is the case in many environments such as chains), there must be a node $v$ of
degree $d$ adjacent to a node $v^{\prime}$ of degree $d^{\prime}\neq d$. A
random walk policy will assign $p(v,v^{\prime})=\frac{1}{d}$, while
$p(v^{\prime},v)$ will receive probability $\frac{1}{d^{\prime}}$; thus,
$P^{\pi}$ will not be symmetric. Fortunately, this is not a barrier to
spectral analysis; the eigenvectors and eigenvalues of $P^{\pi}$ will still be
real, as their transition matrix will be similar to a symmetric matrix. We
defer to Machado et al. (2017) for a more detailed discussion of this
relationship.

###  12.8 Learning dynamics for ensemble prediction

We provide some visualizations of the induced behaviour on features as a
result of training an ensemble with multiple heads and zero reward,
replicating the analysis of Section 5.2.1, to highlight how the
eigendecomposition of $P^{\pi}$ affects the learned representations. We run
our evaluations on the Four-Rooms Gridworld by initializing
$\Phi\in\mathbb{R}^{105\times 10}$ (i.e. $|\mathcal{X}|=105$ and the number of
features $d=10$) and simulating the ODE defined in Equation 5.10 for time
$t=100$ with transition matrix $P^{\pi}$ defined by the uniform random policy
on this Gridworld. In some cases, the features converged to zero quickly and
so we show a final $t<100$ to highlight the behaviour of the representation
before it reaches zero.

We consider three variables which we permit to vary: the initialization scheme
of features, in one case sampled from an isotropic Gaussian rand or from a
randomly initialized 2-layer MLP nn); whether the weight matrix is fixed at
initialization fix or permitted to follow the flow defined by Equation 5.7
train; and finally the number of ‘heads’, M=1, 20, and 200.

In Figure 12.1, we plot the output of an arbitrary head $\mathbf{w}^{m}$ of
the ensemble. In Figure 12.2 we visualize the value of a single feature (i.e.
a single column of $\Phi$).

We observe, as predicted, that for fixed heads in the overparameterized
regime, the features (and the value functions they induce) converge to smooth
eigenfunctions. We do not see meaningful convergence of the features trained
in conjunction with a single weight vector. In contrast, the value functions
and features trained in conjunction with ensembles with more heads than the
feature dimension consistently resemble the eigenfunctions of $P^{\pi}$. When
$(\mathbf{w}^{m})$ are held fixed, we see convergence to smooth eigenfunctions
as predicted by our theory; when $(\mathbf{w}^{m})$ are permitted to vary
according to the flow in Equation 5.11, we see convergence to the most
eigenfunction corresponding to the most negative eigenfunction of $P^{\pi}$.

Figure 12.1: Value functions learned by the ensemble head at index 0 for
different training regimes. Plot titles of form (feature initialization
scheme, train/fix weight matrix, number of heads in ensemble). Observe that
the representation learned with fixed weights tends to converge to smoother
eigenfunctions than those learned with weights that are also allowed to train.
f Figure 12.2: Values of ensemble feature at index 0 for different training
regimes. Plot titles of form (feature initialization scheme, train/fix weight
matrix, number of heads in ensemble). Observe that the representation learned
with fixed weights tends to converge to smoother eigenfunctions than those
learned with weights that are also allowed to train.

###  12.9 Experimental details

####  12.9.1 Experimental details for Figure 5.3

In our evaluations of the evolution of single feature vectors, we compute the
continuous-time feature evolution defined in Equation (5.6), using $P^{\pi}$
defined by a random walk on a simple Four-Rooms Gridworld with no reward. We
use a randomly initialized representation
$\Phi\in\mathbb{R}^{|\mathcal{X}|\times 10}$, and use a single column of this
matrix in our feature visualization (we observed similar behaviour in each
feature). To compute trajectories, we use the SciPy ODE solver solve_ivp
(Virtanen et al., 2020).

####  12.9.2 Experimental details for Section 5.5.1

Here, we provide details of the environment used in producing Figure 5.5.1.
The environment is a 30-state chain, with two actions, left and right, which
move the agent one state to the left or right, respectively. When the agent
cannot move further left or right (due to being at an end state of the chain),
the result of the corresponding action keeps the agent in the same state.
There is additionally environment stochasticity of $0.01$, meaning that with
this probability, a uniformly random action is executed instead. This
stochasticity ensures that $P^{\pi}$ satisfies the conditions of Assumption 1.
Taking the action left in the left-most state incurs a reward of $+2$, and
taking the action right in the right-most state incurs a reward of $+1$; all
other rewards are zero.

####  12.9.3 Experimental details for Section 5.5.2

We modify a base Double DQN agent (Van Hasselt et al., 2016) and evaluate on
the ALE without sticky actions (Bellemare et al., 2013). Our agents are
implemented in Jax (Bradbury et al., 2018), and are based on the DQN Zoo (Quan
and Ostrovski, 2020). Unless otherwise mentioned, all hyperparameters are as
for the default Double DQN agent, with the exception of the epsilon parameter
in the evaluation policy, which is set to 0.001 in all agents, and the
optimizer, which for agents using auxiliary tasks CV, REM and Ensemble is Adam
with epsilon $0.1/32^{2}$, and a lightly tuned learning rate; see below for
further details.

Experimental results shown in bar plots, such as Figures 5.6 and 12.4, report
a “relative score” which is the per-game score normalized by the maximum
average score achieved by any agent or configuration. The same, per-game,
normalization values are used for all such figures.

Auxiliary task details. In this section, we describe the implementations of
all auxiliary tasks considered in the main text.

  * •

_QR-DQN._ The implementation and hyperparameters match QR-DQN-1 in Dabney et
al. (2018).

  * •

_DDQN+RC._ We use a many-head DQN network which is identical to the standard
neural network used for DQN, except that the output dimension is
$(M+1)\times|\mathcal{A}|$ instead of $|\mathcal{A}|$, where $M$ is the number
of auxiliary heads. Random cumulants are generated using a separate neural
network with the same architecture as a standard DQN, but with output
dimension equal to the number of auxiliary heads. The width of the Huber loss
for each auxiliary head is equal to the number of auxiliary tasks. Let
$\phi(x)\in\mathbb{R}^{M}$ be the output of the cumulant network given input
observation $x$, with $M$ the number of auxiliary heads. Then the cumulant for
auxiliary head $m$, at time step $t$, is given by
$c_{t}=s\times(\phi(x_{t+1})-\phi(x_{t}))$, where $s\in\mathbb{R}$ is a
scaling factor. We performed a small hyperparameter sweep over scaling factors
in $\\{1,10,100,500\\}$, finding $s=100$ to provide the best performance and
use this value for all reported experiments. Note that this auxiliary task and
the details are nearly identical to the _CumulantValues_ auxiliary task of
Dabney et al. (2021), except that we do not pass the values through a tanh
non-linearity as this did not appear to have any impact in practice. We
performed a hyperparameter sweep over learning rates and gradient norm
clipping for this agent, considering learning rates
$\\{0.00025,0.0001,0.00005\\}$ and gradient clipping in $\\{10,40\\}$. We
found that a learning rate of $0.00005$ and gradient norm clipping of $40$ to
work best and use these values for all experiments.

  * •

_DDQN+REM._ We use a many-head variant of Double DQN, with heads trained
according to the REM loss of Agarwal et al. (2020). For the agent’s policy, an
argmax over a uniform average of the heads is used. We swept over learning
rates of $0.0001$ and $0.00005$, generally finding $0.00005$ to perform best.

  * •

_DDQN+Ensemble._ As for the REM auxiliary task, we use a many-head variant of
Double DQN. Each head is trained using its own double DQN loss, and the
resulting losses are averaged. For the agent’s policy, an argmax over a
uniform average of the heads is used. We swept over learning rates of $0.0001$
and $0.00005$, generally finding $0.00005$ to perform best.

Modified dense-reward games. We modified four Atari games (Pong, MsPacman,
Seaquest, and Q*bert) to obtain sparse, harder versions of these games to test
the performance of random cumulants and other auxiliary tasks. The details of
these games are given below. In each case a low-valued, commonly encountered
reward is ‘censored’, which means that during training the agent observes a
reward of $0$ instead of the targeted reward. When evaluated, and thus for all
empirical results reported, the standard uncensored rewards are reported.

  * •

_Sparse Pong._ All negative rewards are censored (i.e. set to 0 before being
fed to the agent), so the agent receives a reward of +1 for scoring against
the opponent, but no reward when it concedes a point to the opponent. As $0$,
$1$, and $-1$ are the only rewards in Pong, this modification makes Pong
significantly harder. The agent can no longer learn to ‘avoid losing points‘,
but can only improve by learning to score points directly.

  * •

_Sparse MsPacman._ All rewards less than or equal to 10 are censored. This
corresponds to rewards for the numerous small pellets that MsPacman eats, but
not the larger pellets or ghosts. Each level ends when all of the small
pellets are consumed, thus, by hiding these from the agent we may have
significantly changed the primary incentive for the agent to advance the game.

  * •

_Sparse Seaquest._ All rewards less than or equal to 20 are censored. This
corresponds to the rewards for shooting the sharks underwater, but not the
rewards for picking up divers or surfacing. Additionally, even the rewards for
sharks increase beyond this level, and thus become visible, once the agent has
surfaced and collected enough divers.

  * •

_Sparse Q*bert._ All rewards less than or equal to 25 are censored. These are
the rewards for flipping the colour of a tile, which is the primary source of
reward and the mechanism for advancing to the next level of the game. Once all
tiles are flipped, the agent will go to the next level. However, the agent can
still observe rewards for going to the next level and for dispatching the
enemies.

As described in the main text, we found that the sparse versions of MsPacman,
Seaquest, and Q*bert were too difficult for any agent we tested to achieve a
reasonable level of performance. In Figure 12.3, we display the performance of
several auxiliary tasks on these games, noting that the performance achieved
is extremely low in comparison to the agents trained on the standard versions
of these games (see Section 5.5.2).

Figure 12.3: Learning curves on sparsified MsPacman (left), sparsified
Seaquest (centre), and sparisifed Q*bert (right).

Hyperparameter sweeps. In Figure 12.4 we vary the weight of the auxiliary loss
for the random cumulants agents, with the aim of understanding how this
hyperparameters affect each method’s performance. Next, in Figures 12.5 and
12.6 we present the results of a hyperparameter sweep for Ensemble and REM
respectively. For these two, since there is no separate auxiliary loss as in
RC, we vary number of heads and the learning rate. Results presented in the
main text use the best settings for each algorithm found from these sweeps.

Figure 12.4: Results of hyper-parameter sweep for Random Cumulant (RC) method,
where each row is for a different value of multiplicative scale applied to the
auxiliary losses and each bar corresponds to the number of auxiliary heads
($M$). Note that the first row of results corresponds to initializing a
network with the auxiliary heads, but setting the weight to zero, effectively
disabling the auxiliary task. Figure 12.5: Results of hyper-parameter sweep
for the Ensemble method, where each row is for a different learning rate and
each bar corresponds to the number of auxiliary heads ($M$). Figure 12.6:
Results of hyper-parameter sweep for the REM method, where each row is for a
different learning rate and each bar corresponds to the number of auxiliary
heads ($M$).

##  Chapter 13 Capacity loss

###  13.1 Proofs

####  13.1.1 Estimator consistency

We here show that our estimator of the agent’s feature rank is consistent.
First recall

$\displaystyle\left(\frac{1}{\sqrt{n}}\Phi_{n}\right)^{\top}\left(\frac{1}{\sqrt{n}}\Phi_{n}\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\phi(x_{i})\phi(x_{i})^{\top}\,.$
(13.1) The following property of the expected value holds
$\displaystyle\mathbb{E}_{x\sim P}[\phi(x)\phi(x)^{\top}]$
$\displaystyle=\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\phi(x_{i})\phi(x_{i})^{\top}\right]\,.$
(13.2) It is then straightforward to apply the strong law of large numbers. To
be explicit, we consider an element of $M=\mathbb{E}[\phi\phi^{\top}]$,
$M_{ij}$. $\displaystyle\mathbb{E}[(\phi(x)\phi(x)^{\top})_{ij}]$
$\displaystyle=M_{ij}=\mathbb{E}[\phi_{i}(x)\phi_{j}(x)]\implies\sum_{k=1}^{n}\frac{1}{n}\phi_{i}(x_{k})\phi_{j}(x_{k})\overset{a.s.}{\rightarrow}M_{ij}\,.$
(13.3)

Since we have convergence for any $M_{ij}$, we get convergence of the
resulting matrix to $M$. Because the singular values of $\Phi$ are the
eigenvalues of $M$ and the eigenvalues are continuous functions of that
matrix, the eigenvalues of $M_{n}$ converge to those of $M$ almost surely.
Then for almost all values of $\epsilon$, the threshold estimator
$N(\lambda_{1},\dots,\lambda_{k};\epsilon)=|\\{\lambda_{i}>\epsilon\\}|$ will
converge to $N(\text{spec}(M);\epsilon)$. Specifically, the estimator will be
convergent for all values of $\epsilon$ which are not eigenvalues of $M$
itself.

####  13.1.2 Feature collapse case study: quantile regression

We apply similar analysis to that of Chapter 5 to better understand the effect
of sparse-reward environments on representation collapse. To do so, we return
to the setting where $\Phi_{t}$ are non-parametric features and $w_{t}$ a
linear function approximator which jointly parameterize a value function
$V_{t}=\langle\Phi_{t}(x),w_{t}\rangle$. We recall the dynamics

$\partial_{t}\Phi_{t}=\alpha(\gamma
P^{\pi}-I)\Phi_{t}(w_{t}w_{t}^{\top})+R^{\pi}w_{t}^{\top}$ (13.4)

and

$\partial_{t}w_{t}=\beta\Phi_{t}^{\top}[(\gamma
P^{\pi}-I)\Phi_{t}w_{t}+R^{\pi}]\,,$ (13.5)

where $P^{\pi}\in\mathbb{R}^{\mathcal{X}\times\mathcal{X}}$ is the matrix of
state-transition probabilities under $\pi$, and
$R^{\pi}\in\mathbb{R}^{\mathcal{X}}$ is the vector of expected rewards.

In value-based deep RL, we model a Q-function which takes as input an
observation $\mathbf{x}$ and outputs a vector
$Q(s,a_{i})_{i=1}^{n_{a}}\in\mathbb{R}^{n_{a}}$. This resembles the setting of
ensemble prediction, whose dynamics we also recall here.

$\displaystyle\partial_{t}\Phi^{M}_{t}\\!=$
$\displaystyle\alpha\\!\sum_{m=1}^{M}(R^{\pi}\\!+\\!\gamma
P^{\pi}\Phi^{M}_{t}w_{t}^{m}\\!-\\!\Phi^{M}_{t}w_{t}^{m})(w_{t}^{m})^{\top}\,,$
(13.6) $\displaystyle\partial_{t}w_{t}^{m}=$
$\displaystyle\beta(\Phi^{M}_{t})^{\top}(R^{\pi}+\gamma
P^{\pi}\Phi^{M}_{t}w^{m}_{t}-\Phi_{t}w^{m}_{t})\,.$ (13.7)

The ensemble learning regime also bears similarity to the quantile regression
DQN (QR-DQN) objective (Dabney et al., 2018), which learns to fit a set of
quantiles to the distribution taken by the return when treated as a random
variable. Each quantile $\tau_{i}\in(0,1)$ is trained using a quantile
regression loss, of the form

$\mathcal{L}^{\tau}_{\mathrm{QR}}(\theta):=\mathbb{E}_{\hat{Z}\sim
Z}[\rho_{\tau}(\hat{Z}-\theta)]\quad\text{ where
}\rho_{\tau}(u)=u(\tau-\delta_{u<0}),\;\forall u\in\mathbb{R}.$

This loss is known to yield unbiased gradients, however it has the undesirable
property that the gradients of $\mathcal{L}^{\tau}_{\mathrm{QR}}$ remain
constant even as $\theta\rightarrow\tau$, which can result in pathological
convergence properties. The QR-DQN objective addresses this by implementing a
Huber loss (Huber, 1964), whose gradients tend to zero at its minimum.

$\mathcal{L}_{\kappa}(u)=\begin{cases}\frac{1}{2}u^{2}&\text{if
}|u|\leq\kappa\\\ \kappa(|u|-\frac{1}{2}\kappa)&\text{otherwise}.\end{cases}$
(13.8)

For a sufficiently large number of quantiles and under similar conditions as
in Theorem 5.4.1 the dynamics induced by this objective bear marked
resemblance to those of the ensemble prediction setting. In particular, when
no reward is observed in the environment, we again obtain that the features
will converge to the zero vector. The setting of this result is distinct from
that of deep neural network representation dynamics, as neural networks use
discrete optimization steps, finite learning rates, and typically do not
leverage linear ensembles. However, we emphasize two crucial observations that
suggest the intuition developed in this setting may be relevant: first, in
sparse reward environments the representation will be pushed to zero along
dimensions spanned by the linear weights used to compute outputs. Once
sufficiently many independent weight vectors are being used to make
predictions, this effectively forces every dimension of the representation to
fit the zero vector output. We would therefore expect representation collapse
to be particularly pronounced in the QR-DQN agents trained on sparse-reward
environments, as in this setting we obtain many independently initialized
heads all identically trying to fit the zero target.

######  Theorem 13.1.1.

Let let $\bm{\tau}=(\tau_{i})_{i=1}^{M}$ be a set of quantile functions
$\tau_{i}:\mathcal{X}\rightarrow\mathbb{R}$ with corresponding estimators
$(\hat{\tau}^{i})_{i=1}^{M}$ of the form
$\hat{\bm{\tau}}=\hat{\tau}^{i}(\mathbf{x})=\langle\phi(\mathbf{x}),\mathbf{w}^{i}\rangle$
for $\mathbf{w}^{i}\in\mathbb{R}^{d}$,
$\phi:\mathcal{X}\rightarrow\mathbb{R}^{d}$. Let $\pi$ be some policy in an
MDP $\mathcal{M}$, with $R^{\pi}=\mathbf{0}$, and $P^{\pi}$ be the
corresponding transition function. Let $\Phi^{M}_{t}$, $\mathbf{w}^{i}_{t}$
follow the dynamics

$\displaystyle\partial_{t}\Phi_{t}$
$\displaystyle=\beta^{M}\nabla_{\Phi}\mathcal{L}_{\kappa}(\hat{\bm{\tau}})$
(13.9) $\displaystyle\partial_{t}\mathbf{w}_{t}$
$\displaystyle=\alpha^{M}\nabla_{\mathbf{w}}\mathcal{L}_{\kappa}(\hat{\bm{\tau}})\;.$
(13.10)

Then if $\alpha^{M}=0$ or $\alpha^{M}=O(\frac{1}{M})$, letting
$\Phi_{\infty}=\lim_{t\rightarrow\infty}\Phi_{t}$, we obtain

$\lim_{M\rightarrow\infty}\Phi_{\infty}\rightarrow\bm{0}.$ (13.11)

######  Proof 13.1.2.

We break the derivation of this result into two cases. We first observe that,
when $\alpha=0$ and $\beta=1$, the QR-DQN update reduces $\|V_{t}\|_{\infty}$
by either $\kappa$ if $\|(\gamma P^{\pi}-I)V_{t}\|_{\infty}>\kappa$ or
$\gamma\|V_{t}\|_{\infty}$ if $\|(\gamma P^{\pi}-I)V_{t}\|_{\infty}<\kappa$.
In the latter case, the QR-DQN objective is identical to the TD updates
studied in Chapter 5, and we obtain convergence of $\Phi$ to zero in the case
of infinitely many heads, and in the case of $M=d$ heads with orthogonal
initialization aligned with the features.

In the case where $M\rightarrow\infty$, when $w^{i}$ are initialized to scale
with $\frac{1}{\sqrt{M}}$, we obtain straightforwardly that
$\|\Phi_{0}w^{i}\|\overset{P}{\rightarrow}0$. Thus, the limiting probability
that any error falls outside the $\kappa$ cutoff of the Huber loss will be
zero, and the dynamics on $\Phi$ will be identical to the TD dynamics studied
previously, allowing us to apply the result of Theorem 5.4.1.

In the case where $M=d$ and the $w^{i}$ are initialized such that
$\langle\phi^{i},w^{j}\rangle=\delta_{i,j}\phi^{i}$, we need only show that
the dynamics followed by quantile regression are sufficiently well-behaved to
push $\|V_{t}\|_{\infty}<\kappa$ for some finite $t$.

We note that in this case we can express the dynamics as follows, and for the
rest of this discussion assume without loss of generality that
$\phi^{i}_{t}(x)>0\forall x\in\mathcal{X}$.

$\displaystyle\partial_{t}\Phi_{t}$
$\displaystyle=-\sum_{i=1}^{M}\min((I-\gamma
P^{\pi})\Phi_{t}w^{i},\kappa)(w^{i})^{\top}$ (13.12)
$\displaystyle=-\sum_{i=1}^{M}\min((I-\gamma
P^{\pi})\phi^{i}_{t}w^{i},\kappa)(w^{i})^{\top}$ (13.13)
$\displaystyle\implies\partial_{t}\phi^{k}_{t}$
$\displaystyle=--\min((I-\gamma
P^{\pi})\phi^{k}_{t}w^{k},\kappa)(w^{k})^{\top}$ (13.14)
$\displaystyle=-\min((I-\gamma P^{\pi})\phi^{k}_{t},\kappa)$ (13.15)

Let $\phi^{i}_{t}$ be a feature vector at some time $t$. Let $x_{\max}$
maximize $\\{|\phi^{i}_{t}(x)|:x\in\mathcal{X}\\}$. Then we know that the
time-derivative on $\partial_{t}\phi^{i}_{t}(x_{\max})$ must have the opposite
sign to $\phi^{i}_{t}(x_{\max})$, as it takes the following form.

$\displaystyle\partial_{t}\phi^{i}_{t}(x_{\max})$
$\displaystyle=-\min((I-\gamma P^{\pi})\phi^{i}_{t}(x_{\max}),\kappa)$ (13.16)
$\displaystyle\mathrm{sign}(\partial_{t}\phi^{i}_{t}(x_{\max})$
$\displaystyle=-\mathrm{sign}(\phi^{i}_{t}(x_{\max})$ (13.17)

Now, because this applies to the maximal value of $\phi^{i}_{t}$ over all
states, we get that the function
$\tilde{\phi}^{i}(t)=\max_{x\in\mathcal{X}}\phi^{i}_{t}(x)$ is decreasing. The
rate of this decrease is either constant, in which case it is equal to
$\kappa$, or we get the standard exponential convergence described in 7.4.

Key insight.
In the presence of many prediction targets, such as those induced by a
quantile regression objective, sparse-reward environments will induce low
dimensional feature representations in deep RL agents.

###  13.2 Sequential supervised learning

####  13.2.1 Details: target-fitting capacity on non-stationary MNIST

In addition to our evaluations in the Atari domain, we also consider a variant
of the MNIST dataset in which the labels change over the course of training.

  * •

Inputs and Labels: We use 1000 randomly sampled input digits from the MNIST
dataset and assign either binary or random targets.

  * •

Distribution Shift: We divide training into $N=30$ or $N=10$ iterations
depending on the structure of the target function. In each iteration, a target
function is randomly sampled, and the network’s parameters obtained at the end
of the previous iteration are used the initial values for a new optimization
run. We use the Adam (Kingma and Ba, 2015) optimizer with learning rate 1e-3,
and train to minimize the mean squared error between the network outputs and
the targets for either 3000 or 5000 steps depending on the nature of the
target function.

  * •

Architecture: we use a standard fully-connected architecture with ReLU
activations, and vary the width and depth of the network. The parameters at
the start of the procedure are initialized following the defaults in the Jax
Haiku library.

We note that the dataset sizes, training budgets, and network sizes in the
following experiments are all relatively small. This was chosen to enable
short training times and decrease the computational budget necessary too
replicate the experiments. The particular experiment parameters were selected
to be the fastest and cheapest settings in which we could observe the capacity
loss phenomenon, while still being nontrivial tasks. In general, we found that
capacity loss is easiest to measure in a ’sweet spot’ where the task for a
given architecture is simple enough for a freshly-initialized network to
attain low loss, but complex enough that the network cannot trivially solve
the task. In the findings of the following section, we see how some of the
larger architectures do not exhibit capacity loss on ‘easier’ target
functions, but do on more challenging ones that exhibit less structure. This
suggests that replicating these results in larger networks will be achievable,
but will require re-tuning the task difficulty to the larger network’s
capacity.

####  13.2.2 Additional evaluations

Figure 13.1: Mean squared error at the end of training on each iteration of
the hash-MNIST task. Target-fitting error increases over time in smaller
networks, but increasing the depth or width of the network slows down capacity
loss, enabling positive transfer in the largest networks we studied.

We expand on the MNIST target-fitting task shown in the main text by
considering how network size and target function structure influences capacity
loss.

  * •

Random-MNIST (smooth) this task uses the images from the MNIST dataset as
inputs. The goal is to perform regression on the outputs of a randomly
initialized, fixed neural network. We use a small network for this task,
consisting of two width-30 fully connected hidden layers with ReLU activations
which feed into a final linear layer which outputs a scalar. Because the
network outputs are small, we scale them by 10 so that it is not possible to
get a low loss by simply predicting the network’s bias term. This task, while
randomly generated, has some structure: neural networks tend to map similar
inputs to similar outputs, and so the inductive bias of the targets will match
that of the function approximator we train on them.

  * •

Hash-MNIST (non-smooth) uses the same neural network architecture as the
previous task to generate targets, however rather than using the scaled
network output as the target, we multiply the output by 1e3 and feed it into a
sine function. The resulting targets no longer have the structure induced by
the neural network. This task amounts to memorizing a set of labels for the
input points.

  * •

Threshold-MNIST (sparse) replaces the label of an image with a binary
indicator variable indicating whether the label is smaller than some
threshold. To construct a sequence of tasks, we set the threshold at iteration
$i$ to be equal to $i$. This means that at the first iteration, the labels are
of the form $(x,0)$ for all inputs $x$. At the second iteration, they are of
the form $(x,\delta(y<1))$, where $y$ is the digit in the image $x$, and so
on.

We consider MLP networks of varying widths and depths, noting that the network
architecture used to generate the random targets is fixed and independent of
the approximating architecture. We are interested in evaluating whether
factors such as target function difficulty, network parameterization, and
number of target functions previously fit influence the network’s ability to
fit future target functions. Our results are shown in Figure 13.1, 13.2, and
13.3. We visualize srank and feature rank of the features output at the
network’s penultimate layer, in addition to the loss obtained at the end of
each iteration.

Figure 13.2: Mean squared error after 2e3 training steps on the random-MNIST
task. Target-fitting error increases over time in under-parameterized
networks, but increasing the depth or width of the network slows down capacity
loss, enabling positive transfer in the largest network we studied. Figure
13.3: Mean squared error after 2e3 training steps on the threshold-MNIST task.
Target-fitting error increases over time in under-parameterized networks, but
increasing the depth or width of the network slows down capacity loss,
enabling positive transfer in the largest network we studied.

####  13.2.3 Effect of InFeR on target-fitting capacity in MNIST

In addition to our study of the Atari suite, we also study the effect of InFeR
on the non-stationary MNIST reward prediction task with a fully-connected
architecture; see Figure 13.4. We find that it significantly mitigates the
decline in target-fitting capacity demonstrated in Figure 6.1.

Figure 13.4: Effect of adding InFeR to the regression objective in a random
reward prediction problem on the non-stationary MNIST environment studied
previously. We see that the InFeR objective produces networks that can
consistently outperform those trained with a standard regression objective,
exhibiting minimal capacity loss in comparison to the same network
architecture trained on the same sequence of targets.

###  13.3 Atari evaluations

We now present full evaluations of many of the quantities described in the
corresponding chapter, along with a study of the sensitivity of InFeR to its
hyperparameters. We use the same training procedure for all of the figures in
this section, loading agent parameters from checkpoints to compute the
quantities shown.

####  13.3.1 Hyperparameter sensitivity of InFeR in deep reinforcement
learning agents

We report results of hyperparameter sweeps over the salient hyperparameters
relating to InFeR, so as to assess the robustness of the method. For both the
DDQN and Rainbow agents augmented with InFeR, we sweep over the number of
auxiliary predictions (1, 5, 10, 20), the cumulant scale used in the
predictions (10, 100, 200), and the scale of the auxiliary loss (0.01, 0.05,
0.1, 0.2). We consider the capped human-normalized return across four games
(Montezuma’s Revenge, Hero, James Bond, and MsPacman), and run each
hyperparameter configuration with 3 seeds. Results are shown in Figure 13.5
for the DDQN agent; we compare performance as each pair of hyperparameters
varies (averaging across the other hyperparameter, games, and seeds, and the
last five evaluation runs of each agent). Corresponding results for Rainbow
are given in Figure 13.6.

Figure 13.5: Hyperparameter sweeps for the DDQN+InFeR agent. Each contour plot
shows average capped human-normalized score at the end of training
marginalized over all hyperparameters not shown on its axes.

Figure 13.6: Hyperparameter sweeps for the Rainbow+InFeR agent. Each contour
plot shows average capped human-normalized score at the end of training
marginalized over all hyperparameters not shown on its axes.

  * •

Agent: We train a Rainbow agent (Hessel et al., 2018) with the same
architecture and hyperparameters as are described in the open-source
implementation made available by Quan and Ostrovski (2020). We additionally
add InFeR, as described in Section 6.3, with 10 heads, gradient weight 0.1 and
scale 100.

  * •

Training: We follow the training procedure found in the Rainbow implementation
mentioned above. We train for 200 million frames, with 500K evaluation frames
interspersed every 1M training frames. We save the agent parameters and replay
buffer every 10M frames to estimate feature dimension and target-fitting
capacity.

####  13.3.2 Feature rank

We first extend the results shown in Figure 6.3 to two additional games:
Seaquest, and a sparsified version of Pong in which the agent does not receive
negative rewards when the opponent scores. In these settings, we stored agent
checkpoints once every 10M frames in each 200M frame trajectory, and used 5000
sampled inputs from the agent’s replay buffer to estimate the feature rank,
using the cutoff $\epsilon=0.01$. Results are shown in Figure 13.7.

Figure 13.7: Feature rank and performance of RL agents on demonstrative Atari
environments.

We further evaluate the evolution of feature rank in agents trained on all 57
games in the arcade learning environment in Figure 13.8. We find that the
decline in dimension after the first checkpoint at 10M frames shown across the
different agents in the selected games also occurs more generally in Rainbow
agents across most environments in the Atari benchmark. We also show that in
most cases adding InFeR mitigates this phenomenon. Our observations here do
not show a uniform decrease in feature rank or a uniformly beneficial effect
of InFeR. The waters become particularly muddied in settings where neither the
Rainbow nor Rainbow+InFeR agent consistently make learning progress such as in
tennis, solaris, and private eye. It is outside the scope of this work to
identify precisely why the agents do not make learning progress in these
settings, but it does not appear to be due to the type of representation
collapse that can be effectively prevented by InFeR.

Procedure. We compute the feature rank by sampling $n=50000$ transitions from
the replay buffer and take the set of origin states as the input set. We then
compute a $n\times d$ matrix whose row $i$ is given by the output of the
penultimate layer of the neural network given input $S_{i}$. We then take the
singular value decomposition of this matrix and count the number of singular
values greater than $0.01$ to get an estimate of the dimension of the
network’s representation layer.

In most games, we see a decline in feature rank after the first checkpoint at
10M frames. Strikingly, this decline in dimension holds even in the online RL
setting where the agent’s improving policy presumably leads it to observe a
more diverse set of states over time, which under a fixed representation would
tend to increase the numerical rank of the feature matrix. This indicates that
even in the face of increasing state diversity, agents’ representations face
strong pressure towards degeneracy. It is worth noting, however, that the
agents in dense-reward games do tend to see their feature rank increase
significantly early in training; this is presumably due to the network
initially learning to disentangle the visually similar states that yield
different bootstrap targets.

Figure 13.8: feature rank of agent representations over the course of training
on all 57 games in the Atari benchmark. We compare Rainbow against
Rainbow+InFeR.

####  13.3.3 Target-fitting capacity early in training

In this section we examine the target-fitting capacity of neural networks
trained with DQN, QR-DQN, and Rainbow over the course of $50$ million
environment frames on five games in the Atari benchmark (amidar, montezuma’s
revenge, pong, bowling, and hero). Every $1$ million training frames we save a
checkpoint of the neural network weights and replay buffer. For each
checkpoint, we generate a random target network by initializing network
weights with a new random seed. We then train the checkpoint network to
predict the output of this random target network for $10000$ mini-batch
updates (batch size of $32$) under a mean squared error loss, for states
sampled from the first $100,000$ frames in the checkpoint’s replay buffer.
Furthermore, we repeat this for $10$ seeds used to initialize the random
target network weights.

The results of this experiment are shown in Figure 13.9 (in orange), where the
solid lines show means and shaded regions indicate standard deviations over
all seeds (both agent seeds ($5$) and target fitting seeds ($10$), for a total
of $50$ trials). We also show srank and feature rank of the features output at
the network’s penultimate layer for each of the checkpointed networks used for
target fitting. These are computed using the network features generated from
$1000$ states sampled randomly from that checkpoint’s replay buffer. For
feature rank, averages and standard deviations are only over the $5$ agent
seeds.

Figure 13.9: Mean squared error, after $10000$ training steps for the target-
fitting on random network targets. We also show the corresponding feature rank
of the pre-trained neural network (before target-fitting).

####  13.3.4 Performance

We provide full training curves for both Rainbow and Rainbow+InFeR on all
games in Figures 13.10 & 13.11 (capped human-normalized performance), and
13.12 & 13.13 (raw evaluation score). We also provide evaluation performance
curves for DDQN and DDQN+InFeR agents in Figure 13.14.

Figure 13.10: Full evaluation of capped human-normalized performance on Atari
benchmarks for the default Rainbow architecture. Figure 13.11: Full evaluation
of capped human-normalized performance on Atari benchmarks in the double-width
Rainbow architecture. Figure 13.12: Full evaluation of raw scores on Atari
benchmarks for the default Rainbow architecture. Figure 13.13: Full evaluation
of raw scores on Atari benchmarks for the double-width Rainbow architecture.
Figure 13.14: Evaluations of the effect of InFeR on performance of a Double
DQN agent. Overall we see a slight improvement in average performance over all
games, alongside a significant improvement in Montezuma’s Revenge.

##  Chapter 14 Interference and generalization

###  14.1 Proofs

####  14.1.1 Proofs of main results

See 7.2.1

######  Proof 14.1.1.

Recall we assume the following dynamical system

$\displaystyle\partial_{t}V_{t}$ $\displaystyle=-(I-\gamma P^{\pi})V_{t}+R$
Inducing the trajectory $\displaystyle V_{t}$ $\displaystyle=\exp(-t(I-\gamma
P^{\pi}))(V_{0}-V^{\pi})+V^{\pi}$ As we assume $P^{\pi}$ is diagonalizable,
this implies that $(I-\gamma P^{\pi})$ is also diagonalizable. Let
$u_{1},\dots,u_{n}$ denote the right eigenvectors of $P^{\pi}$ with
corresponding eigenvalues $\lambda_{1}\geq\dots\geq\lambda_{n}$. Let
$V_{0}=\sum\alpha^{0}_{i}u_{i}$. $\displaystyle V_{t}$
$\displaystyle=\sum\alpha_{i}^{t}u_{i}$ $\displaystyle=\exp(-t(I-\gamma
P^{\pi}))(\sum\alpha_{i}^{0}-\alpha^{\pi}_{i}u_{i})+\sum\alpha^{\pi}_{i}u_{i}$
$\displaystyle=\sum\exp(-t(1-\gamma\lambda_{i}))\bigg{(}\sum(\alpha_{i}^{0}-\alpha_{i}^{\pi})u_{i}+\sum\alpha_{i}^{\pi}u_{i}\bigg{)}$
Now, we consider the value of $V_{t}-V^{\pi}$ along each coordinate. Note that
we have not assumed an orthogonal eigenbasis, thus cannot speak directly to
the norm of the projection of this difference onto the eigenspace
corresponding to each eigenvector $\lambda_{k}$. However, treating the
eigendecomposition as a basis, we can discuss how the coordinates
$\alpha^{t}_{i}$ of the value function $V_{t}$ converge with respect to this
basis. $\displaystyle|V_{t}-V^{\pi}|[i]=|\alpha^{t}_{i}-\alpha^{\pi}_{i}|$
$\displaystyle=|\exp(-t(1-\gamma\lambda_{i}))(\alpha_{i}^{0}-\alpha_{i}^{\pi})+\alpha_{i}^{\pi}-\alpha^{\pi}_{i}|$
$\displaystyle=|\exp(-t(1-\gamma\lambda_{i}))(\alpha_{i}^{0}-\alpha_{i}^{\pi})|=\exp(-t(1-\gamma\lambda_{i}))|(\alpha_{i}^{0}-\alpha_{i}^{\pi})|$

We conclude by noting that for large values of $\lambda_{i}$, the exponential
term $\exp(-t(1-\gamma\lambda_{i}))$ will decay more slowly as a function of
$t$ than for smaller values of $\lambda_{i}$. Thus, these coordinates (which
correspond to non-smooth functions over the state space) will converge
fastest. When the eigenvectors form an orthogonal basis, as is the case for
symmetric $P^{\pi}$, we can go further and observe that this convergence will
apply to the norm of the projection of the value function into the
corresponding eigenspace. Thus for symmetric $P^{\pi}$, we obtain the
following stronger convergence result, where $U_{k}$ denotes the eigenspace
corresponding to the eigenvalue $\lambda_{k}$.

$\|\Pi_{U_{k}}(V_{t}-V^{\pi})\|=\exp(-t(1-\gamma\lambda_{k}))\|\Pi_{U_{k}}(V_{0}-V^{\pi})\|$
(14.1)

See 1 Let $V_{0}=\sum\alpha_{i}v_{i}$. Then, letting $V_{t}$ be defined as in
Equation 7.4.

$\mathrm{TD}(V_{t})\leq\sum_{i=1}^{n}\exp(-2t(1-\gamma\lambda_{i}))(\alpha^{\pi}_{i}-\alpha_{i}^{0})^{2}(1-\gamma\lambda_{i})^{2}\;.$
(14.2)

######  Proof 14.1.2.

By our assumption on the diagonalizability of $P^{\pi}$, we can leverage the
previous result on the coordinates of $V_{t}$.

$\displaystyle V_{t}-V^{\pi}$
$\displaystyle=\sum\exp(-t(1-\gamma\lambda_{i}))\bigg{(}\sum(\alpha_{i}^{0}-\alpha_{i}^{\pi})u_{i}\bigg{)}$
We then bound the TD error as follows. $\displaystyle\|V_{t}-\gamma
P^{\pi}V_{t}-R\|^{2}$ $\displaystyle=\|V_{t}-\gamma P^{\pi}V_{t}+\gamma
P^{\pi}V^{\pi}-\gamma P^{\pi}V^{\pi}-R\|$ $\displaystyle=\|V_{t}-\gamma
P^{\pi}V^{\pi}-R-\gamma P^{\pi}(V_{t}-V^{\pi})\|$ Since $V^{\pi}=R+\gamma
P^{\pi}V^{\pi}$, we obtain the following. $\displaystyle=\|(I-\gamma
P^{\pi})(V_{t}-V^{\pi})\|^{2}$
$\displaystyle=\|\sum(1-\gamma\lambda_{k})(\alpha_{i}^{t}-\alpha_{i}^{\pi})u_{i}\|^{2}$
$\displaystyle\leq\sum(\alpha^{\pi}_{i}-\alpha^{t}_{i})^{2}(1-\gamma\lambda_{i})^{2}$

The remainder follows a straightforward substitution.

See 7.12

######  Proof 14.1.3.

While our prior analysis has considered the continuous time system
$\tilde{\theta}_{t}$, this does not perfectly approximate the discrete system
$\theta_{t}$. When a fixed step size is used, the first-order continuous-time
approximation accrues error roughly proportional to $\alpha t$. We then follow
the procedure of Barrett and Dherin (2021), applying a Taylor expansion to the
evolution of $\tilde{\theta}_{t}$ with respect to time. We will use the
notation $\tilde{\theta}(t)$ to denote the explicit dependence of
$\tilde{\theta}$ as a function of time.

$\displaystyle\tilde{\theta}(\alpha t)$
$\displaystyle=\tilde{\theta}(0)+\sum\frac{(\alpha t)^{n}}{n!}\theta^{(n)}(0)$
(14.3) $\displaystyle=\tilde{\theta}(0)+\alpha
tf(\tilde{\theta}(0))+\frac{(\alpha t)^{2}}{2}\nabla_{\theta}f\cdot
f(\tilde{\theta}(0))+O(\alpha^{3})$ (14.4)
$\displaystyle=\tilde{\theta}(0)+\alpha tf(\tilde{\theta}(0))+\frac{(\alpha
t)^{2}}{2}f_{1}(\theta(0))+O(\alpha^{3})$ (14.5) Relating this back to the
discrete system $\theta_{t}$ $\displaystyle\theta_{1}$
$\displaystyle=\theta_{0}+\alpha f(\theta_{0})=\tilde{\theta}(0)+\alpha
f(\tilde{\theta}(0))$ (14.6) $\displaystyle\theta_{1}$
$\displaystyle=\tilde{\theta}(1)-\frac{\alpha^{2}}{2}f_{1}(\tilde{\theta}(0))+O(\alpha^{3})$
(14.7) Thus, the system
$\partial_{t}\check{\theta}_{t}=f(\check{\theta}_{t})+\alpha^{2}/2f_{1}(\check{\theta}_{t})$
satisfies $\displaystyle\theta_{1}$
$\displaystyle=\check{\theta}(1)+O(\alpha^{3})$ (14.8)

We begin by observing that $\nabla_{\theta}\|V_{\theta}-\square
TV_{\theta}\|^{2}=(V_{\theta}-TV_{\theta})\cdot\nabla_{\theta}V_{\theta}=f(\theta)$.

$\displaystyle\theta$ $\displaystyle=\theta_{0}+\alpha nf(\theta_{0})+(\alpha
n)^{2}/2\nabla_{\theta}f(\theta_{0})\cdot f(\theta_{0})+O((\alpha n)^{3})$
(14.9) $\displaystyle=\theta_{0}+\alpha nf(\theta_{0})+\frac{(\alpha
n)^{2}}{2}f_{1}(\theta_{0})+O((n\alpha)^{3})$ (14.10) We then express
$f_{1}(\theta)$ as follows. $\displaystyle f_{1}(\theta_{0})$
$\displaystyle=\nabla_{\theta}[f(\theta_{0})]\cdot[f(\theta_{0})]$ (14.11)
$\displaystyle=[\nabla^{2}_{w}V_{\theta}\cdot((\gamma
P^{\pi}-I)V_{\theta}+r)+\nabla_{\theta}V_{\theta}\cdot((\gamma
P^{\pi}-I)\nabla_{\theta}V_{\theta})][f(\theta)]$ (14.12)
$\displaystyle=[\nabla_{\theta}^{2}V_{\theta}\cdot((\gamma
P^{\pi}-I)V_{\theta}+r)+\nabla_{\theta}V_{\theta}\cdot\nabla_{\theta}V_{\theta}][f(\theta)]$
(14.13)
$\displaystyle\quad+\gamma[\nabla_{\theta}V_{\theta}P^{\pi}\nabla_{\theta}V_{\theta}][f(\theta)]$
(14.14) Noting that the left hand side term is equal to the gradient of the
gradient norm penalty for the stop-gradient version of the TD regression
problem, we simplify as follows:
$\displaystyle=\frac{1}{2}\nabla_{\theta}\|\nabla_{\theta}\frac{1}{2}\|V_{\theta}-\square
T^{\pi}V_{\theta}\|^{2}\|^{2}+\gamma[\nabla_{\theta}V_{\theta}\cdot
P^{\pi}\cdot\nabla_{\theta}V_{\theta}][f(\theta)]$ (14.15)

We note that, unlike in the stochastic gradient descent setting, $f_{1}$ does
not correspond to a gradient of any function. Instead, it corresponds to the
second-order we would get for a frozen target, which corresponds to a gradient
norm penalty, plus a term that measures the alignment of the gradients at each
state and its expected successor. Intuitively, both of these terms minimize
the ‘variance’ in the loss induced by noisy, discrete gradient steps. The
flatter loss surfaces induced by the gradient norm penalty will naturally lead
to greater robustness to parameter perturbations. The gradient alignment term
reflects the observation previously that non-smooth functions contribute the
most to the TD error, and so encourages the first-order gradient effects on
successive states to move in a similar direction.

We note that this final observation seems to be at odds with the tendency for
TD learning to encourage more tabular updates. Why would a second-order
correction term which promotes flat minima and gradient alignment result in
tabular updates? To answer this, we point to the tendency of TD targets to
converge along. the non-smooth components of the value function first. We are
therefore faced with finding a flat region of parameter space to fit a
discontinuous function. A representation which succeeds at this will benefit
from minimizing interference between states, as the gradients for one
transition will be on average uncorrelated with even nearby other states. The
gradient alignment penalty suggests that, while the implicit regularization
will prefer flat minima, smooth interference patterns which move other states
in a similar direction to the current state will be penalized less than non-
smooth directions.

######  Corollary 3.

The second-order dynamics push features towards precisely the worst direction
w.r.t. stability. I.p. looking at the set of positive definite representations
introduced by Ghosh and Bellemare (2020) we see

$\\{v:v^{\top}P^{\pi}v<\gamma^{-1}\|v\|_{\Xi}\\}$ (14.16)

whereas the optimal gradients for the second order term implicitly solve the
following optimization problem

$\min\mathbb{E}_{x\sim\eta(x)}[g(x)^{\top}g(x)-\gamma
g(x)^{\top}(P^{\pi}g)(x)]$ (14.17)

See 2

######  Proof 14.1.4.

We leverage the dynamics
$\partial_{t}V_{t}=K(X,X)\nabla_{\theta}V_{\theta}\cdot((\gamma P^{\pi}-I)+r)$
and follow the derivation of Section 5 of Jacot et al. (2018).

We can develop intuitions for the kernel gradient descent setting by
considering the special case of linear function approximation, where
$K(x_{1},x_{2})=\langle\phi(x_{1}),\phi(x_{2})\rangle$ for some feature map
$\phi$. For the moment, we will define $\Phi$ to be a matrix consisting of
features for every state in the state space $X$ (i.e. we update all states in
the mdp at once). We then obtain

$\displaystyle\partial_{t}\mathbf{w}_{t}$
$\displaystyle=\alpha\Phi^{\top}(R^{\pi}+\gamma
P^{\pi}\Phi\mathbf{w}_{t}-\Phi\mathbf{w}_{t})\,.$ (14.18)

We can express the evolution of the value function constructed by
multiplication of $\Phi$ and $w$ as follows.

$\displaystyle\partial_{t}V_{t}$
$\displaystyle=(\partial_{w}V_{t})^{\top}\partial_{t}w_{t}=\Phi\partial_{t}w_{t}$
(14.19) $\displaystyle=-\Phi(\Phi^{\top}(I-\gamma P^{\pi})\Phi)w$ (14.20)
$\displaystyle=-\Phi\Phi^{\top}(I-\gamma P^{\pi})V_{t}$ (14.21)
$\displaystyle=-K(I-\gamma P^{\pi})V_{t}$ (14.22) We further consider the
dynamics of the value function on inputs outside of the set of states on which
the Bellman updates are computed as follows.
$\displaystyle\partial_{t}V_{t}(x_{\mathrm{test}})$
$\displaystyle=(\partial_{w}V_{t}(x_{\mathrm{test}}))^{\top}\partial_{t}w_{t}$
(14.23) $\displaystyle=-\phi(x_{\mathrm{test}})^{\top}\Phi^{\top}(I-\gamma
P^{\pi})V_{t}$ (14.24)
$\displaystyle=-K(x_{\mathrm{test}},X_{\mathrm{train}})K(X_{\mathrm{train}},X_{\mathrm{train}})^{-1}\partial_{t}V_{t}$
(14.25)

We now lift the assumption that all states are updated. In this more general
kernel gradient descent setting, we let $K$ be a kernel as before, with
$\tilde{K}=K(X_{\mathrm{train}},X_{\mathrm{train}})$ and
$\kappa_{x_{\mathrm{test}}}=K(x_{\mathrm{test}},X_{\mathrm{train}})$. We then
obtain the following dynamics

$\displaystyle\partial_{t}V_{t}(x_{\mathrm{test}})$
$\displaystyle=\kappa_{x_{\mathrm{test}}}\tilde{K}^{-1}\partial_{t}V_{t}(X_{\mathrm{train}})$
(14.26) In particular, this results in the following trajectory.
$\displaystyle V_{t}(x_{\mathrm{test}})$
$\displaystyle=V_{0}(x_{\mathrm{test}})+\kappa_{x_{\mathrm{test}}}\tilde{K}^{-1}[V_{t}(X_{\mathrm{train}})-V_{0}(X_{\mathrm{train}})]$
(14.27)

An interesting case study occurs when we consider, e.g., off-policy evaluation
where the bootstrap targets used in the TD updates may not have been visited
by the agent during training. This will be the case in many offline RL
problems, where the action that would be selected by the policy we seek to
evaluate was not taken by the behaviour policy, and so the agent leverages
bootstrap targets which are not updated as part of the training set of states.
In such cases, we will decompose the state space as
$X=X_{\mathrm{train}}\oplus X_{\mathrm{test}}$. The dynamics we get in this
case look quite different from standard kernel regression, as the dynamics of
the training states will depend on the predictions on the ‘test’ states. To
condense notation, we will use $T^{\pi}V_{t}$ to refer to an application of
the Bellman operator $V_{t}\mapsto\gamma P^{\pi}V_{t}+R^{\pi}$.

$\displaystyle\partial_{t}V_{t}(X_{\mathrm{train}})$
$\displaystyle=\Phi_{{\mathrm{train}}}\Phi_{\mathrm{train}}^{\top}((T^{\pi}V_{t})(X_{\mathrm{train}})-V_{t}(X_{\mathrm{train}}))$
(14.28) $\displaystyle\partial_{t}V_{t}(X_{\mathrm{test}})$
$\displaystyle=\Phi_{{\mathrm{test}}}\Phi_{\mathrm{train}}^{\top}((T^{\pi}V_{t})(X_{\mathrm{train}})-V_{t}(X_{\mathrm{train}}))$
(14.29) We note that $(T^{\pi}V_{t})(X_{\mathrm{train}})$ depends on both
$V(X_{\mathrm{train}})$ and $V(X_{\mathrm{test}})$ due to the application of
the Bellman operator $T^{\pi}$. We thus end up with the following joint
system. $\displaystyle\partial_{t}V_{t}(X_{\mathrm{train}}\oplus
X_{\mathrm{test}})$
$\displaystyle=\Phi_{{\mathrm{test}}}\Phi_{\mathrm{train}}^{\top}((T^{\pi}V_{t})(X_{\mathrm{train}})-V_{t}(X_{\mathrm{train}}))\oplus\Phi_{{\mathrm{train}}}\Phi_{\mathrm{train}}^{\top}((T^{\pi}V_{t})(X_{\mathrm{train}})-V_{t}(X_{\mathrm{train}}))$
(14.30) $\displaystyle\partial_{t}V_{t}(X_{\mathrm{train}}\oplus
X_{\mathrm{test}})$
$\displaystyle=(\Phi_{{\mathrm{test}}}\oplus\Phi_{{\mathrm{train}}})\Phi_{\mathrm{train}}^{\top}((T^{\pi}V_{t})(X_{\mathrm{train}})-V_{t}(X_{\mathrm{train}}))$
(14.31) Using a non-standard notation of $K_{1}\oplus K_{2}:=X\mapsto
K_{1}(X)\oplus K_{2}(X)$, we can then rewrite the above in terms of the dot
product kernel $K(x,x^{\prime})$ as follows.
$\displaystyle\partial_{t}V_{t}(X_{\mathrm{all}})$
$\displaystyle=(\tilde{K}\oplus\kappa_{x_{\mathrm{test}}})[(T^{\pi}V_{t}-V_{t})(X_{\mathrm{train}})]$
(14.32)

We emphasize that while this at first looks as though the dynamics are
independent of the value $V_{t}(X_{\mathrm{test}})$, this is an artefact of
the Bellman operator notation $(T^{\pi}V_{t})(X_{t})$, which hides the
dependence of the Bellman targets $T^{\pi}V_{t}$ on $X_{\mathrm{test}}$. In
particular, we can write
$(T^{\pi}V_{t})(X_{t})=\Pi_{X_{\mathrm{train}}}[\gamma
P^{\pi}V_{t}(X_{\mathrm{train}}\oplus X_{\mathrm{test}})+R^{\pi}]$, which
makes this dependence more explicit but is less succinct.

###  14.2 Experiment details

####  14.2.1 Estimation of update rank

To estimate the update rank of an agent, we sample $k$ transitions from the
agent’s replay buffer and compute the matrix $A(\theta)$ as described in
Section 7.3. We use the agent’s current optimizer state and its current
parameters in this computation. We then take the singular value decomposition
of $A$ to obtain $k$ singular values $S=\\{\sigma_{1},\dots,\sigma_{k}\\}$. We
then threshold using the numerical approach taken in prior works (Maddox et
al., 2020), and compute the size of the set $S_{\epsilon}=\\{\sigma\in
S:\sigma>\epsilon\max(S)\\}$. This allows us to ignore directions of near-zero
variation in the update matrix. In practice, we use $\epsilon=0.1$.

Because the Q-functions learned by value-based deep RL agents are vector-
rather than scalar-valued functions of state, and our estimator depends on an
2-dimensional update matrix, we must make a choice on how to represent the
change in the state-value function. We considered taking the maximum over
actions, the mean over actions, selecting a fixed action index, and selecting
the action taken in the transition on which the update was computed, and found
that both choices produced similar trends. In all evaluations in this paper,
Q-functions are reduced using the max operator. We apply the same approach for
distributional agents by taking the expectation over the distribution
associated with each state-action pair.

To evaluate the policy-based agents, whose outputs correspond to distributions
over actions, we compute the norm of the difference in the output probability
distributions for each state in lieu of taking the difference of output
values. I.e., the entry $A_{i,j}=\|p_{\theta}(x_{j})-p_{\theta_{i}}(x_{j})\|$,
where the discrete probability distribution $p_{\theta}$ is taken as a vector.

####  14.2.2 ProcGen

Figure 14.1: Example levels from the dodgeball environment.

The ProcGen benchmark consists of sixteen procedurally generated environments.
Each environment consists of a set of randomly generated levels, of which a
fixed subset are used for training and a disjoint subset are used for
evaluation. Levels differ superficially in their observations and initial
sprite layouts but retain the same underlying structure, as can be seen in
Figure 14.1. The observation space is a box space with the RGB pixels the
agent sees in a numpy array of shape (64, 64, 3).

Our PPO and DAAC agents use the same hyperparameters and implementation as is
provided by Raileanu and Fergus (2021). Our behaviour cloning objective
minimizes the KL divergence between the distillation agent the pretrained
agent’s policies, with an entropy bonus equal to that used to train the
original PPO agent.

####  14.2.3 Atari

We additionally perform evaluations on environments from the Atari benchmarks.
Due to computational constraints, we consider only a subset of the entire
benchmark. We obtain a mixture of easy games, such as pong and boxing, and
more challenging games like seaquest, where we measure difficulty by the time
it takes for the agent to meet human performance. For some experiments, we
used the sparse-reward environment Montezuma’s Revenge.

In our distillation experiments, we train the original agent for 50M frames
using $\epsilon$-greedy exploration with $\epsilon=0.1$, and train the
distillation agents for a number of updates equivalent to 10M frames of data
collected online. We base our implementation off of the open-source
implementations in Ostrovski et al. (2021).

For our behaviour cloning objective, we use the same architecture as is used
for DQN, but feed the final layer of actions into a softmax to obtain a
probability distribution over actions, which we denote as $P_{\theta}(a|x)$.
Given a state-action pair taken by the target agent, we implement the
following behaviour cloning loss for distillation

$\ell(\theta,x_{i},a_{i})=-\log
P_{\theta}(a_{i}|x_{i})-0.1H(P_{\theta}(\cdot|x_{i}))$ (14.33)

where $H$ denotes the entropy of a distribution. We use a replay capacity of
1e6 and allow the pre-trained agent to collect additional data during
distillation to further increase the training set size of the distilled
agents.

###  14.3 Additional numerical evaluations

We provide additional numerical evaluations to provide insight into the
theoretical results of Section 7.2.

####  14.3.1 Fourier analysis

We begin by studying the Fourier decomposition of value and reward functions
in popular Atari domains by treating the value function as a function of time
rather than as a function of observations. In this sense, the Fourier
decomposition is measuring the continuity of the value function with respect
to time and so is a closer approximation of the notion of smoothness we focus
on in Section 7.2.1. We show our evaluations in Figure 14.2.

Figure 14.2: Fourier decomposition of Atari value functions when viewed as a
function of time. We sample $k$ consecutive states from the replay buffer and
compute the predicted value on each state (fixing an arbitrary action) to get
a function $V:\\{1,\dots,k\\}\rightarrow\mathbb{R}$. We then compute the
Fourier decomposition of this function. The top row shows indices $k=0\dots
50$, while the bottom row omits the $k=0$ index (the constant function) to
better illustrate the rate of decay of the spectrum of each function.

####  14.3.2 Kernel gradient descent

We include an illustration of the kernel gradient descent dynamics described
in Section 7.2.2 in Figure 14.3. We run our evaluations using a radial basis
function (RBF) kernel of varying lengthscale, with shorter lengthscales
corresponding to weaker generalization between states. While the shorter
lengthscale corresponds to more stable learning dynamics and better fitting of
the value function on the training set, it also induces greater value
approximation error on the test states. In contrast, the longer lengthscales
result in better generalization to novel test states under Monte Carlo
dynamics, but result in divergence for large values of $\gamma$.

Figure 14.3: Numerical evaluations of kernel gradient descent with an RBF
kernel. The MDP in question is a "circle MDP" whose states are integers
$n\in\\{1,\dots,50\\}$. We assume the agent is ‘trained’ on states 1 to 40,
and does not perform value function updates on the final ten states, use the
policy which always takes the agent from state $n$ to $n+1\mod 50$, and set a
single reward at state 25. Each row corresponds to a different value of the
discount factor $\gamma$: the top corresponds to $\gamma=0.5$, and the bottom
to $\gamma=0.99$. Each column corresponds to the lengthscale which
parameterizes the kernel, going left to right: 0.01, 1.0, and 100. The left
hand side and right hand side are distinguished by the number of update steps
which the TD dynamics are evaluated for. The LHS runs TD for only 20 steps,
while the RHS runs it for 100 steps. MC updates are run for 1500 steps on both
figures. We see that for $\gamma=0.99$, the larger-lengthscale kernel
predictions diverge under TD dynamics, though not Monte Carlo. The Monte Carlo
dynamics further nicely illustrate the trade-off between generalizing out of
the training set and ability to fit the discontinuities of the value function
on the training set. The larger lengthscale has lower MSE from the value
function on the test set, but fails to fit the discontinuity of the value
function at the reward state. Meanwhile, the smaller lengthscales easily fit
the value function on the training set but predict zero for all over states.

Additionally, as promised in Section 7.2.2, we illustrate the role of smooth
eigenfunctions in generalization in Figure 14.4. To produce this figure, we
randomly generate an unweighted graph and then construct an MDP whose dynamics
correspond to a random walk on this graph. We consider the generalization
error of a kernel regression process where the kernel $K_{S}$ is of the form
$K_{S}(x,y)=\sum_{i\in S}v_{\lambda_{i}}(x)v_{\lambda_{i}}(y)$ for some
$S\subseteq\mathrm{spec}(P^{\pi})$. In the right-hand-side plot of Figure
14.4, we set $S=\\{1,\dots,20\\}$, so that our analysis concentrates on smooth
eigenfunctions. We then consider the generalization error of this smooth
kernel when we only regress on a subset of the state space selected uniformly
at random111Because the MDP-generating process is invariant to permutations of
the state indices, we sample the indices
$\\{1,\dots,\lfloor|\mathcal{X}|\times\mathrm{trainingfraction}\rfloor\\}$,
and average over randomly generated MDPs. . We study the effect of varying the
size of this set, i.e. the fraction of states in the training set, in Figure
14.4, in order to quantify the degree to which additional information about
the value function translates to improved generalization. We consider three
regression problems: regression on $V^{\pi}$, regression on the projection of
$V^{\pi}$ onto the span of $T=\\{v_{1},\dots,v_{20}\\}$, and
$B=\\{v_{n-19},\dots,v_{n}\\}$. Unsurprisingly, we see that the smooth kernel
is able to improve its generalization performance as the size of the training
set increases when it is set to regress $V^{\pi}$ or
$\Pi_{T}V^{\pi}=V^{\pi}_{T}$. However, when the kernel regresses only on the
projection of $V^{\pi}$ onto the non-smooth eigenvectors, we do not see a
benefit of adding additional training points: because there is no information
about the smooth components of the function in the targets, adding additional
data points will not help to improve regression accuracy. The left hand side
of the figure shows similarly that fitting local information in the form of
$n$-step returns for small $n$ also does not provide the kernel with
sufficient information for it to be able to extrapolate and improve its
generalization error as the size of the training set increases.

Figure 14.4: Generalization of predicted function under kernel regression
using $n$-step return targets evaluated on a random subset of states (left),
and projecting value function onto top or bottom eigenvectors of $P^{\pi}$
(right). We see a similar trend where for larger $n$ (corresponding to
smoother targets), the kernel regression method generalizes better with
increasing dataset sizes. For smaller $n$ and for the projection of $V^{\pi}$
onto non-smooth eigenvectors, adding additional data points does not improve
generalization performance.

###  14.4 Additional empirical results

####  14.4.1 Additional value distillation results

We consider three different types of regression to the outputs of the pre-
trained network, along with two more traditional bootstrapping methods for
offline RL. Q-regression regresses the outputs of the distilled network to
those of the pre-trained network for every action. qa-regression only does
q-value regression on the action taken by the pre-trained agent. adv-
regression regresses on the advantage function (computed as the q-value minus
the mean over all actions) given by the pre-trained agent; qr does quantile
regression q-learning on the offline data; double-q performs a standard double
q-learning update on the offline data.

We find that all of these methods obtain an initial update rank significantly
below that of the pre-trained network when they begin training, which
increases over time. Regression to the advantages obtains a significantly
lower update rank than any other method, suggesting that the advantage
function may be much smoother than the action-value function. With respect to
performance on the original environment, we see that the methods which use all
action values at every update obtain significantly higher performance than
those which only update a single action at a time. This improvement in
performance is not mediated by an auxiliary task effect or an increase in the
network’s ability to distinguish states: the advantage regression network
attains low update rank but high performance, while the qr-regression task
provides a great deal of information to the representation but is not
competitive with the q-regression network.

Figure 14.5: Results from post-training distillation on a variety of
objectives. We note that advantage regression tends to exhibit the lowest
update rank, with the qr agent tending to exhibit the highest update rank and
the q-regression objectives falling somewhere in between. Because the
behaviour cloning objective minimizes a cross-entropy loss rather than a
regression loss, further investigation is required to understand how the
trajectory of its update dimension differs from those of the regression
objectives.

####  14.4.2 More detailed update trajectories

We include a more detailed view of the update matrices obtained by DQN and C51
agents during the first 7 million frames of training, roughly 5% of the
training budget, in Figure 14.6. We see that even early in training, the DQN
and C51 agents both exhibit significant overfitting behaviour. Note that
states are sampled uniformly at random from the replay buffer, and then
assigned an index based on the output of a clustering algorithm to improve
readability of the figures.

Figure 14.6: Update matrices for distributional and DQN agents on four games
from the Atari suite, chosen to represent a range of reward densities and
difficulties. Each iteration corresponds to 1e5 training frames.

##  Chapter 15 Generalization across environments

###  15.1 Implementation details

####  15.1.1 Model learning: rich observations

For the model learning experiments we use an almost identical encoder
architecture as in Tassa et al. (2018), with two more convolutional layers to
the convnet trunk. Secondly, we use ReLU activations after each convolutional
layer, instead of ELU. We use kernels of size $3\times 3$ with $32$ channels
for all the convolutional layers and set stride to $1$ everywhere, except of
the first convolutional layer, which has stride $2$. We then take the output
of the convolutional net and feed it into a single fully-connected layer
normalized by LayerNorm (Ba et al., 2016). Finally, we add tanh nonlinearity
to the $50$ dimensional output of the fully-connected layer.

The decoder consists of one fully-connected layer that is then followed by
four deconvolutional layers. We use ReLU activations after each layer, except
the final deconvolutional layer that produces pixels representation. Each
deconvolutional layer has kernels of size $3\times 3$ with $32$ channels and
stride $1$, except of the last layer, where stride is $2$.

The dynamics and reward models are all MLPs with two hidden layers with 200
neurons each and ReLU activations.

####  15.1.2 Reinforcement learning

For the reinforcement learning experiments we modify the Soft Actor-Critic
PyTorch implementation by Yarats and Kostrikov (2020) and augment with a
shared encoder between the actor and critic, the general model $f_{s}$ and
task-specific models $f_{\eta}^{e}$. The forward models are multi-layer
perceptions with ReLU non-linearities and two hidden layers of 200 neurons
each. The encoder is a linear layer that maps to a 50-dim hidden
representation. We also use L1 regularization on the $S$ latent
representation. We add two additional dimensions to the state space, a
spurious correlation dimension that is a multiplicative factor of the last
dimension of the ground truth state, as well as an environment id. We add
Gaussian noise $\mathcal{N}(0,0.01)$ to the original state dimension, similar
to how Arjovsky et al. (2019) incorporate noise in the label to make the task
harder for the baseline.

Soft Actor Critic (SAC) Haarnoja et al. (2018) is an off-policy actor-critic
method that uses the maximum entropy framework to derive soft policy
iteration. At each iteration, SAC performs soft policy evaluation and
improvement steps. The policy evaluation step fits a parametric soft
Q-function $Q(x_{t},a_{t})$ using transitions sampled from the replay buffer
$\mathcal{D}$ by minimizing the soft Bellman residual,

$J(Q)=\mathbb{E}_{(x_{t},x_{t},r_{t},x_{t+1})\sim\mathcal{D}}\bigg{[}\bigg{(}Q(x_{t},a_{t})-r_{t}-\gamma\bar{V}(x_{t+1})\bigg{)}^{2}\bigg{]}.$

The target value function $\bar{V}$ is approximated via a Monte-Carlo estimate
of the following expectation,

$\bar{V}(x_{t+1})=\mathbb{E}_{a_{t+1}\sim\pi}\big{[}\bar{Q}(x_{t+1},a_{t+1})-\alpha\log\pi(a_{t+1}|x_{t+1})\big{]},$

where $\bar{Q}$ is the target soft Q-function parameterized by a weight vector
obtained from an exponentially moving average of the Q-function weights to
stabilize training. The policy improvement step then attempts to project a
parametric policy $\pi(a_{t}|x_{t})$ by minimizing KL divergence between the
policy and a Boltzmann distribution induced by the Q-function, producing the
following objective,

$J(\pi)=\mathbb{E}_{x_{t}\sim\mathcal{D}}\bigg{[}\mathbb{E}_{a_{t}\sim\pi}[\alpha\log(\pi(a_{t}|x_{t}))-Q(x_{t},a_{t})]\bigg{]}.$

We provide the hyperparameters used for the RL experiments in table 15.1.

Parameter name | Value
---|---
Replay buffer capacity | $1000000$
Batch size | $1024$
Discount $\gamma$ | $0.99$
Optimizer | Adam
Critic learning rate | $10^{-5}$
Critic target update frequency | $2$
Critic Q-function soft-update rate $\tau_{\textrm{Q}}$ | 0.005
Critic encoder soft-update rate $\tau_{\textrm{enc}}$ | 0.005
Actor learning rate | $10^{-5}$
Actor update frequency | $2$
Actor log stddev bounds | $[-5,2]$
Encoder learning rate | $10^{-5}$
Decoder learning rate | $10^{-5}$
Decoder weight decay | $10^{-7}$
L1 regularization weight | $10^{-5}$
Temperature learning rate | $10^{-4}$
Temperature Adam’s $\beta_{1}$ | $0.9$
Init temperature | $0.1$

Table 15.1:  A complete overview of used hyper parameters.

## Contributions to joint-authored work

The research in this thesis is the product of a number of valuable
collaborations.

Chapter 3 is based on work presented at the NeurIPS 2019 workshop on machine
learning with guarantees (Lyle et al., 2019b). All empirical results in this
section were proposed and implemented by me. While I produced an initial
analysis of PAC-Bayes bounds under symmetries and showed a preliminary version
of Theorem 3.4.3 for finite groups independently, I worked closely with
Benjamin Bloem-Reddy to generalize these initial results to the form presented
in this thesis.

Chapter 4 is principally built on the NeurIPS 2020 paper (Lyle et al., 2020),
but also draws on some of the insights developed in a tandem work led by
Binxin Ru and myself which was presented at NeurIPS 2021 (Ru et al., 2021). I
was responsible for all theoretical and empirical results concerning linear
models and gradient alignment, while Lisa Schut extended and improved on my
initial toy experiments on neural networks to generate Figures 4.5 and 11.4.
Figure 4.6 was produced independently by me, but was inspired by analysis
initially performed by Binxin Ru.

Chapter 5 was written in close collaboration with Mark Rowland and Will
Dabney, and the initial research question sparking this project was
brainstormed during joint meetings involving all authors. I ran the
evaluations for Figure 5.3 and performed the evaluations on linear value
function evolution in Appendix 12.8. Mark proposed the continuous-time
formalism and proved the initial subspace convergence result for a single
value function, while I proposed the ‘exact feature update’ framework and
proved the results concerning auxiliary tasks and ensemble prediction.

Chapter 6 is based on work I led during an internship at DeepMind (Lyle et
al., 2022a). I conducted additional analysis into the learned representations
of the agents used for the empirical results of that work, and eventually
formulated the main hypotheses of this chapter based on that analysis. I wrote
and ran the experiment code for the supervised and Atari benchmarks. My co-
authors ran code I had written during my internship after I returned to Oxford
to generate final versions of several figures, and provided helpful discussion
throughout the project.

Chapter 7 is based on (Lyle et al., 2022b), for which I was the lead author. I
was responsible for the implementations in all empirical results and for the
proposal and initial proofs of the theoretical results. The other authors on
the paper provided feedback on early drafts of the paper and recommendations
for interesting experimental conditions to pursue.

Chapter 8 is based on a paper co-first-authored by myself and Amy Zhang. I
stated and proved all theoretical results included in the thesis, proposed the
algorithm for linear state abstractions, and implemented the linear model
experiments. Both Amy and I worked together to propose the nonlinear MISA
architecture and training objective.

## References

  * Abdolshah et al. [2021] Majid Abdolshah, Hung Le, Thommen Karimpanal George, Sunil Gupta, Santu Rana, and Svetha Venkatesh.  A new representation of successor features for transfer across dissimilar environments.  In _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , pages 1–9. PMLR, 2021.
  * Abel et al. [2019] David Abel, Dilip Arumugam, Kavosh Asadi, Yuu Jinnai, Michael L Littman, and Lawson LS Wong.  State abstraction as compression in apprenticeship learning (icml).  In _Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press._ , 2019.
  * Achille et al. [2018] Alessandro Achille, Matteo Rovere, and Stefano Soatto.  Critical learning periods in deep networks.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Advani et al. [2020] Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky.  High-dimensional dynamics of generalization error in neural networks.  _Neural Networks_ , 132:428–446, 2020.
  * Agarwal et al. [2020] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi.  An optimistic perspective on offline reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 2020.
  * Ahuja et al. [2020] Kartik Ahuja, Karthikeyan Shanmugam, Kush Varshney, and Amit Dhurandhar.  Invariant risk minimization games.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 145–155. PMLR, 2020.
  * Akaike [1998] Hirotogu Akaike.  _Information Theory and an Extension of the Maximum Likelihood Principle_ , pages 199–213.  Springer, 1998.
  * Alesiani et al. [2021] Francesco Alesiani, Shujian Yu, and Mathias Niepert.  Continual invariant risk minimization, 2021.
  * Amit and Meir [2018] Ron Amit and Ron Meir.  Meta-learning by adjusting priors based on extended PAC-Bayes theory.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 205–214, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Anschel et al. [2017] Oron Anschel, Nir Baram, and Nahum Shimkin.  Averaged-DQN: Variance reduction and stabilization for deep reinforcement learning.  In _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , 2017.
  * Arjovsky et al. [2019] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz.  Invariant risk minimization.  _arXiv preprint arXiv:1907.02893_ , 2019.
  * Arora et al. [2019] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , 2019.
  * Arpit et al. [2017] Devansh Arpit, Stanisław Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al.  A closer look at memorization in deep networks.  In _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , pages 233–242. PMLR, 2017.
  * Ash and Adams [2020] Jordan Ash and Ryan P Adams.  On warm-starting neural network training.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Ba et al. [2016] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton.  Layer normalization.  _arXiv preprint_ , 2016.
  * Baird [1993] L Baird.  Advantage updating.  _Technical Report_ , 1993.
  * Barreto et al. [2017] André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver.  Successor features for transfer in reinforcement learning.  In _Advances in neural information processing systems_ , pages 4055–4065, 2017.
  * Barrett and Dherin [2021] David Barrett and Benoit Dherin.  Implicit gradient regularization.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Bartlett [1997] Peter L Bartlett.  For valid generalization the size of the weights is more important than the size of the network.  In _Advances in neural information processing systems_ , pages 134–140, 1997.
  * Bartlett et al. [2017] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In _Advances in Neural Information Processing Systems_ , pages 6240–6249, 2017.
  * Bartlett et al. [2020] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler.  Benign overfitting in linear regression.  _Proceedings of the National Academy of Sciences_ , 117(48):30063–30070, 2020.
  * Bartoldson et al. [2020] Brian Bartoldson, Ari Morcos, Adrian Barbu, and Gordon Erlebacher.  The generalization-stability tradeoff in neural network pruning.  _Advances in Neural Information Processing Systems_ , 33:20852–20864, 2020.
  * Basu [1955] D. Basu.  On statistics independent of a complete sufficient statistic.  _Sankhyā: The Indian Journal of Statistics (1933-1960)_ , 15(4):377–380, 1955.  ISSN 00364452.
  * Baum and Haussler [1989] Eric B Baum and David Haussler.  What size net gives valid generalization?  In _Advances in neural information processing systems_ , pages 81–90, 1989.
  * Beck et al. [2021] Nathan Beck, Durga Sivasubramanian, Apurva Dani, Ganesh Ramakrishnan, and Rishabh Iyer.  Effective evaluation of deep active learning on image classification tasks.  _arXiv preprint_ , 2021.
  * Behzadian and Petrik [2018] Bahram Behzadian and Marek Petrik.  Feature selection by singular value decomposition for reinforcement learning.  In _ICML Prediction and Generative Modeling Workshop_ , 2018.
  * Belkin et al. [2019] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine learning and the bias-variance trade-off.  _Proceedings of the National Academy of Sciences_ , 116(32):15849–15854, 2019.
  * Bellemare et al. [2013] 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_ , 47:253–279, 2013.
  * Bellemare et al. [2017] Marc G Bellemare, Will Dabney, and Rémi Munos.  A distributional perspective on reinforcement learning.  In _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , 2017.
  * Bellemare et al. [2019] Marc G 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.  _Advances in neural information processing systems_ , 2019.
  * Bengio et al. [2017] Emmanuel Bengio, Valentin Thomas, Joelle Pineau, Doina Precup, and Yoshua Bengio.  Independently controllable features.  In _Reinforcement Learning and Decision Making (RLDM)_ , 2017.
  * Bengio et al. [2020] Emmanuel Bengio, Joelle Pineau, and Doina Precup.  Interference and generalization in temporal difference learning (icml).  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 767–777. PMLR, 2020.
  * Bengio et al. [2014] Yoshua Bengio, Mehdi Mirza, Ian Goodfellow, Aaron Courville, and Xia Da.  An empirical investigation of catastrophic forgeting in gradient-based neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2014.
  * Benjamin et al. [2019] Ari Benjamin, David Rolnick, and Konrad Kording.  Measuring and regularizing networks in function space.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Benton et al. [2021] Gregory W Benton, Wesley J Maddox, Sanae Lotfi, and Andrew Gordon Wilson.  Loss surface simplexes for mode connecting volumes and fast ensembling.  _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , 18–24 Jul 2021.
  * Berariu et al. [2021] Tudor Berariu, Wojciech Czarnecki, Soham De, Jorg Bornschein, Samuel Smith, Razvan Pascanu, and Claudia Clopath.  A study on the plasticity of neural networks.  _arXiv preprint arXiv:2106.00042_ , 2021.
  * Bertsekas [2018] Dimitri P Bertsekas.  Feature-based aggregation and deep reinforcement learning: A survey and some new implementations.  _IEEE/CAA Journal of Automatica Sinica_ , 6(1):1–31, 2018.
  * Bertsekas and Tsitsiklis [1996] Dimitri P Bertsekas and John N Tsitsiklis.  _Neuro-Dynamic Programming_.  Athena Scientific, 1st edition, 1996.
  * Blei et al. [2017] David M Blei, Alp Kucukelbir, and Jon D McAuliffe.  Variational inference: A review for statisticians.  _Journal of the American statistical Association_ , 112(518):859–877, 2017.
  * Bloem-Reddy and Teh [2019] B. Bloem-Reddy and Y.W̃. Teh.  Probabilistic symmetry and invariant neural networks.  _Journal of Machine Learning Research_ , 2019.
  * Blundell et al. [2015] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra.  Weight uncertainty in neural network.  In _Proceedings of the 32nd International Conference on Machine Learning (ICML)_ , pages 1613–1622, 2015.
  * Borkar and Meyn [2000] Vivek S. Borkar and Sean P. Meyn.  The o.d.e. method for convergence of stochastic approximation and reinforcement learning.  _SIAM J. Control. Optim._ , 38:447–469, 2000.
  * Bousquet and Elisseeff [2002] Olivier Bousquet and André Elisseeff.  Stability and generalization.  _The Journal of Machine Learning Research_ , 2:499–526, 2002.
  * Boyan [1999] Justin A Boyan.  Least-squares temporal difference learning (icml).  In _ICML_ , pages 49–56. Citeseer, 1999.
  * Bradbury et al. [2018] 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\.
  * Bubeck and Sellke [2021] Sébastien Bubeck and Mark Sellke.  A universal law of robustness via isoperimetry.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Catoni [2007] Olivier Catoni.  _PAC-Bayesian supervised classification: the thermodynamics of statistical Learning (ICML)_.  Institute of Mathematical Statistics, 2007.
  * Chaudhari et al. [2017] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina.  Entropy-sgd: Biasing gradient descent into wide valleys.  _ICLR_ , 2017.
  * Chen et al. [2019] Shuxiao Chen, Edgar Dobriban, and Jane H Lee.  Invariance reduces variance: Understanding data augmentation in deep learning and beyond.  _arXiv preprint arXiv:1907.10905_ , 2019.
  * Chung et al. [2018] Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White.  Two-timescale networks for nonlinear value function approximation.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Cobbe et al. [2019] Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman.  Quantifying generalization in reinforcement learning.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1282–1289. PMLR, 09–15 Jun 2019.
  * Cobbe et al. [2020] Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman.  Leveraging procedural generation to benchmark reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 2048–2056. PMLR, 2020.
  * Cobbe et al. [2021] Karl W Cobbe, Jacob Hilton, Oleg Klimov, and John Schulman.  Phasic policy gradient.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 2020–2027. PMLR, 2021.
  * Cohen and Welling [2016] Taco S. Cohen and Max Welling.  Group equivariant convolutional networks.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning (ICML)_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 2990–2999. PMLR, 2016.
  * Cohen et al. [2019] Taco S Cohen, Mario Geiger, and Maurice Weiler.  A general theory of equivariant CNNs on homogeneous spaces.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Cubuk et al. [2019] Ekin Dogus Cubuk, Barret Zoph, Dandelion Mané, Vijay Vasudevan, and Quoc V. Le.  Autoaugment: Learning augmentation policies from data.  _Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Czarnecki et al. [2019] Wojciech M Czarnecki, Razvan Pascanu, Simon Osindero, Siddhant Jayakumar, Grzegorz Swirszcz, and Max Jaderberg.  Distilling policy distillation.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1331–1340. PMLR, 2019.
  * Dabney et al. [2018] Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos.  Distributional reinforcement learning with quantile regression.  In _AAAI Conference on Artificial Intelligence_ , 2018.
  * Dabney et al. [2021] Will Dabney, André Barreto, Mark Rowland, Robert Dadashi, John Quan, Marc G Bellemare, and David Silver.  The value-improvement path: Towards better representations for reinforcement learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 2021.
  * Damianou and Lawrence [2013] Andreas Damianou and Neil Lawrence.  Deep gaussian processes.  In _Proceedings of Machine Learning Research_ , volume 31, pages 207–215. PMLR, 2013.
  * Daneshmand et al. [2021] Hadi Daneshmand, Amir Joudaki, and Francis Bach.  Batch normalization orthogonalizes representations in deep random networks.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Dao et al. [2019] Tri Dao, Albert Gu, Alexander J Ratner, Virginia Smith, Christopher De Sa, and Christopher Ré.  A kernel theory of modern data augmentation.  _Proceedings of the 36th International Conference on Machine Learning, PMLR 97_ , 2019.
  * Daxberger et al. [2021] Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig.  Laplace redux-effortless bayesian deep learning.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Dayan [1993] Peter Dayan.  Improving generalization for temporal difference learning: The successor representation.  _Neural Computation_ , 5(4):613–624, 1993.
  * de Haan et al. [2019] Pim de Haan, Dinesh Jayaraman, and Sergey Levine.  Causal confusion in imitation learning.  _Advances in Neural Information Processing Systems_ , 2019.
  * De Palma et al. [2019] Giacomo De Palma, Bobak Kiani, and Seth Lloyd.  Random deep neural networks are biased towards simple functions.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Degrave et al. [2022] Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al.  Magnetic control of tokamak plasmas through deep reinforcement learning.  _Nature_ , 602(7897):414–419, 2022.
  * Dinh et al. [2017] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio.  Sharp minima can generalize for deep nets.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1019–1028. JMLR. org, 2017.
  * Dohare et al. [2021] Shibhansh Dohare, A Rupam Mahmood, and Richard S Sutton.  Continual backprop: Stochastic gradient descent with persistent randomness.  _arXiv preprint arXiv:2108.06325_ , 2021.
  * Dong et al. [2020] Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma.  On the expressivity of neural networks for deep reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 2627–2637. PMLR, 2020.
  * Dong and Yang [2020] Xuanyi Dong and Yi Yang.  Nas-bench-201: Extending the scope of reproducible neural architecture search.  In _International Conference on Learning Representations (ICLR)_ , 2020.  URL https://openreview.net/forum?id=HJxyZkBKDr.
  * Donini et al. [2018] Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil.  Empirical risk minimization under fairness constraints.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Du et al. [2019] Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Langford.  Provably efficient RL with rich observations via latent state decoding.  _International Conference on Machine Learning_ , pages 1665–1674, 2019.
  * Duchi et al. [2011] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(61):2121–2159, 2011.
  * Dutordoir et al. [2020] Vincent Dutordoir, Mark van der Wilk, Artem Artemev, and James Hensman.  Bayesian image classification with deep convolutional gaussian processes.  In _Proceedings of Machine Learning Research_ , volume 108, pages 1529–1539. PMLR, 2020.
  * Duvenaud et al. [2016] David Duvenaud, Dougal Maclaurin, and Ryan Adams.  Early stopping as nonparametric variational inference.  In _Artificial Intelligence and Statistics_ , pages 1070–1077, 2016\.
  * Dziugaite and Roy [2017] Gintare Karolina Dziugaite and Daniel M Roy.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  In _UAI_ , 2017.
  * Dziugaite and Roy [2018a] Gintare Karolina Dziugaite and Daniel M Roy.  Entropy-sgd optimizes the prior of a pac-bayes bound: Generalization properties of entropy-sgd and data-dependent priors.  _Proceedings of the 35th International Conference on Machine Learning, PMLR 80_ , pages :1377–1386, 2018a.
  * Dziugaite and Roy [2018b] Gintare Karolina Dziugaite and Daniel M Roy.  Data-dependent PAC-Bayes priors via differential privacy.  In _Advances in Neural Information Processing Systems 31_ , pages 8430–8441, 2018b.
  * Dziugaite et al. [2020] Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M Roy.  In search of robust measures of generalization.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Eberhardt and Scheines [2007] Frederick Eberhardt and Richard Scheines.  Interventions and causal inference.  _Philosophy of Science_ , 74(5):981–995, 2007\.  10.1086/525638.
  * Erhan et al. [2010] Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent.  Why does unsupervised pre-training help deep learning?  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pages 201–208. JMLR Workshop and Conference Proceedings, 2010.
  * Farahmand [2011] Amir-massoud Farahmand.  _Regularization in Reinforcement Learning_.  PhD Thesis, University of Alberta, 2011.
  * Farebrother et al. [2018] Jesse Farebrother, Marlos C Machado, and Michael Bowling.  Generalization and regularization in dqn.  _arXiv preprint arXiv:1810.00123_ , 2018.
  * Fawzi et al. [2016] Alhussein Fawzi, Horst Samulowitz, Deepak Turaga, and Pascal Frossard.  Adaptive data augmentation for image classification.  In _2016 IEEE International Conference on Image Processing (ICIP)_ , pages 3688–3692. Ieee, 2016.
  * Fedus et al. [2019a] William Fedus, Carles Gelada, Yoshua Bengio, Marc G Bellemare, and Hugo Larochelle.  Hyperbolic discounting and learning over multiple horizons.  In _Reinforcement Learning and Decision Making (RLDM)_ , 2019a.
  * Fedus et al. [2019b] William Fedus, Dibya Ghosh, John D Martin, Marc G Bellemare, Yoshua Bengio, and Hugo Larochelle.  On catastrophic interference in Atari 2600 games.  _Reinforcement Learning and Decision Making_ , 2019b.
  * Filos et al. [2021] Angelos Filos, Clare Lyle, Yarin Gal, Sergey Levine, Natasha Jaques, and Greg Farquhar.  Psiphi-learning: Reinforcement learning with demonstrations using successor features and inverse temporal difference learning.  _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , 2021.
  * Finn et al. [2017] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , pages 1126–1135. PMLR, 2017.
  * Fort and Scherlis [2019] Stanislav Fort and Adam Scherlis.  The goldilocks zone: Towards better understanding of neural network loss landscapes.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 3574–3581, 2019.
  * Fort et al. [2019] Stanislav Fort, Paweł Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan.  Stiffness: A new perspective on generalization in neural networks.  _arXiv preprint arXiv:1901.09491_ , 2019.
  * Fort et al. [2020] Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli.  Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Fortunato et al. [2018] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Remi Munos, Demis Hassabis, et al.  Noisy networks for exploration.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Frankle and Carbin [2019] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Frankle et al. [2020a] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin.  Linear mode connectivity and the lottery ticket hypothesis.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 3259–3269. PMLR, 13–18 Jul 2020a.
  * Frankle et al. [2020b] Jonathan Frankle, David J. Schwab, and Ari S. Morcos.  The early phase of neural network training.  In _International Conference on Learning Representations (ICLR)_ , 2020b.
  * Gal and Ghahramani [2016] Yarin Gal and Zoubin Ghahramani.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  _Proceedings of the 33rd International Conference on Machine Learning (ICML)_ , pages 1050–1059, 2016.
  * Gelada et al. [2019] Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Marc G. Bellemare.  DeepMDP: Learning continuous latent space models for representation learning.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2170–2179, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Germain et al. [2016a] Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien.  Pac-bayesian theory meets bayesian inference.  In _Advances in Neural Information Processing Systems_ , pages 1884–1892, 2016a.
  * Germain et al. [2016b] Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien.  PAC-Bayesian theory meets Bayesian inference.  In _Advances in Neural Information Processing Systems_ , pages 1884–1892, 2016b.
  * Ghiassian et al. [2020] Sina Ghiassian, Banafsheh Rafiee, Yat Long Lo, and Adam White.  Improving performance in reinforcement learning by breaking generalization in neural networks.  _arXiv preprint arXiv:2003.07417_ , 2020.
  * Ghosh and Bellemare [2020] Dibya Ghosh and Marc G Bellemare.  Representations for stable off-policy reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 2020.
  * Glorot and Bengio [2010] Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , pages 249–256. JMLR Workshop and Conference Proceedings, 2010.
  * Gogianu et al. [2021] Florin Gogianu, Tudor Berariu, Mihaela Rosca, Claudia Clopath, Lucian Busoniu, and Razvan Pascanu.  Spectral normalisation for deep reinforcement learning: an optimisation perspective.  _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , pages 3734–3744, 2021.
  * Golatkar et al. [2019] Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 2019.
  * Golub et al. [1976] Gene H Golub, Virginia C Klema, and Gilbert W Stewart.  Rank degeneracy and least squares problems, 1976.
  * Goyal et al. [2019] Anirudh Goyal, Riashat Islam, DJ Strouse, Zafarali Ahmed, Hugo Larochelle, Matthew Botvinick, Sergey Levine, and Yoshua Bengio.  Transfer and exploration via the information bottleneck.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Graves [2011] Alex Graves.  Practical variational inference for neural networks.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.
  * Gulcehre et al. [2022] Caglar Gulcehre, Srivatsan Srinivasan, Jakub Sygnowski, Georg Ostrovski, Mehrdad Farajtabar, Matt Hoffman, Razvan Pascanu, and Arnaud Doucet.  An empirical study of implicit regularization in deep offline rl.  _arXiv preprint arXiv:2207.02099_ , 2022.
  * Haar [1933] Alfred Haar.  Der massbegriff in der theorie der kontinuierlichen gruppen.  _Annals of mathematics_ , pages 147–169, 1933.
  * Haarnoja et al. [2018] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1861–1870, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Hanin and Rolnick [2019] Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Hansen and Wang [2021] Nicklas Hansen and Xiaolong Wang.  Generalization in reinforcement learning by soft data augmentation.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 13611–13617. IEEE, 2021.
  * Hardt et al. [2016] Moritz Hardt, Ben Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In _Proceedings of the 33rd International Conference on Machine Learning (ICML)_. PMLR, 2016.
  * Harvey et al. [2017] Nick Harvey, Christopher Liaw, and Abbas Mehrabian.  Nearly-tight VC-dimension bounds for piecewise linear neural networks.  In Satyen Kale and Ohad Shamir, editors, _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pages 1064–1068. PMLR, 07–10 Jul 2017.
  * He et al. [2020] Bobby He, Balaji Lakshminarayanan, and Yee Whye Teh.  Bayesian deep ensembles via the neural tangent kernel.  _Advances in Neural Information Processing Systems_ , 2020.
  * He and Su [2020] Hangfeng He and Weijie J Su.  The local elasticity of neural networks.  _International Conference on Learning Representations (ICLR)_ , 2020\.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE international conference on computer vision_ , pages 1026–1034, 2015.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hessel et al. [2018] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver.  Rainbow: Combining improvements in deep reinforcement learning.  In _AAAI conference on artificial intelligence_ , 2018.
  * Hinton and Van Camp [1993] Geoffrey E Hinton and Drew Van Camp.  Keeping the neural networks simple by minimizing the description length of the weights.  In _Proceedings of the sixth annual conference on Computational learning theory_ , pages 5–13, 1993.
  * Hochreiter and Schmidhuber [1997a] Sepp Hochreiter and Jürgen Schmidhuber.  Flat minima.  _Neural Computation_ , 9(1):1–42, 1997a.
  * Hochreiter and Schmidhuber [1997b] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997b.
  * Hoffer et al. [2017] Elad Hoffer, Itay Hubara, and Daniel Soudry.  Train longer, generalize better: closing the generalization gap in large batch training of neural networks.  In _Advances in Neural Information Processing Systems_ , pages 1731–1741, 2017.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Huber [1964] Peter J. Huber.  Robust estimation of a location parameter.  _The Annals of Mathematical Statistics_ , 35(1):73–101, 1964.  ISSN 00034851.
  * Igl et al. [2019] Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann.  Generalization in reinforcement learning with selective noise injection and information bottleneck.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Igl et al. [2021] Maximilian Igl, Gregory Farquhar, Jelena Luketina, Wendelin Boehmer, and Shimon Whiteson.  Transient non-stationarity and generalisation in deep reinforcement learning.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _Proceedings of the 32nd International Conference on Machine Learning (ICML)_ , pages 448–456. PMLR, 2015.
  * Iyyer et al. [2014] Mohit Iyyer, Jordan Boyd-Graber, Leonardo Claudino, Richard Socher, and Hal Daumé III.  A neural network for factoid question answering over paragraphs.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 633–644, October 2014.
  * Izmailov et al. [2018] P Izmailov, AG Wilson, D Podoprikhin, D Vetrov, and T Garipov.  Averaging weights leads to wider optima and better generalization.  In _34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018_ , pages 876–885, 2018.
  * Jaakkola et al. [1994] Tommi Jaakkola, Michael I. Jordan, and Satinder P Singh.  On the convergence of stochastic iterative dynamic programming algorithms.  _Neural Computation_ , 6(6), 1994.
  * Jacot et al. [2018] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In _Advances in neural information processing systems_ , pages 8571–8580, 2018.
  * Jaderberg et al. [2015] Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al.  Spatial transformer networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Jaderberg et al. [2017] Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu.  Reinforcement learning with unsupervised auxiliary tasks.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Jiang et al. [2021a] Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel.  Prioritized level replay.  In _International Conference on Machine Learning_ , pages 4940–4950. PMLR, 2021a.
  * Jiang et al. [2015] Nan Jiang, Alex Kulesza, and Satinder Singh.  Abstraction selection in model-based reinforcement learning.  In _Proceedings of the 32nd International Conference on Machine Learning (ICML)_ , 2015.
  * Jiang et al. [2021b] Ray Jiang, Tom Zahavy, Zhongwen Xu, Adam White, Matteo Hessel, Charles Blundell, and Hado Van Hasselt.  Emphatic algorithms for deep reinforcement learning.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 5023–5033. PMLR, 18–24 Jul 2021b.
  * Jiang et al. [2020] Yiding Jiang, Behnam Neyshabur, Dilip Krishnan, Hossein Mobahi, and Samy Bengio.  Fantastic generalization measures and where to find them.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Jin et al. [2020] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143. PMLR, 2020\.
  * Johansson et al. [2016] Fredrik Johansson, Uri Shalit, and David Sontag.  Learning representations for counterfactual inference.  In _Proceedings of the 33rd International Conference on Machine Learning (ICML)_ , pages 3020–3029, 2016.
  * Jong and Stone [2005] Nicholas K Jong and Peter Stone.  State abstraction discovery from irrelevant state variables.  In _IJCAI_ , volume 8, pages 752–757. Citeseer, 2005.
  * Kalimeris et al. [2019] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang.  Sgd on neural networks learns functions of increasing complexity.  _Advances in Neural Information Processing Systems_ , 32:3496–3506, 2019.
  * Kamath et al. [2021] Pritish Kamath, Akilesh Tangella, Danica Sutherland, and Nathan Srebro.  Does invariant risk minimization capture invariance?  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 4069–4077. PMLR, 13–15 Apr 2021.
  * Keskar et al. [2017] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  _ICLR_ , 2017.
  * Khan et al. [2019] Mohammad Emtiyaz E Khan, Alexander Immer, Ehsan Abedi, and Maciej Korzepa.  Approximate inference turns deep networks into gaussian processes.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 3094–3104. Curran Associates, Inc., 2019.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_ , 2015.
  * Kirk et al. [2021] Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel.  A survey of generalisation in deep reinforcement learning.  _arXiv preprint arXiv:2111.09794_ , 2021.
  * Kirkpatrick et al. [2017] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the National Academy of Sciences_ , 114(13):3521–3526, 2017.
  * Koehler et al. [2021] Frederic Koehler, Lijia Zhou, Danica Sutherland, and Nathan Srebro.  Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 20657–20668. Curran Associates, Inc., 2021.
  * Konda and Tsitsiklis [2000] Vijay R Konda and John N Tsitsiklis.  Actor-critic algorithms.  In _Advances in neural information processing systems_ , pages 1008–1014, 2000.
  * Kondor and Trivedi [2018] Risi Kondor and Shubhendu Trivedi.  On the generalization of equivariance and convolution in neural networks to the action of compact groups.  In _Proc. ICML 35_ , volume 80 of _PMLR_ , pages 2747–2755, 2018\.
  * Kossen et al. [2021] Jannik Kossen, Neil Band, Clare Lyle, Aidan N Gomez, Tom Rainforth, and Yarin Gal.  Self-attention between datapoints: Going beyond individual input-output pairs in deep learning.  _Advances in Neural Information Processing Systems_ , 2021.
  * Krogh and Hertz [1991] Anders Krogh and John Hertz.  A simple weight decay can improve generalization.  _Advances in neural information processing systems_ , 4, 1991.
  * Kullback and Leibler [1951] S. Kullback and R. A. Leibler.  On information and sufficiency.  _Ann. Math. Statist._ , 22(1):79–86, 03 1951\.  10.1214/aoms/1177729694.
  * Kumar et al. [2021] Aviral Kumar, Rishabh Agarwal, Dibya Ghosh, and Sergey Levine.  Implicit under-parameterization inhibits data-efficient deep reinforcement learning.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Kumar et al. [2022] Aviral Kumar, Rishabh Agarwal, Tengyu Ma, Aaron Courville, George Tucker, and Sergey Levine.  Dr3: Value-based deep reinforcement learning requires explicit regularization.  _Proceedings of the 39th International Conference on Machine Learning (ICML)_ , 2022.
  * Küttler et al. [2020] Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel.  The nethack learning environment.  _Advances in Neural Information Processing Systems_ , 33:7671–7684, 2020.
  * Lakshminarayanan et al. [2017] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In _Advances in neural information processing systems_ , pages 6402–6413, 2017.
  * Lan et al. [2022] Charline Le Lan, Stephen Tu, Adam Oberman, Rishabh Agarwal, and Marc G Bellemare.  On the generalization of representations in reinforcement learning.  _Artificial Intelligence and Statistics (AISTATS)_ , 2022.
  * Langford and Shawe-Taylor [2003] John Langford and John Shawe-Taylor.  Pac-bayes & margins.  _Advances in neural information processing systems_ , pages 439–446, 2003.
  * Laskin et al. [2020a] Michael Laskin, Aravind Srinivas, and Pieter Abbeel.  CURL: Contrastive unsupervised representations for reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 2020a.
  * Laskin et al. [2020b] Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas.  Reinforcement learning with augmented data.  _Advances in Neural Information Processing Systems_ , 33:19884–19895, 2020b.
  * Lee et al. [2018] Jaehoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri.  Deep neural networks as gaussian processes.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Lee et al. [2019] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  _Advances in neural information processing systems_ , 32, 2019.
  * Lee et al. [2020] Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein.  Finite versus infinite neural networks: an empirical study.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Lee et al. [2021] Kimin Lee, Laura M Smith, and Pieter Abbeel.  Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training.  In _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , pages 6152–6163. PMLR, 2021.
  * Lever et al. [2013] Guy Lever, François Laviolette, and John Shawe-Taylor.  Tighter PAC-Bayes bounds through distribution-dependent priors.  _Theoretical Computer Science_ , 473:4–28, 2013.
  * Levine et al. [2017] Nir Levine, Tom Zahavy, Daniel J Mankowitz, Aviv Tamar, and Shie Mannor.  Shallow updates for deep reinforcement learning.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Lewandowski [2020] Alex Lewandowski.  Generalization across space and time in reinforcement learning.  _NeurIPS Pre-Registration in Machine Learning Workshop_ , 2020.
  * Li and Pathak [2021] Alexander Li and Deepak Pathak.  Functional regularization for reinforcement learning via learned fourier features.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Li et al. [2018] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein.  Visualizing the loss landscape of neural nets.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 6391–6401, 2018.
  * Li et al. [2006] Lihong Li, Thomas J Walsh, and Michael L Littman.  Towards a unified theory of state abstraction for mdps.  In _ISAIM_ , 2006.
  * Li and Hoiem [2017] Zhizhong Li and Derek Hoiem.  Learning without forgetting.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(12):2935–2947, 2017.
  * Lin et al. [2019] Xingyu Lin, Harjatin Baweja, George Kantor, and David Held.  Adaptive auxiliary task weighting for reinforcement learning.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Liu et al. [2020a] Vincent Liu, Adam White, Hengshuai Yao, and Martha White.  Towards a practical measure of interference for reinforcement learning.  _arXiv preprint arXiv:2007.03807_ , 2020a.
  * Liu et al. [2020b] Vincent Liu, Adam M White, Hengshuai Yao, and Martha White.  Measuring and mitigating interference in reinforcement learning.  _arXiv preprint_ , 2020b.
  * Lo and Ghiassian [2019] Yat Long Lo and Sina Ghiassian.  Overcoming catastrophic interference in online reinforcement learning with dynamic self-organizing maps.  _arXiv preprint arXiv:1910.13213_ , 2019.
  * Lopez-Paz and Ranzato [2017] David Lopez-Paz and Marc’Aurelio Ranzato.  Gradient episodic memory for continual learning (icml).  In _Advances in Neural Information Processing Systems_ , 2017.
  * Louizos et al. [2017] Christos Louizos, Uri Shalit, Joris M Mooij, David Sontag, Richard Zemel, and Max Welling.  Causal effect inference with deep latent-variable models.  In _Advances in Neural Information Processing Systems_ , pages 6446–6456, 2017.
  * Lyle et al. [2019a] Clare Lyle, Marc G Bellemare, and Pablo Samuel Castro.  A comparative analysis of expected and distributional reinforcement learning.  In _AAAI Conference on Artificial Intelligence_ , 2019a.
  * Lyle et al. [2019b] Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy.  On the benefits of invariance in neural networks.  _NeurIPS Workshop on Machine Learning with Guarantees_ , 2019b.
  * Lyle et al. [2020] Clare Lyle, Lisa Schut, Robin Ru, Yarin Gal, and Mark van der Wilk.  A bayesian perspective on training speed and model selection.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Lyle et al. [2021a] Clare Lyle, Mark Rowland, Georg Ostrovski, and Will Dabney.  On the effect of auxiliary tasks on representation dynamics.  In _Artificial Intelligence and Statistics (AISTATS)_ , 2021a.
  * Lyle et al. [2021b] Clare Lyle, Amy Zhang, Minqi Jiang, Joelle Pineau, and Yarin Gal.  Resolving causal confusion in reinforcement learning via robust exploration.  In _Self-Supervision for Reinforcement Learning Workshop - ICLR 2021_ , 2021b.
  * Lyle et al. [2022a] Clare Lyle, Mark Rowland, and Will Dabney.  Understanding and preventing capacity loss in reinforcement learning.  In _International Conference on Learning Representations (Spotlight)_ , 2022a.
  * Lyle et al. [2022b] Clare Lyle, Mark Rowland, Will Dabney, Marta Kwiatkowska, and Yarin Gal.  Learning dynamics and generalization in reinforcement learning.  _Proceedings of the 39th International Conference on Machine Learning (ICML)_ , 2022b.
  * Machado et al. [2017] Marlos C. Machado, Marc G. Bellemare, and Michael Bowling.  A Laplacian framework for option discovery in reinforcement learning.  In Doina Precup and Yee Whye Teh, editors, _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 2295–2304. PMLR, 06–11 Aug 2017.
  * Machado et al. [2018a] Marlos C Machado, Marc G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling.  Revisiting the Arcade Learning Environment: Evaluation protocols and open problems for general agents.  _Journal of Artificial Intelligence Research_ , 61:523–562, 2018a.
  * Machado et al. [2018b] 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)_ , 2018b.
  * MacKay [1998] David J. C. MacKay.  Choice of basis for laplace approximation.  _Journal of Machine Learning_ , 33(1), 1998.
  * MacKay [1992] David JC MacKay.  _Bayesian methods for adaptive models_.  PhD thesis, California Institute of Technology, 1992.
  * MacKay [2003] David JC MacKay.  _Information theory, inference and learning algorithms_.  Cambridge university press, 2003.
  * Maddox et al. [2019] Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson.  A simple baseline for bayesian uncertainty in deep learning.  In _Advances in Neural Information Processing Systems_ , pages 13132–13143, 2019.
  * Maddox et al. [2020] Wesley J Maddox, Gregory Benton, and Andrew Gordon Wilson.  Rethinking parameter counting in deep models: Effective dimensionality revisited.  _arXiv preprint arXiv:2003.02139_ , 2020.
  * Magliacane et al. [2018] Sara Magliacane, Thijs van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij.  Domain adaptation by using causal inference to predict invariant conditional distributions.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 10846–10856. Curran Associates, Inc., 2018.
  * Mahadevan [2005] Sridhar Mahadevan.  Proto-value functions: Developmental reinforcement learning.  In _Proceedings of the 22nd International Conference on Machine Learning (ICML)_ , pages 553–560, 2005.
  * Mahadevan [2009] Sridhar Mahadevan.  Learning representation and control in Markov decision processes: New frontiers.  _Foundations and Trends® in Machine Learning (ICML)_ , 1(4):403–565, 2009.
  * Mahadevan and Maggioni [2007] 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_ , 8(Oct):2169–2231, 2007.
  * Mandt et al. [2017] Stephan Mandt, Matthew D Hoffman, and David M Blei.  Stochastic gradient descent as approximate bayesian inference.  _The Journal of Machine Learning Research_ , 18(1):4873–4907, 2017.
  * Matthews et al. [2017] Alexander G de G Matthews, Jiri Hron, Richard E Turner, and Zoubin Ghahramani.  Sample-then-optimize posterior sampling for bayesian linear models.  _Advances in Neural Information Processing Systems_ , 2017.
  * Matthews et al. [2018] Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani.  Gaussian process behaviour in wide deep neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * McAllester [1999] David A. McAllester.  Some PAC-Bayesian Theorems.  _Machine Learning (ICML)_ , 37(3):355–363, 1999\.
  * Mirowski et al. [2017] Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew J Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, Dharshan Kumaran, and Raia Hadsell.  Learning to navigate in complex environments.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Misra et al. [2020] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford.  Kinematic state abstraction and provably efficient rich-observation reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 6961–6971. PMLR, 2020.
  * Mnih et al. [2015] 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_ , 518(7540):529–533, 2015.
  * Morcos et al. [2018] Ari S. Morcos, David G.T. Barrett, Neil C. Rabinowitz, and Matthew Botvinick.  On the importance of single directions for generalization.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Nagarajan and Kolter [2019] Vaishnavh Nagarajan and J. Zico Kolter.  Uniform convergence may be unable to explain generalization in deep learning.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alche-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 11615–11626. Curran Associates, Inc., 2019.
  * Nakkiran et al. [2021] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.  Deep double descent: Where bigger models and more data hurt.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2021(12):124003, 2021.
  * Neal [2012] Radford M Neal.  _Bayesian learning for neural networks_ , volume 118.  Springer Science & Business Media, 2012.
  * Negrea et al. [2020] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy.  In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 7263–7272. PMLR, 2020.
  * Neyshabur et al. [2015a] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  In search of the real inductive bias: On the role of implicit regularization in deep learning.  _International Conference on Learning Representations (Workshop Track)_ , 2015a.
  * Neyshabur et al. [2015b] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  Norm-based capacity control in neural networks.  In _Conference on Learning (ICML) Theory_ , pages 1376–1401, 2015b.
  * Neyshabur et al. [2017] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro.  Exploring generalization in deep learning.  In _Advances in Neural Information Processing Systems_ , pages 5947–5956, 2017.
  * Neyshabur et al. [2019] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro.  The role of over-parametrization in generalization of neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Nikishin et al. [2022] Evgenii Nikishin, Max Schwarzer, Pierluca D’Oro, Pierre-Luc Bacon, and Aaron Courville.  The primacy bias in deep reinforcement learning.  In _Proceedings of the 39th International Conference on International Conference on Machine Learning (ICML)_ , 2022.
  * Osband et al. [2016] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy.  Deep exploration via bootstrapped DQN.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Osband et al. [2018] Ian Osband, John Aslanides, and Albin Cassirer.  Randomized prior functions for deep reinforcement learning.  In _Advances in Neural Information Processing Systems_ , pages 8617–8629, 2018.
  * Ostrovski et al. [2021] Georg Ostrovski, Pablo Samuel Castro, and Will Dabney.  The difficulty of passive learning in deep reinforcement learning.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Packer et al. [2018] Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song.  Assessing generalization in deep reinforcement learning.  _arXiv preprint_ , 2018.
  * Parker-Holder et al. [2022] Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel.  Evolving curricula with regret-based environment design.  _arXiv preprint arXiv:2203.01302_ , 2022.
  * Parr et al. [2008] Ronald Parr, Lihong Li, Gavin Taylor, Christopher Painter-Wakefield, and Michael L Littman.  An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning.  In _Proceedings of the 25th International Conference on Machine Learning (ICML)_ , 2008.
  * Pearl [2000] Judea Pearl.  _Causality: models, reasoning and inference_ , volume 29.  Springer, 2000.
  * Peters et al. [2016] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen.  Causal inference by using invariant prediction: identification and confidence intervals.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 78(5):947–1012, 2016.
  * Peters et al. [2017] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  _Elements of causal inference: foundations and learning algorithms_.  MIT press, 2017.
  * Pohlen et al. [2018] Tobias Pohlen, Bilal Piot, Todd Hester, Mohammad Gheshlaghi Azar, Dan Horgan, David Budden, Gabriel Barth-Maron, Hado Van Hasselt, John Quan, Mel Večerík, et al.  Observe and look further: Achieving consistent performance on atari.  _arXiv preprint arXiv:1805.11593_ , 2018.
  * Popper [1968] Karl R Popper.  _The logic of scientific discovery, Karl R. Popper_.  Hutchinson. London. GB, 1968.
  * Precup et al. [2001] Doina Precup, Richard S Sutton, and Sanjoy Dasgupta.  Off-policy temporal-difference learning with function approximation.  In _ICML_ , pages 417–424, 2001.
  * Puterman [1994] Martin L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  Wiley Series in Probability and Statistics. Wiley, 1994.  ISBN 978-0-47161977-2.  10.1002/9780470316887.
  * Qi et al. [2017] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  _Proc. Computer Vision and Pattern Recognition (CVPR), IEEE_ , pages 652–660, 2017.
  * Quan and Ostrovski [2020] John Quan and Georg Ostrovski.  DQN Zoo: Reference implementations of DQN-based agents, 2020.
  * Radford et al. [2018] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  _arXiv preprint_ , 2018.