summaries: This paper proposes a set of tools to probe spectral bias of deep neural networks, that is their tendency to learn low frequency, simpler functions earlier in training, whereas high frequencies are fit later. Authors propose adding noise to the labels through a target function via label smoothing, where the frequency and direction of the target function in image space can be varied. Moreover, they introduce a linear interpolation technique on validation data to probe the smoothness of the learned function along paths connecting natural images. Authors perform extensive experiments to demonstrate how the proposed tools can be used to investigate the spectral effect of training parameters such as model size and different forms of explicit and implicit regularization.

summaries: This work presents an empirical study of how different training aspects affect the spectral bias of neural networks in practice. To that end, the authors propose to inject label noise of different frequencies to the CIFAR10 dataset and suggest that the time a neural network takes to start overfitting this noise is a good metric of its spectral bias. They also propose to measure the variability of the loss landscape in the linear interpolation path between two images as proxy for spectral bias. Experiments on the effect of model architecture, explicit regularization, and data augmentation suggest that deep neural networks exhibit a strong spectral bias, in practice, which can be modulated by different design factors.

summaries: This paper proposes two methods for estimating smoothness of the prediction function learned by a deep network :   1/ an extension of Rahaman et al. to multiclass classification, by adding a sine of desired frequency to the target vector, then training on the new target vectors. The "effective noise fitting" is then the difference between the validation loss on clean targets and the validation loss on modified targets.  2/ a measure of change of the logits in l2 norm between 2 training examples, averaged over many examples  Using their methods, they show the effect on the smoothness of the predicted function of:  - varying the number of parameters  - adding explicit regularization (weight decay/mixup)  - distillation

summaries: The paper focuses on the spectral bias of neural networks, i.e., their tendency to learn first the low-frequency information. The goal of this work is to extend the spectral bias into practical image recognition networks, i.e., beyond the fully-connected nets and the NTK regime that it was previously studied. To that end, the paper conducts a number of studies in both explicit and implicit regularization schemes used in practice, and provides links for the success of model distillation.

abstractText: Despite their ability to represent highly expressive functions, deep learning models trained with SGD seem to find simple solutions that generalize surprisingly well. Spectral bias – the tendency of neural networks to prioritize learning low frequency functions – is one possible explanation for this phenomenon, but so far spectral bias has primarily been observed in theoretical models and simplified experiments. In this work, we propose methodologies for measuring spectral bias in modern image classification networks. We find that these networks indeed exhibit spectral bias, and that interventions that improve generalization sometimes increase and sometimes decrease the frequencies of the learned function. For example, we experimentally show that larger models learn high frequencies more readily than smaller ones, but many forms of regularization, both explicit and implicit, inhibit the learning of high frequencies. We also explore the connections between function frequency and image frequency and find that spectral bias is sensitive to the low frequencies prevalent in natural images. Our work enables measuring and ultimately influencing the spectral behavior of neural networks used for image classification, and is a step towards understanding why deep models generalize well.

authors:
Ronen Basri
David Jacobs
Yoni Kasten
Shira Kritchman

title: The convergence rate of neural networks for learned functions of different frequencies, 2019

authors:
Ronen Basri
Meirav Galun
Amnon Geifman
David Jacobs
Yoni Kasten
Shira Kritchman

title: Frequency bias in neural networks for input of non-uniform density, 2020

authors:
Mikhail Belkin
Siyuan Ma
Soumik Mandal

title: To understand deep learning we need to understand kernel learning

authors:
Zac Cranko
Simon Kornblith
Zhan Shi
Richard Nock

title: Lipschitz networks and distributional robustness, 2018

authors:
Ekin D. Cubuk
Barret Zoph
Dandelion Mane
Vijay Vasudevan
Quoc V. Le

title: Autoaugment: Learning augmentation policies from data, 2019a

authors:
Ekin D. Cubuk
Barret Zoph
Jonathon Shlens
Quoc V. Le

title: Randaugment: Practical automated data augmentation with a reduced search space, 2019b

title: The mnist database of handwritten digit images for machine learning research

venue: IEEE Signal Processing Magazine,

authors:
Suriya Gunasekar
Jason Lee
Daniel Soudry
Nathan Srebro

title: Implicit bias of gradient descent on linear convolutional networks, 2019

title: Characterizing implicit bias in terms of optimization geometry, 2020

authors:
Moritz Hardt
Benjamin Recht
Yoram Singer

title: Train faster, generalize better: Stability of stochastic gradient descent, 2016

authors:
Elad Hoffer
Itay Hubara
Daniel Soudry

title: Train longer, generalize better: closing the generalization gap in large batch training of neural networks, 2018

authors:
Jason Jo
Yoshua Bengio

title: Measuring the tendency of cnns to learn surface statistical regularities, 2017

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On large-batch training for deep learning: Generalization gap and sharp minima, 2017

authors:
Alex Krizhevsky
Vinod Nair
Geoffrey Hinton

title: Cifar-10 (canadian institute for advanced research)

venue: Globally-robust neural networks,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks, 2019

authors:
Horia Mania
John Miller
Ludwig Schmidt
Moritz Hardt
Benjamin Recht

title: Model similarity mitigates test set overuse, 2019

authors:
Hossein Mobahi
Mehrdad Farajtabar
Peter L. Bartlett

title: Self-distillation amplifies regularization in hilbert space, 2020

authors:
Preetum Nakkiran
Gal Kaplun
Dimitris Kalimeris
Tristan Yang
Benjamin L. Edelman
Fred Zhang
Boaz Barak

title: Sgd on neural networks learns functions of increasing complexity, 2019

authors:
Behnam Neyshabur
Ryota Tomioka
Nathan Srebro

title: In search of the real inductive bias: On the role of implicit regularization

venue: in deep learning,

authors:
Behnam Neyshabur
Srinadh Bhojanapalli
David McAllester
Nathan Srebro

title: Exploring generalization in deep learning, 2017

authors:
Behnam Neyshabur
Zhiyuan Li
Srinadh Bhojanapalli
Yann LeCun
Nathan Srebro

title: Towards understanding the role of over-parametrization in generalization of neural networks, 2018

authors:
Guillermo Ortiz-Jimenez
Apostolos Modas
Seyed-Mohsen Moosavi-Dezfooli
Pascal Frossard

title: Hold me tight! influence of discriminative features on deep network boundaries, 2020a

title: Neural anisotropy directions, 2020b

authors:
Samet Oymak
Zalan Fabian
Mingchen Li
Mahdi Soltanolkotabi

title: Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian, 2019

authors:
Nasim Rahaman
Aristide Baratin
Devansh Arpit
Felix Draxler
Min Lin
Fred A. Hamprecht
Yoshua Bengio
Aaron Courville

title: On the spectral bias of neural networks, 2019

authors:
Harshay Shah
Kaustav Tamuly
Aditi Raghunathan
Prateek Jain
Praneeth Netrapalli

title: The pitfalls of simplicity bias in neural networks, 2020

authors:
Daniel Soudry
Elad Hoffer
Mor Shpigel Nacson
Suriya Gunasekar
Nathan Srebro

title: The implicit bias of gradient descent on separable data, 2018

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jonathon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer

authors:
DJ Tolhurst
Y Tadmor
Tang Chao

title: Amplitude spectra of natural images

venue: Ophthalmic and Physiological Optics,

authors:
Ashia C Wilson
Rebecca Roelofs
Mitchell Stern
Nathan Srebro
Benjamin Recht

title: The marginal value of adaptive gradient methods in machine learning

venue: arXiv preprint arXiv:1705.08292,

authors:
Zhi-Qin John Xu
Yaoyu Zhang
Yanyang Xiao

title: Training behavior of deep neural network in frequency domain, 2019

authors:
Yoshihiro Yamada
Masakazu Iwamura
Takuya Akiba
Koichi Kise

title: Shakedrop regularization for deep residual learning

venue: IEEE Access,

authors:
Dong Yin
Raphael Gontijo Lopes
Jonathon Shlens
Ekin D. Cubuk
Justin Gilmer

title: A fourier perspective on model robustness in computer vision, 2020

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks, 2017

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization, 2017

authors:
Hongyi Zhang
Moustapha Cisse
Yann N. Dauphin
David Lopez-Paz

title: mixup: Beyond empirical risk minimization, 2018

authors:
Xiao Zhang
Haoyi Xiong
Dongrui Wu

title: Rethink the connections among generalization, memorization and the spectral bias of dnns

heading: 1 INTRODUCTION

text:
Two fundamental questions in machine learning are why overparameterized models generalize and how to make them more robust to distribution shift. Resolving both of these questions requires understanding how complex our models should be.
For instance, it is thought that overparameterized models generalize well because there are implicit regularizers that constrain the complexity of the learned functions. However, the precise nature of these implicit regularizers, and their importance in practice, remains unclear. As for how to achieve robustness, no consensus has emerged regarding function complexity. On the one hand, Cranko et al. (2018) and Leino et al. (2021) argue that Lipschitz smoothness of the learned function offers a guarantee of robustness; on the other, Shah et al. (2020) and Madry et al. (2019) argue that simplicity can be harmful and a robust model must actually be more complex than its non-robust counterpart.
One window into function complexity is spectral bias – the tendency of neural networks to learn low frequency (simple and smooth) functions early in training, gradually increasing the frequency (complexity) of the learned function as training proceeds. Foundational work in this area has shown theoretical evidence of spectral bias by analyzing convergence rates of neural networks towards functions of different frequencies and showing that they converge to low frequency functions at a faster rate (Basri et al., 2019; Rahaman et al., 2019).
In practice, spectral bias is difficult to measure: the most direct method involves taking a Fourier transform with respect to the input, which is expensive to compute due to the high dimensionality of images. Early experimental work focused on low-dimensional synthetic data (Basri et al., 2019; 2020) or used proxy measurements of spectral bias by inserting label noise of various frequencies during training (Rahaman et al., 2019). However, the label noise method is limited to binary classification/regression and involves modifying the training data, making it difficult to disentangle how other changes to the training data (such as data augmentation) affect the spectral content of the learned function. Thus, it remains an open question as to whether modern neural networks exhibit spectral bias and what role it plays in generalization.
In this work, we investigate model complexity through the lens of spectral bias, by introducing experimental methods to study the frequency decomposition of the functions learned by modern image classification networks. We find that neither simplicity nor complexity is purely beneficial or detrimental to performance.
Contributions. We extend the label noise procedure of Rahaman et al. (2019) to enable measuring spectral bias in multi-class classification and apply this technique to understand the function frequencies present in high-accuracy models on CIFAR-10 (Krizhevsky et al.). We also introduce a second method for measuring the smoothness of a learned function via linear interpolation between test examples. This offers a proxy measurement of spectral bias without the need to modify training labels, allowing us to probe the effects of the training data on the learned function frequencies.
Using these experimental methods, we find that increasing the model size decreases spectral bias; larger models learn high frequencies faster. However, we observe that more accurate models are not always higher frequency. Several forms of explicit and implicit regularization, including weight decay, increasing the dataset size, and applying Mixup (Zhang et al., 2018) data augmentation, increase spectral bias and produce a lower-frequency learned function. Our experiments show that these common training interventions affect the frequency content of the learned function in different ways, helping us to understand their mechanism and offering a tool to aid design of improved training methods in the future.
This perspective allows us to shed light on the mechanism behind self-distillation, in which a student model is trained to fit the predictions of a teacher model. Using our linear interpolation methodology, we observe that self-distillation produces a student model whose learned function is smoother than that of its teacher. This suggests that the teacher model acts as a sort of low-pass filter on the target function, perhaps making it more accessible to the spectrally-biased student.
Finally, we explore the relationship between image frequency and function frequency. By further extending the label noise methodology of Rahaman et al. (2019) to study spectral bias in directions of interest through the input space, we find that models are most sensitive to the low image frequencies common in natural images.

heading: 2 RELATED WORK

text:
Implicit bias. A common belief is that some form of implicit bias imposed by the training procedure may account for the generalization ability of overparameterized neural networks, and accordingly, much research has been directed towards understanding these implicit biases (Soudry et al., 2018; Zhang et al., 2017; Keskar et al., 2017; Gunasekar et al., 2019; 2020; Hardt et al., 2016; Hoffer et al., 2018; Belkin et al., 2018; Neyshabur et al., 2018; 2015; 2017; Mania et al., 2019; Gunasekar et al., 2019; Nakkiran et al., 2019). One of the most well-known forms of implicit bias comes from the optimization algorithm itself, which typically guides networks to solutions that generalize well (Soudry et al., 2018; Keskar et al., 2017; Wilson et al., 2017).
Spectral bias. Spectral bias is a form of implicit bias, with much recent attention including theoretical and experimental approaches (Oymak et al., 2019; Xu et al., 2019; Rahaman et al., 2019; Basri et al., 2019; Zhang et al., 2021); we describe some of these prior results here. Basri et al. (2019) studied spectral bias using a linear model of SGD training dynamics to show that models learn low frequency (simple) functions early in training and then gradually learn higher frequencies as training proceeds, assuming training data that is distributed uniformly on the hypersphere. Basri et al. (2020) extended the analysis to consider nonuniformly spaced training data, and found that learning is faster where samples are denser; if sampling is nonuniform, then during training, the learned function will be higher frequency in regions with denser samples.
Rahaman et al. (2019) used a more direct analysis to show the same spectral bias toward low frequency functions and also suggested that when training data lie on a manifold (as natural images are believed to), increasing the complexity of the manifold makes it easier for models to fit high frequency functions. Additionally, Rahaman et al. (2019) posited that high frequency components of the learned function are most sensitive to perturbations in the model parameters, connecting back to the idea of flat optimization minima (Neyshabur et al., 2017) or smooth loss landscape Mehmeti-Göpel et al. (2021). They proposed experimental methods to study spectral bias in image classification, but
focused on a binary subset of the relatively simple MNIST dataset (Deng, 2012), with mean square error loss.
Our label smoothing experiments are a direct extension of Rahaman et al. (2019) to multiclass classification with the more common cross-entropy loss. Our linear interpolation experiments are somewhat similar to the recently-proposed experimental methods in Zhang et al. (2021), except that we sample along paths between images rather than in regions surrounding each image; this allows for a more global measurement of spectral bias.
Model sensitivity to image frequency. While we focus on function frequency in this work, prior research aimed to understand model sensitivity to image frequencies. Jo & Bengio (2017) found that CNNs are sensitive to Fourier statistics of the training data, even those irrelevant to human viewers. Ortiz-Jimenez et al. (2020b) studied the image frequency bias induced by using a convolutional architecture, and Ortiz-Jimenez et al. (2020a) argued that models are sensitive primarily to discriminative Fourier directions in the training data. They posit that adversarial training induces large margins in orthogonal directions, thereby improving robustness. Yin et al. (2020) introduced a procedure to measure the sensitivity of trained models to Fourier image perturbations, and showed that adversarial training and Gaussian data augmentation increase robustness to high frequency perturbations but increase sensitivity to low frequency perturbations. Our work adds to this line of research a study of the interplay between two notions of frequency: the function frequency involved in spectral bias, and the image frequencies present in the data.

heading: 3 METHODOLOGY

text: The goal of our work is to measure the complexity of neural network functions through the lens of frequency. In low dimensions, measuring the frequency decomposition of a function is straightforward and tractable: evaluate the function at dense, uniform sampling positions and compute its discrete Fourier transform. However, the function of interest in image classification is unavoidably highdimensional, mapping images (with thousands of pixel values) to object classes. It would be intractable even to collect sufficient samples of this function to compute a discrete Fourier transform, let alone compute the transform itself. Instead, we employ two complementary approaches to measure informative proxies of this frequency decomposition.

heading: 3.1 LABEL SMOOTHING

text:
The core idea for measuring function frequency introduced by Rahaman et al. (2019) is to construct a sinusoid over the space of images, and to use that sinusoid as a form of label noise during training. Let D = {(Xi,yi)}ntraini=1 be the training examples and Dvalid = {(Xj ,yj)} nval j=1 be the validation examples, with Xi an image and yi a one-hot class encoding, where ntrain is the number of training examples, nval is the number of validation examples, d is the side length of an image (assumed to be square for simplicity), c is the number of color channels, and M is the number of classes, so Xi ∈ Rd×d×c and yi ∈ RM . To extend this procedure to the multi-class setting, we add noise of various frequencies to an M - dimensional label vector via label smoothing (Szegedy et al., 2015). Let S : Rd×d×c → [0, 1] be a target function that maps an input image Xi to a scalar value between 0 and 1. We apply label smoothing to each label yi, mapping it to ȳi = yi(1−S(Xi)) + 1M S(Xi) to retain a valid probability distribution. We then train from scratch using the original examples Xi and their smoothed labels ȳi. Finally, we evaluate on the validation images Xj , comparing to both their original one-hot labels yj and smoothed labels ȳj = yj(1− S(Xj)) + 1M S(Xj). Our experiments use the CIFAR-10 dataset (Krizhevsky et al.), where ntrain = 50000, nval = 10000, d = 32, c = 3, and M = 10; however, our experimental setup is sufficiently general as to transfer easily to any image classification task.
This method is introduced in Figure 1. As training proceeds, we see both the training loss (between predictions and smoothed labels ȳi) and noisy validation loss (between predictions and smoothed labels ȳj) decrease. The clean validation loss (between predictions and one-hot labels yj), however, initially decreases but at some point in training plateaus or begins to increase. At this point, the model has begun to learn the target function S. Accordingly, we introduce noise fitting, defined as the difference between the validation loss on one-hot labels and the validation loss on labels smoothed with the same function S that was applied to the training labels:
noise fitting = clean validation loss− noisy validation loss (1)
We compare different models by computing the minimum noise fitting achieved throughout training. A model with higher min noise fitting more readily fits the target function S than a model with lower min noise fitting.
By choosing different functions S, we can probe nuances of spectral bias. Typically (inspired by Rahaman et al. (2019)) we choose a radial wave: S(X) = sin(2πf(‖X‖ − ED‖X‖)), where we can vary the frequency f to understand spectral bias at this global scale. We can also choose more targeted functions S; for instance, if V is a direction of interest through the space of images (i.e. V is an image-shaped vector of unit norm), we can construct S(X) = sin(2πf 〈X,V〉). This allows us to vary both the frequency and direction of the target sinusoid, to understand model sensitivity along different directions through image space.
However, label smoothing has a few limitations. It requires retraining each model from scratch, with substantial investment of time and computational resources. Because it involves perturbing the training labels, it cannot directly answer questions about the interaction between the training dataset and spectral bias, such as the effects of data augmentation. For the same reason, we cannot use this methodology to study the spectral decomposition of existing trained models.

heading: 3.2 LINEAR INTERPOLATION

text:
To complement the label smoothing approach, we also propose a measurement methodology based on linear interpolation between validation images. Although we cannot take dense, regularly-spaced samples that cover the entire input (image) space, we can sample along specific paths through, and thereby glean glimpses into the spectral content of the learned function.
We consider two types of paths: those between images from the same class, and those between images from different classes. When considering paths between images in the same class, we choose 200 random, distinct pairs of images from each of the 10 CIFAR-10 classes and average over the paths defined by these pairs. When interpolating between classes, we choose 200 random, distinct image pairs from each of the 45 (10 choose 2) pairs of distinct classes, and average over the resulting paths.
For each pair of images (X0,X1), we vary λ ∈ [0, 1] to trace out a path, where each image in the path is given by Xλ = λX1 + (1− λ)X0. We choose λs so that the distance between adjacent images on the path is constant, which means that each path may produce a different number of samples depending on the total distance between X0 and X1. Before interpolating, we normalize X0 and X1. Figure 2 (Bottom Left) shows an illustrative example of two images and a corresponding interpolation path between them. For our experiments, we typically have 50 to 100 images along the interpolation path.
Relationship between interpolation and label smoothing experiments. In order to validate our interpolation methodology, we consider the oracle function that maps directly from the interpolated image Xλ to the target label used in our label smoothing experiments. By increasing the frequency of the label smoothing noise, we create oracle functions with higher frequencies. We then verify that our interpolation measurement indeed measures higher frequencies on the higher frequency oracle functions.
In Figure 2 (Left), we show an example where we vary the label smoothing frequency from f = 0 to f = 0.05. We plot the value of λ along the interpolating path on the x axis, and the norm of the difference between the model output on the interpolated image ŷλ and the model output on the original image ŷ0 on the y axis. The norm of the prediction difference allows us to visualize how smooth the function is along the interpolating path; smoother prediction difference norm indicates a lower frequency function.
In order to quantify the frequency of the function along the interpolating path, we compute the per-class discrete Fourier transform (DFT). Letting {Xλt}Tt=1 denote the set of interpolated images, the DFT coefficient for frequency f is given by Ŷf [m] = ∑T t=1 ŷλt [m] exp(−i2πft), where i is the imaginary number and m ∈ {1, . . . ,M} denotes the class. In order to determine how the magnitudes of the DFT coefficients Ŷf are distributed between low and high frequencies, we quantify how much of the spectrum is high frequency by choosing a frequency threshold and computing the fraction of the total coefficient magnitudes above the threshold. In Figure 2 (Right) we show this summary metric averaged over all within-class interpolating paths for the oracle functions.
Both sides of Figure 2 show that our interpolation methodology indeed measures the oracle functions that we constructed to be high frequency as high frequency. In Figure 2 (Left), the higher frequency oracle functions have less smooth prediction norm differences, and in Figure 2 (Right), they have a higher fraction of DFT coefficient magnitudes in the high frequencies.

heading: 3.3 DATA AND MODELS

text:
Our experiments use the CIFAR-10 (Krizhevsky et al.) dataset of low-resolution natural images from ten classes, a mixture of animals and objects. Images are pixel-wise normalized by the mean and standard deviation of the training images. We consider six different convolutional neural networks that have achieved high accuracy on this task: two wide-resnets (Zagoruyko & Komodakis, 2017) of different sizes (wrn 32 and wrn 160), three shake-shake regularized networks (Gastaldi, 2017) of different sizes (shake shake 32, shake shake 96, and shake shake 112), and pyramid net, which uses the even stronger shake-drop regularization (Yamada et al., 2019). Our implementations are based
on Cubuk et al. (2019a); we use the same optimizer (stochastic gradient descent with momentum) and cosine learning rate schedule. We train without data augmentation (to ensure all models are trained on exactly the same examples), except for experiments that explicitly vary data augmentation. Without data augmentation, the test accuracies of our models are: 89.4% (wrn 32), 90.2% (wrn 160), 92.2% (shake shake 32), 93.5% (shake shake 96), 93.6% (shake shake 112), and 95.8% (pyramid net).

heading: 4 RESULTS

text: Throughout this section we show representative examples from our experiments to highlight our main findings. Full results (on all six models we tested) are included in section A.

heading: 4.1 SPECTRAL BIAS AND MODEL ARCHITECTURE

text:
We begin by applying our label smoothing methodology to find that modern image classification CNNs exhibit spectral bias, learning low frequency target functions early in training and learning higher frequency functions as training proceeds. Note that Figure 3 (Left) shows spectral bias over a small but illustrative range of frequencies (the full range of frequencies we tested was 0 to 0.1); target functions of sufficiently low frequency are fit almost immediately and target functions of sufficiently high frequency are never learned during the 250 epochs of training we tested.
Although all models we tested exhibit spectral bias, we found that the precise nature of the bias depends on the choice of model. For example, with all else fixed, increasing the width of a model decreases its spectral bias, enabling it more readily fit target frequency functions. This trend is evident in Figure 3 for the wide-resnet family (Center) and the shake-shake family (Right). Results of our label smoothing experiment on all six models we tested are included in section A.2.

heading: 4.2 SENSITIVITY TO NATURAL IMAGE DIRECTIONS

text:
Although label smoothing with a radial wave offers a convenient global picture of spectral bias, by replacing the radial wave with other target functions we can use the same methodology to test more localized aspects of spectral bias. We take a step in this direction by considering the family of target label smoothing functions S(X; k) = sin(2πf 〈X,Fk〉), where Fk is a diagonal Fourier basis image with frequency k and the same dimensions as X, visualized in Figure 4 (Bottom).
We consider (a subset of) Fourier basis images because the Fourier spectra statistics of natural images are well studied (see, e.g. Tolhurst et al. (1992)): natural images tend to be composed of Fourier basis images with amplitude proportional to their inverse spatial frequency. Indeed, in Figure 4 we find that shake shake 96 is more sensitive to label smoothing in low image frequency directions.
This finding is consistent with theoretical predictions of Basri et al. (2020) that models learn faster in regions of higher density of training examples: since low image frequencies are more common
in natural images, the effective sampling density enjoyed by a label smoothing target is higher in these directions. It is also possible that this bias is inherent to the convolutional model architecture regardless of the data distribution, as discussed in Ortiz-Jimenez et al. (2020b), or that a combination of both effects is at play. Determining the precise cause of this image frequency finding is an interesting direction for further study.

heading: 4.3 SPECTRAL BIAS AND REGULARIZATION

text:
We also found a relationship between regularization and spectral bias, which is explored in Figure 5 and Figure 6. Some forms of regularization, like weight decay and dropout, are amenable to study by either of our methodologies; Figure 5 demonstrates agreement between these methods in the context of varying weight decay. Further results showing agreement between these two measurement methodologies are presented in section A.4.
In total we consider 4 types of (explicit and implicit) regularization: weight decay, training set size, data augmentation (Cubuk et al., 2019b;a; Zhang et al., 2018), and the strength of Mixup augmentation (Zhang et al., 2018). The latter three involve changes to the training data and are therefore only directly studied via our interpolation methodology, which we use in Figure 6.
Weight Decay. Weight decay is a penalty on the square norm of the model parameters; a stronger penalty encourages a model to learn smaller-norm weights. Figure 5 shows that increasing the weight decay also encourages a model to learn high frequencies slower (Left) and to ultimately be lower-frequency (Right). This result is consistent with the expectation that smaller-norm weights yield a learned function with a smaller Lipschitz constant and thus smoother changes in output (as discussed e.g. in Szegedy et al. (2014)). This experiment also demonstrates the nuanced relationship between the bandwidth or smoothness of the learned function and its accuracy; shake shake 32 trained with weight decay 0.0005 or 0.001 achieves higher test accuracy compared to the same architecture trained with either more or less weight decay. Neither complexity nor smoothness is, in itself, purely beneficial or detrimental: the trick is to balance them appropriately for the dataset.
Training Set Size. As shown in Figure 6 (Left) on wrn 160, we find that increasing the number of training examples produces a lower-frequency learned function. Note that all models in Figure 6 (Left) were trained for the same number of epochs and with the same batch size, so the models trained with more examples were also trained for more gradient steps (since each epoch contained more batches). The models trained with more examples therefore had ample opportunity to fit the high frequencies present in their counterparts trained with fewer examples, and yet did not. This result supports the idea that additional examples serve as an implicit regularization by forcing the model away from more complex solutions that would predict the added examples incorrectly.
Data Augmentation. Data augmentation is a common strategy to increase the effective training set size without the expense of actually collecting additional examples. In Figure 6 (Center) we consider the effects of RandAugment (Cubuk et al., 2019b), AutoAugment (Cubuk et al., 2019a), and Mixup (Zhang et al., 2018) data augmentation strategies, each of which tends to improve the final accuracy of the trained model (with RandAugment producing the most substantial benefits in our experiments). RandAugment and AutoAugment generate new images by applying geometric and lighting transformations, whereas Mixup produces new images by linearly interpolating between pairs of existing images. We find that training with RandAugment or AutoAugment tends to make the learned function slightly less smooth between examples of the same class (Top). Mixup (at strength 0.1) makes the learned function substantially smoother, both within-class (Top) and between-class (Bottom). This experiment reinforces the nuanced relationship between function complexity and performance; a model can be improved by the addition of helpful complexity (as in RandAugment and AutoAugment, which encode robust transformation priors) or by the removal of unnecessary complexity (as in Mixup, which encodes a simple linear prior in unsupervised input regions).
Mixup Strength. Mixup augmentation (Zhang et al., 2018) perturbs each batch of training data as follows: each example is matched with a partner based on a random permutation of the batch, and each example is then perturbed towards its partner by an interpolation amount λ drawn from a symmetric beta distribution (with the same λ used for all examples in the batch). We refer to the parameter of this beta distribution as the Mixup strength, as it controls the degree to which the augmented images tend to lie close to an original training image or close to the average of two training images. A parameter
of 0 corresponds to no augmentation (λ = 0 or λ = 1, always using the original images), a parameter of 1 corresponds to the uniform distribution over λ ∈ [0, 1], and a parameter of ∞ corresponds to λ = 0.5, the exact midpoint between a pair of training images. Figure 6 (Center) uses Mixup strength 0.1 (one of the values recommended by Zhang et al. (2018)). Figure 6 (Right) shows that, as expected, increasing the strength of the Mixup augmentation generally makes the learned function lower-frequency, but that Mixup that is too strong can yield high frequencies. Interestingly, the impact of Mixup strength on the learned frequencies is different within versus between classes, suggesting that perhaps tuning this parameter separately for these two cases may prove beneficial.

heading: 4.4 SELF-DISTILLATION

text:
In a sense another form of regularization, we finally consider the effect of self-distillation on the smoothness of the learned function. In self-distillation, a ‘teacher’ model is trained with some form of strong regularization, in our case a combination of weight decay and early stopping based on training loss. A ‘student’ model with the same architecture is then trained from scratch to fit the pseudolabels produced by the teacher, instead of the original one-hot training labels (alternatively, an interpolation between the pseudolabels and the original labels may be used). Prior research (Furlanello et al., 2018) found that this procedure can train student models that outperform both their teachers and a baseline (the same architecture trained to completion on the one-hot labels).
Prior research has also sought to understand the mechanism behind knowledge distillation and self-distillation in particular. Mobahi et al. (2020) finds that self-distillation acts as a regularizer by limiting the basis functions available to the student to learn. We complement their theoretical work with our interpolation experimental methodology in Figure 7, where indeed we find that the student model learns a lowerfrequency function than its teacher, when both have the same training loss. We conjecture that this effect is analogous to low-pass prefiltering common in digital signal processing: a highfrequency target function that we cannot adequately sample is first smoothed (in this case by being approximated by a regularized teacher) and then it can be modeled via samples without further loss in fidelity. Without this prefiltering, our samples are inadequate to capture the complexity of the target function, so we reconstruct an imperfect version corrupted by aliasing.

heading: 5 CONCLUSIONS

text:
In this paper, we introduced two methods to measure spectral bias in modern image classification neural networks, and applied these methods towards the central question:
What kinds of function frequencies are needed for modern neural networks to generalize?
Specifically, we applied these methods to examine the impact of a variety of training choices on the learned frequencies. Among training choices that improve validation accuracy, using a larger model, training longer, and using RandAugment (Cubuk et al., 2019b) or AutoAugment (Cubuk et al., 2019a) tend to increase the frequency of the learned function. However, regularizing with modest weight decay, training with more examples, using modest Mixup augmentation (Zhang et al., 2018), and performing self-distillation all improve validation accuracy while decreasing the frequency of the learned function. Our findings support the common wisdom that, while some complexity is necessary to fit the data, unnecessary complexity can harm generalization. Our experimental methods offer a valuable window into precisely what kind of function complexity we should strive for.

heading: REPRODUCIBILITY STATEMENT

text: An anonymized copy of our code is included in the supplement. Our work uses the publicly-available CIFAR-10 dataset (Krizhevsky et al.).

heading: ETHICS STATEMENT

text:
Since our work is foundational rather than applied in nature, we do not anticipate any direct ethical concerns. However, as with any foundational research in machine learning, our work has the potential to improve the performance and controllability of machine learning models, particularly in the domain of image classification. These improvements in turn may find use in ethical (e.g. medical diagnostics, autonomous vehicles) or ethically questionable (e.g. surveillance) applications.
As for direct ethical impacts of our work, we acknowledge the energy costs of training and evaluating the models used in our experiments. One of our key contributions is proposing a method (via linear interpolation) to measure the frequency content of a learned function without retraining, which should enable future experimental research in spectral bias to be less energy-intensive.

heading: A APPENDIX

heading: A.1 LINEAR INTERPOLATION: METHODOLOGICAL DETAILS

text: For each sampled path, we compute the discrete Fourier transform (DFT) of the prediction function separately for each of the M class predictions, take the (real) magnitude of the resulting (complex) DFT coefficients, and average them among the M classes. We then average these coefficient magnitudes among the many paths (all within-class paths and, separately, all between-class paths) and compute the fraction of this averaged DFT magnitude that is allocated to the high frequency components. We use a simple threshold that considers the lowest 10% of frequency components (i.e. frequencies between 0 and 0.05) “low” and the remaining (between 0.05 and 0.5) “high”, but qualitatively our results are not sensitive to this particular threshold. The highest frequency we can measure is 0.5, the Nyquist rate corresponding to our sampling distance of 1; if a particular maximum frequency is desired for measurement all that must be changed to achieve it is the sampling distance along the interpolating paths.

heading: A.2 LABEL SMOOTHING

text: A.3 SENSITIVITY TO NATURAL IMAGE DIRECTIONS

heading: A.4 AGREEMENT BETWEEN LABEL SMOOTHING AND LINEAR INTERPOLATION

text:
A.4.1 VARYING THE FREQUENCY OF THE RADIAL WAVE LABEL SMOOTHING
When the frequency of the radial wave used for label smoothing increases, models take more time to fit the smoothing noise. Figure 3 (Left) and Figure 8 show this using label smoothing; the corresponding interpolation experiment is shown in Figure 10. The target frequencies between 0.035 and 0.04 are close enough that, were the model to fit each perfectly, the interpolation curves would be nearly visually indistinguishable, as we can tell from Figure 2 (Left). However, the model is actually smoother when trying to fit higher frequency label smoothing noise, because it fits this noise less well (in addition to fitting it later in training). We can see this effect, for instance, by noting that wrn 32, wrn 160, and shake shake 32 fail to fit frequency 0.04, both in Figure 8 and Figure 10.
It is also worth noting that, in Figure 10 and repeatedly across our interpolation experiments, the learned function is smoother (lower-frequency) within-class and less smooth (higher-frequency) between-class. This is to be expected since the model must change predictions somewhere along the path between examples from different classes.

heading: A.4.2 LEARNING LOW FREQUENCIES FIRST

text:
The label smoothing experiment presented in Figure 3 (Left) and Figure 8 shows that low frequency target functions are learned earlier than higher frequency targets; we can also confirm this finding
using interpolation with model checkpoints saved at different epochs throughout training (without any label smoothing). We see that indeed in the early stages of training low frequencies predominate, with higher frequencies entering as training proceeds. Surprisingly, we also see that towards the end of training low frequencies again predominate; the reason for this is an interesting question for further research.

heading: A.4.3 WEIGHT DECAY

text:
Figure 5 shows on shake shake 32 via both label noise and linear interpolation that increasing the weight decay results in a smoother (lower frequency) learned function. Figure 12 shows the same result across all six models we tested.
(a) shake shake 32 (b) shake shake 96 (c) shake shake 112
(d) wrn 32 (e) wrn 160 (f) pyramid net
(A) Radial wave label smoothing
(b) shake shake 32 (c) shake shake 96 (d) shake shake 112
(e) wrn 32 (f) wrn 160 (g) pyramid net
(B) Min noise fitting summaries of label smoothing. Note that for pyramid net, min noise fitting does not fully capture the results of noise fitting; the “dips” are clearly separated across epochs, with higher weight decay inducing delayed dips, even if they achieve similar minimum noise fitting values.

heading: A.5 TRAINING SET SIZE

text: Figure 6 (Left) shows the regularization (frequency reduction) effect of increasing dataset size for wrn 160. Figure 13 shows the same effect on all six models we tested.

heading: A.6 DATA AUGMENTATION

text: Figure 6 (Center) uses linear interpolation to study the effect of common data augmentation procedures on the learned frequencies for wrn 160. Figure 14 shows the same experiment on all six models we tested.

heading: A.6.1 MIXUP STRENGTH

text: Figure 6 (Right) uses linear interpolation to show that training with Mixup data augmentation (Zhang et al., 2018) causes wrn 160 to learn a lower-frequency function, but too much Mixup can produce a higher-frequency function. Figure 15 repeats the experiment on all six models we tested.

heading: A.7 SELF-DISTILLATION

text: Figure 7 uses linear interpolation to show that self-distillation with shake shake 96 produces a student model that is lower-frequency than its teacher, even though both are trained to the same training loss and the student has higher validation accuracy than the teacher. Figure 16 shows the same result across all six models we tested.


summaries: This paper proposes a mode-switching strategy for the exploration/exploitation dilemma instead of monolithic behaviour policies in order to obtain more diverse behaviour. Different granularities for the timing of the switches as well as different switching mechanisms are investigated (blind vs. informed switching). The focus for exploration is not on how, but when. For exploration, they both use Random Network Distillation (RND) as well as a uniform policy. Their experiments are conducted on the Atari Learning Environment (ALE), where they provide performance and diversity results.

summaries: This paper proposes to study exploration at different levels of granularity. Current methods either explore at the level of individual steps (e.g., \epsilon-greedy), or at the level of experiments (e.g. first a reward-free exploration phase, followed by a task-dependent learning phase using the gathered data). This paper proposes to study exploration at the intra-episodic level, i.e. where the agent switches between exploration and exploitation within the same episode.   They discuss various design choices to perform exploration at this level, for example switching after a certain number of steps or with a certain probability, or switching based on the discrepancy between the predicted value and actual experienced value.   The experimental results show that including intra-episodic exploration gives a modest benefit over other exploration schemes when using an R2D2 base agent. Other insights are also included, which show that the proportion of exploration does change throughout the learning process, indicating that different degrees of exploration are useful at different stages. They also show that the informed switching component learns switching behaviors which are non-uniform throughout the episodes.

summaries: This paper studies switching between exploit and explore modes in reinforcement learning. It discusses switching mechanisms based on time ("blind switching") and based on state ("informed switching"). Studying seven Atari games, an empirical analysis of different switching mechanisms is performed.

summaries: This paper investigates when to switch between exploitation and exploration and how long to stay in each exploration mode during RL learning. It proposes new ways to explore the subject, especially with intra-episodic exploration variants. It presents a large body of study results (10 pages of appendices!!), and concludes with very thought-provoking suggestions and discussions.

abstractText: Exploration remains a central challenge for reinforcement learning (RL). Virtually all existing methods share the feature of a monolithic behaviour policy that changes only gradually (at best). In contrast, the exploratory behaviours of animals and humans exhibit a rich diversity, namely including forms of switching between modes. This paper presents an initial study of mode-switching, nonmonolithic exploration for RL. We investigate different modes to switch between, at what timescales it makes sense to switch, and what signals make for good switching triggers. We also propose practical algorithmic components that make the switching mechanism adaptive and robust, which enables flexibility without an accompanying hyper-parameter-tuning burden. Finally, we report a promising and detailed analysis on Atari, using two-mode exploration and switching at sub-episodic time-scales.

authors:
M.A. Addicott
J.M. Pearson
M.M. Sweitzer
D.L. Barack
M.L. Platt

title: A Primer on Foraging and the Explore/Exploit Trade-Off for Psychiatry

venue: Research. Neuropsychopharmacology,

authors:
Adrià Puigdomènech Badia
Pablo Sprechmann
Alex Vitvitskyi
Daniel Guo
Bilal Piot
Steven Kapturowski
Olivier Tieleman
Martı́n Arjovsky
Alexander Pritzel
Andew Bolt
Charles Blundell

title: Never give up: Learning directed exploration strategies, 2020b

authors:
Louis Bagot
Kevin Mets
Steven Latré

title: Learning intrinsically motivated options to stimulate policy exploration, 2020

authors:
Marc G Bellemare
Yavar Naddaf
Joel Veness
Michael Bowling

title: The arcade learning environment: An evaluation platform for general agents

venue: Journal of Artificial Intelligence Research,

authors:
Marc G Bellemare
Sriram Srinivasan
Georg Ostrovski
Tom Schaul
David Saxton
Rémi Munos

title: Unifying count-based exploration and intrinsic motivation

venue: In Neural Information Processing Systems,

authors:
Nicolas Bougie
Ryutaro Ichise

title: Fast and slow curiosity for high-level exploration in reinforcement learning

venue: Applied Intelligence,

authors:
James Bradbury
Roy Frostig
Peter Hawkins
Matthew James Johnson
Chris Leary
Dougal Maclaurin
George Necula
Adam Paszke
Jake VanderPlas
Skye Wanderman-Milne
Qiao Zhang

title: JAX: composable transformations of Python+NumPy programs, 2018

venue: URL http: //github.com/google/jax

authors:
Jacob Buckman
Danijar Hafner
George Tucker
Eugene Brevdo
Honglak Lee

title: Sampleefficient reinforcement learning with stochastic ensemble value expansion

venue: arXiv preprint arXiv:1807.01675,

authors:
David Budden
Matteo Hessel
Iurii Kemaev
Stephen Spencer
Fabio Viola

title: Chex: Testing made fun, in jax!, 2020a. URL http://github.com/deepmind/chex

authors:
David Budden
Matteo Hessel
John Quan
Steven Kapturowski
Kate Baumli
Surya Bhupatiraju
Aurelia Guy
Michael King

title: RLax: Reinforcement Learning in JAX, 2020b. URL http: //github.com/deepmind/rlax

authors:
Yuri Burda
Harrison Edwards
Amos J. Storkey
Oleg Klimov

title: Exploration by random network distillation

authors:
Vı́ctor Campos
Pablo Sprechmann
Steven Hansen
Andre Barreto
Steven Kapturowski
Alex Vitvitskyi
Adrià Puigdomènech Badia
Charles Blundell

title: Coverage as a principle for discovering transferable behavior in reinforcement learning

venue: arXiv preprint arXiv:2102.13515,

authors:
Olivier Cappé
Aurélien Garivier
Odalric-Ambrym Maillard
Rémi Munos
Gilles Stoltz

title: Kullback–leibler upper confidence bounds for optimal sequential allocation

venue: Annals of Statistics,

authors:
Albin Cassirer
Gabriel Barth-Maron
Thibault Sottiaux
Manuel Kroiss
Eugene Brevdo

title: Reverb: An efficient data storage and transport system for ml research, 2020

venue: URL https: //github.com/deepmind/reverb

authors:
Flurin Cathomas
Federica Klaus
Karoline Guetter
Hui-Kuan Chung
Anjali Raja Beharelle
Tobias R. Spiller
Rebecca Schlegel
Erich Seifritz
Matthias N. Hartmann-Riemer
Philippe N. Tobler
Stefan Kaiser

title: Increased random exploration in schizophrenia is associated with inflammation

venue: npj Schizophrenia,

authors:
K. Chakroun
D. Mathar
A. Wiehler
F. Ganzer
J. Peters

title: Dopaminergic modulation of the exploration/exploitation trade-off in human decision-making

venue: Elife, 9,

authors:
David Churchill
Michael Buro

title: Build order optimization in starcraft

venue: In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,

authors:
Jonathan D Cohen
Samuel M McClure
Angela J Yu

title: Should I stay or should I go? How the human brain manages the trade-off between exploitation and exploration

venue: Philosophical Transactions of the Royal Society B: Biological Sciences,

authors:
Vincent D. Costa
Andrew R. Mitz
Bruno B. Averbeck

title: Subcortical substrates of explore-exploit decisions in primates

authors:
Esther Derman
Daniel Mankowitz
Timothy Mann
Shie Mannor

title: A bayesian approach to robust reinforcement learning

venue: In Uncertainty in Artificial Intelligence,

authors:
Jonathan Downar
Adrian P Crawley
David J Mikulis
Karen D Davis

title: A cortical network sensitive to stimulus salience in a neutral behavioral context across multiple sensory modalities

venue: Journal of neurophysiology,

authors:
R. Becket Ebitz
Brianna J. Sleezer
Hank P. Jedema
Charles W. Bradberry
Benjamin Y. Hayden

title: Tonic exploration governs both flexibility and lapses

venue: PLOS Computational Biology,

authors:
Adrien Ecoffet
Joost Huizinga
Joel Lehman
Kenneth O. Stanley
Jeff Clune

title: Go-explore: a new approach for hard-exploration problems, 2021

authors:
Sebastian Flennerhag
Jane X Wang
Pablo Sprechmann
Francesco Visin
Alexandre Galashov
Steven Kapturowski
Diana L Borsa
Nicolas Heess
Andre Barreto
Razvan Pascanu

title: Temporal difference uncertainties as a signal for exploration

venue: arXiv preprint arXiv:2010.02255,

title: Deconstructing the human algorithms for exploration

venue: Cognition, 173:34–42,

authors:
Samuel J. Gershman
Bastian Greshake Tzovaras

title: Dopaminergic genes are associated with both directed and random exploration

venue: bioRxiv,

authors:
Karol Gregor
Danilo Jimenez Rezende
Daan Wierstra

title: Variational intrinsic control

venue: arXiv preprint arXiv:1611.07507,

authors:
Tom Hennigan
Trevor Cai
Tamara Norman
Igor

title: Babuschkin. Haiku: Sonnet for JAX, 2020

venue: URL http://github.com/deepmind/dm-haiku

authors:
Matteo Hessel
David Budden
Fabio Viola
Mihaela Rosca
Eren Sezener
Tom Hennigan

title: Optax: Composable gradient transformation and optimisation, in JAX!, 2020

venue: URL http:// github.com/deepmind/optax

authors:
T.T. Hills
P.M. Todd
D. Lazer
A.D. Redish
I.D. Couzin

title: Exploration versus exploitation in space, mind, and society

venue: Trends Cogn Sci,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Dan Horgan
John Quan
David Budden
Gabriel Barth-Maron
Matteo Hessel
Hado Van Hasselt
David Silver

title: Distributed prioritized experience replay

venue: arXiv preprint arXiv:1803.00933,

authors:
Rein Houthooft
Xi Chen
Yan Duan
John Schulman
Filip De Turck
Pieter Abbeel

title: Vime: Variational information maximizing exploration

venue: arXiv preprint arXiv:1605.09674,

authors:
Max Jaderberg
Volodymyr Mnih
Wojciech Marian Czarnecki
Tom Schaul
Joel Z Leibo
David Silver
Koray Kavukcuoglu

title: Reinforcement learning with unsupervised auxiliary tasks

venue: arXiv preprint arXiv:1611.05397,

authors:
Thomas Jaksch
Ronald Ortner
Peter Auer

title: Near-optimal regret bounds for reinforcement learning

venue: Journal of Machine Learning Research,

authors:
Yuu Jinnai
Jee Won Park
David Abel
George Konidaris

title: Discovering options for exploration by minimizing cover time

venue: In International Conference on Machine Learning,

authors:
Yuu Jinnai
Jee Won Park
Marlos C Machado
George Konidaris

title: Exploration in reinforcement learning with deep covering options

venue: In International Conference on Learning Representations,

authors:
Steven Kapturowski
Georg Ostrovski
Will Dabney
John Quan
Remi Munos

title: Recurrent experience replay in distributed reinforcement learning

authors:
J.M. Kembro
M. Lihoreau
J. Garriga
E.P. Raposo
F. Bartumeus

title: Bumblebees learn foraging routes through exploitation-exploration cycles

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Alexander S Klyubin
Daniel Polani
Chrystopher L Nehaniv

title: Empowerment: A universal agentcentric measure of control

venue: IEEE Congress on Evolutionary Computation,

authors:
Tor Lattimore
Csaba Szepesvári

title: Bandit algorithms

authors:
Cam Linke
Nadia M. Ady
Martha White
Thomas Degris
Adam White

title: Adapting behaviour via intrinsic reward: A survey and empirical study, 2019

authors:
Marlos C Machado
Marc G Bellemare
Erik Talvitie
Joel Veness
Matthew Hausknecht
Michael Bowling

title: Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents

authors:
Daniel J Mankowitz
Timothy Arthur Mann
Shie Mannor

title: Adaptive skills adaptive partitions (ASAP)

authors:
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
Demis Hassabis

title: Human-level control through deep reinforcement learning

authors:
Ted Moskovitz
Jack Parker-Holder
Aldo Pacchiano
Michael Arbel

title: Deep reinforcement learning with dynamic optimism

venue: arXiv preprint arXiv:2102.03765,

authors:
Georg Ostrovski
Marc G. Bellemare
Aäron van den Oord
Rémi Munos

title: Count-based exploration with neural density models

authors:
Pierre-Yves Oudeyer
Frederic Kaplan

title: What is intrinsic motivation? a typology of computational approaches

venue: Frontiers in neurorobotics,

title: Play and exploration in children and animals

authors:
Tom Schaul
John Quan
Ioannis Antonoglou
David Silver

title: Prioritized experience replay

authors:
Tom Schaul
Diana Borsa
David Ding
David Szepesvari
Georg Ostrovski
Will Dabney
Simon Osindero

title: Adapting behaviour for learning progress, 2019

authors:
Tom Schaul
Georg Ostrovski
Iurii Kemaev
Diana Borsa

title: Return-based scaling: Yet another normalisation trick for deep RL

venue: arXiv preprint arXiv:2105.05347,

title: Curious model-building control systems

venue: In Proc. international joint conference on neural networks,

title: Formal theory of creativity, fun, and intrinsic motivation (1990–2010)

venue: IEEE Transactions on Autonomous Mental Development,

authors:
Eric Schulz
Rahul Bhui
Bradley C. Love
Bastien Brier
Michael T. Todd
Samuel J. Gershman

title: Structured, uncertainty-driven exploration in real-world consumer choice

venue: Proceedings of the National Academy of Sciences,

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Richard S Sutton
Doina Precup
Satinder Singh

title: Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning

venue: Artificial intelligence,

authors:
Andrea L Thomaz
Cynthia Breazeal

title: Experiments in socially guided exploration: Lessons learned in building robots that learn with and without human teachers

venue: Connection Science,

title: Efficient exploration in reinforcement learning

title: Adaptive ε-greedy exploration in reinforcement learning based on value differences

venue: In Annual Conference on Artificial Intelligence,

authors:
Gina G Turrigiano
Sacha B Nelson

title: Homeostatic plasticity in the developing nervous system

venue: Nature reviews neuroscience,

authors:
James A. Waltz
Robert C. Wilson
Matthew A. Albrecht
Michael J. Frank
James M. Gold

title: Differential effects of psychotic illness on directed and random exploration

venue: Computational Psychiatry,

authors:
Ziyu Wang
Tom Schaul
Matteo Hessel
Hado Hasselt
Marc Lanctot
Nando Freitas

title: Dueling network architectures for deep reinforcement learning

venue: Proceedings of The 33rd International Conference on Machine Learning,

authors:
Marco A Wiering
Hado Van Hasselt

title: Ensemble algorithms in reinforcement learning

venue: IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics),

authors:
J.M. Wolfe
K.R. Cave
S.L. Franzel

title: Guided search: an alternative to the feature integration model for visual search

venue: J Exp Psychol Hum Percept Perform,

authors:
Daochen Zha
Wenye Ma
Lei Yuan
Xia Hu
Ji Liu

title: Rank the episodes: A simple approach for exploration in procedurally-generated environments

title: 2019). This system comprises of a fleet of 120 CPU-based actors (combined

heading: 1 INTRODUCTION

text:
The trade-off between exploration and exploitation is described as the crux of learning and behaviour across many domains, not just reinforcement learning (Sutton & Barto, 2018), but also in decision making (Cohen et al., 2007), evolutionary biology (Cremer et al., 2019), ecology (Kembro et al., 2019), neuroscience (e.g., focused versus diffuse search in visual attention (Wolfe et al., 1989), dopamine regulations (Chakroun et al., 2020)), cognitive sciences (Hills et al., 2015), as well as psychology and psychiatry (Addicott et al., 2017). In a nutshell, exploration is about the balance between taking the familiar choice that is known to be rewarding and learning about unfamiliar options of uncertain reward, but which could ultimately be more valuable than the familiar options.
Ample literature has studied the question of how much to explore, that is how to set the overall trade-off (and how to adjust it over the course of learning) (Jaksch et al., 2010; Cappé et al., 2013; Lattimore & Szepesvári, 2020; Thrun, 1992), and the question of how to explore, namely how to choose exploratory actions (e.g., randomly, optimistically, intrinsically motivated, or otherwise) (Schmidhuber, 1991; Oudeyer & Kaplan, 2009; Linke et al., 2019). In contrast, the question of when to explore has been studied very little, possibly because it does not arise in bandit problems, where a lot of exploration methods are rooted. The ‘when’ question and its multiple facets are the subjects of this paper. We believe that addressing it could lead to more intentional forms of exploration.
Consider an agent that has access to two modes of behaviour, an ‘explore’ mode and an ‘exploit’ mode (e.g., a random policy and a greedy policy, as in ε-greedy). Even when assuming that the overall proportion of exploratory steps is fixed, the agent still has multiple degrees of freedom: it can explore more at the beginning of training and less in later phases; it may take single exploratory steps or execute prolonged periods of exploration; it may prefer exploratory steps early or late within an episode; and it could trigger the onset (or end) of an exploratory period based on various criteria. Animals and humans exhibit non-trivial behaviour in all of these dimensions, presumably encoding useful inductive biases that way (Power, 1999). Humans make use of multiple effective strategies, such as selectively exploring options with high uncertainty (a form of directed, or informationseeking exploration), and increasing the randomness of their choices when they are more uncertain (Gershman, 2018; Gershman & Tzovaras, 2018; Ebitz et al., 2019). Monkeys use directed exploration to manage explore-exploit trade-offs, and these signals are coded in motivational brain regions (Costa et al., 2019). Patients with schizophrenia register changes in directed exploration and experience low-grade inflammation when shifting from exploitation to random exploration (Waltz et al., 2020; Cathomas et al., 2021). This diversity is what motivates us to study which of these can benefit
RL agents in turn, by expanding the class of exploratory behaviours beyond the commonly used monolithic ones (where modes are merged homogeneously in time).

heading: 2 METHODS

text:
The objective of an RL agent is to learn a policy that maximises external reward. At the high level, it achieves this by interleaving two processes: generating new experience by interacting with the environment using a behaviour policy (exploration) and updating its policy using this experience (learning). As RL is applied to increasingly ambitious tasks, the challenge for exploration becomes to keep producing diverse experience, because if something has not been encountered, it cannot be learned. Our central argument is therefore simple: a monolithic, time-homogeneous behaviour policy is strictly less diverse than a heterogeneous mode-switching one, and the former may hamstring the agent’s performance. As an illustrative example, consider a human learning how to ride a bike (explore), while maintaining their usual happiness through food, sleep, work (exploit): there is a stark contrast between a monolithic, time-homogeneous behaviour that interleaves a twist of the handlebar or a turn of a pedal once every few minutes or so, and the mode-switching behaviour that dedicates prolonged periods of time exclusively to acquiring the new skill of cycling.
While the choice of behaviour in pure exploit mode is straightforward, namely the greedy pursuit of external reward (or best guess thereof), denoted by G, there are numerous viable choices for behaviour in a pure explore mode (denoted by X ). In this paper we consider two standard ones: XU , the naive uniform random policy, and XI , an intrinsically motivated behaviour that exclusively pursues a novelty measure based on random network distillation (RND, (Burda et al., 2018)). See Section 4 and Appendix B for additional possibilities of X . In this paper we choose fixed behaviours for these modes, and focus solely on the question of when to switch between them. In our setting, overall proportion of exploratory steps (the how much), denoted by pX , is not directly controlled but derives from the when.

heading: 2.1 GRANULARITY

text:
An exploration period is an uninterrupted sequence of steps in explore mode. We consider four choices of temporal granularity for exploratory periods, also illustrated in Figure 1.
Step-level exploration is the most common scenario, where the decision to explore is taken independently at each step, affecting one action.1 The canonical example is ε-greedy (Fig.1:C).
Experiment-level exploration is the other extreme, where all behaviour during training is produced in explore mode, and learning is off-policy (the greedy policy is only used for evaluation). This scenario is also very common, with most forms of intrinsic motivation falling into this category, namely pursuing reward with an intrinsic bonus throughout training (Fig.1:A).2
Episode-level exploration is the case where the mode is fixed for an entire episode at a time (e.g., training games versus tournament matches in a sport), see Fig.1:B. This has been investigated for simple cases, where the policy’s level of stochasticity is sampled at the beginning of each episode (Horgan et al., 2018; Kapturowski et al., 2019; Zha et al., 2021).
Intra-episodic exploration is what falls in-between step- and episode-level exploration, where exploration periods last for multiple steps, but less than a full episode. This is the least commonly studied scenario, and will form the bulk of our investigations (Fig.1:D,E,F,G).
We denote the length of an exploratory period by nX (and similarly nG for exploit mode). To characterise granularity, our summary statistic of choice is medX := median(nX ). Note that there are two possible units for these statistics: the raw steps or the proportion of the episode length L. The latter has different (relative) semantics, but may be more appropriate when episode lengths vary widely across training. We denote it as rmedX := median(nX /L).
1The length of an exploratory period tends to be short, but it can be greater than 1, as multiple consecutive step-wise decisions to explore can create longer periods.
2Note that it is also possible to interpret ε-greedy as experiment-level exploration, where the X policy is fixed to a noisy version of G.

heading: 2.2 SWITCHING MECHANISMS

text:
Granularity is but the coarsest facet of the ‘when’ question, but the more precise intra-episode timings matter too, namely when exactly to start and when to stop an exploratory period. This section introduces two mechanisms, blind and informed switching. It is worth highlighting that, in general, the mechanism (or its time resolution) for entering explore mode differs from the one for exiting it (to enter exploit mode) – this asymmetry is crucial to obtain flexible overall amounts of exploration. If switching were symmetric, the proportion would be pX ≈ 0.5. Blind switching The simplest switching mechanism does not take any state into account (thus, we call it blind) and is only concerned with producing switches at some desired time resolution. It can be implemented deterministically through a counter (e.g., enter explore mode after 100 exploit mode steps), or probabilistically (e.g., at each step, enter explore mode with probability 0.01). Its expected duration can be parameterised in terms of raw steps, or in terms of fractional episode length. The opposite of blind switching is informed switching, as discussed below.
Informed switching Going beyond blind switching opens up another rich set of design choices, with switching informed by the agent’s internal state. There are two parts: first, a scalar trigger signal is produced by the agent at each step, using its current information – drawing inspiration from human behaviour, we view the triggering signal as a proxy for uncertainty (Schulz et al., 2019): when uncertainty is high, the agent will switch to explore. Second, a binary switching decision is taken based on the trigger signal (for example, by comparing it to a threshold). Again, triggering will generally not be symmetric between entering and exiting an exploratory period.
To keep this paper focused, we will look at one such informed trigger, dubbed ‘value promise discrepancy’ (see Appendix B for additional competitive variants). This is an online proxy of how much of the reward that the agent’s past value estimate promised (k steps ago) have actually come about. The intuition is that in uncertain parts of state space, this discrepancy will generally be larger than when everything goes as expected. Formally,
Dpromise(t− k, t) := ∣∣∣∣∣V (st−k)− k−1∑ i=0 γiRt−i − γkV (st) ∣∣∣∣∣ where V (s) is the agent’s value estimate at state s, R is the reward, and γ is a discount factor.
Starting mode When periods last for a significant fraction of episode length, it also matters how the sequence is initialised, i.e., whether an episode starts in explore or in exploit mode, or more generally, whether the agent explores more early in an episode or more later on. It is conceivable that the best choice among these is domain dependent (see Figure 6): in most scenarios, the states at the beginning of an episode have been visited many times, thus starting with exploit mode can be beneficial; in other domains however, early actions may disproportionately determine the available future paths (e.g., build orders in StarCraft (Churchill & Buro, 2011)).

heading: 2.3 FLEXIBILITY WITHOUT ADDED BURDEN

text:
Our approach introduces additional flexibility to the exploration process, even when holding the specifics of the learning algorithm and the exploration mode fixed. To prevent this from turning into an undue hyper-parameter tuning burden, we recommend adding two additional mechanisms.
Bandit adaptation The two main added degrees of freedom in our intra-episodic switching set-up are when (or how often) to enter explore mode, and when (or how quickly) to exit it. These can be parameterised by a duration, termination probability or target rate (see Section 3.1). In either case, we propose to follow Schaul et al. (2019) and Badia et al. (2020a), and delegate the adaptation of these settings to a meta-controller, which is implemented as a non-stationary multi-armed bandit that maximises episodic return. As an added benefit, the ‘when’ of exploration can now become adaptive to both the task, and the stage of learning.
Homeostasis In practice, the scales of the informed trigger signals may vary substantially across domains and across training time. For example, the magnitude of Dpromise will depend on reward scales and density and can decrease over time as accuracy improves (the signals could also be noisy). This means that naively setting a threshold hyper-parameter is impractical. For a simple remedy, we have taken inspiration from neuroscience (Turrigiano & Nelson, 2004) to add homeostasis to the binary switching mechanism, which tracks recent values of the signal and adapts the threshold for switching so that a specific average target rate is obtained. This functions as an adaptive threshold, making tuning straightforward because the target rate of switching is configured independently of the scales of the trigger signal. See Appendix A for the details of the implementation.

heading: 3 RESULTS

text:
The design space we propose contains a number of atypical ideas for how to structure exploration. For this reason, we opted to keep the rest of our experimental setup very conventional, and include multiple comparable baselines, ablations and variations.
Setup: R2D2 on Atari We conduct our investigations on a subset of games of the Atari Learning Environment (Bellemare et al., 2013), a common benchmark for the study of exploration. All experiments are conducted across 7 games (FROSTBITE, GRAVITAR, H.E.R.O., MONTEZUMA’S REVENGE, MS. PAC-MAN, PHOENIX, STAR GUNNER), the first 5 of which are classified as hard exploration games (Bellemare et al., 2016), using 3 seeds per game. For our agent, we use the R2D2 architecture (Kapturowski et al., 2019), which is a modern, distributed version of DQN (Mnih et al., 2015) that employs a recurrent network to approximate its Q-value function. This is a common basis used in exploration studies (Dabney et al., 2020; Badia et al., 2020b;a). The only major modification to conventional R2D2 is its exploration mechanism, where instead we implement all the variants of mode-switching introduced in Section 2. Separately from the experience collected for learning, we run an evaluator process that assesses the performance of the current greedy policy. This is what we report in all our performance curves (see Appendix A for more details).
Baselines There are a few simple baselines worth comparing to, namely the pure explore mode (pX = 1, Fig.1:A) and the pure exploit mode (pX = 0), as well as the step-wise interleaved ε-greedy execution (Fig.1:C), where pX = 0.01 = ε (without additional episodic or intra-episodic structure). Given its wide adoption in well-tuned prior work, we expect the latter to perform well overall. The fourth baseline picks a mode for an entire episode at a time (Fig.1:B), with the probability of picking X being adapted by a bandit meta-controller. We denote these as experiment-level-X, experiment-level-G, step-level-0.01 and episode-level-* respectively. For each of these, we have a version with uniform (XU ) and intrinsic (XI ) explore mode.

heading: 3.1 VARIANTS OF INTRA-EPISODIC EXPLORATION

text:
As discussed in Section 2, there are multiple dimensions along which two-mode intra-episodic exploration can vary. The concrete ones for our experiments are:
• Explore mode: uniform random XU , or RND intrinsic reward XI (denoted XU and XI). • Explore duration (nX ): this can be a fixed number of steps (1, 10, 100), or one of these
is adaptively picked by a bandit (denoted by *), or the switching is symmetric between entering and exiting explore mode (denoted by =).
• Trigger type: either blind or informed (based on value promise, see Section 2.2). • Exploit duration (nG): for blind triggers, the exploit duration can be parameterised by fixed
number of steps (10, 100, 1000, 10000), indirectly defined by a probability of terminating (0.1, 0.01, 0.001, 0.0001), or adaptively picked by a bandit over these choices (denoted by n* or p*, respectively). For informed triggers, the exploit duration is indirectly parameterised by a target rate in (0.1, 0.01, 0.001, 0.0001), or a bandit over them (p*), which is in turn transformed into an adaptive switching threshold by homeostasis (Section 2.2).
• Starting mode: G greedy (default) or X explore (denoted by G or X).
We can concisely refer to a particular instance by a tuple that lists these choices. For example, XU-intra(100,informed,p*,X) denotes uniform random exploration XU , with fixed 100- step explore periods, triggered by the value-promise signal at a bandit-determined rate, and starting in explore mode. See Figure 2 for an illustration.

heading: 3.2 PERFORMANCE RESULTS

text:
We start by reporting overall performance results, to reassure the reader that our method is viable (and convince them to keep reading the more detailed and qualitative results in the following sections). Figure 3 shows performance across 7 Atari games according to two human-normalised aggregation metrics (mean and median), comparing one form of intra-episodic exploration to all the baselines, separately for each explore mode (XU and XI ). The headline result is that intra-episodic exploration improves over both step-level and episode-level baselines (as well as the pure experimentlevel modes that we would not expect to be very competitive). The full learning curves per game are found in the appendix, and show scores on hard exploration games like MONTEZUMA’S REVENGE or PHOENIX that are also competitive in absolute terms (at our compute budget of 2B frames).
Note that there is a subtle difference to the learning setups between XU and XI , as the latter requires training a separate head to estimate intrinsic reward values. This is present even in pure exploit mode, where it acts as an auxiliary task only (Jaderberg et al., 2016), hence the differences in pure greedy curves in Figure 3. For details, see Appendix A.

heading: 3.3 DIVERSITY RESULTS

text:
In a study like ours, the emphasis is not on measuring raw performance, but rather on characterising the diversity of behaviours arising from the spectrum of proposed variants. A starting point is to return to Figure 1 (right), and assess how much of the previously untouched space is now filled
by intra-episodic variants, and how the ‘when’ characteristics translate into performance. Figure 4 answers these questions, and raises some new ones. First off, the raw amount of exploration pX is not a sufficient predictor of performance, implying that the temporal structure matters. It also shows substantial bandit adaptation at work: compare the exploration statistics at the start (squares) and end-points of training (crosses), and how these trajectories differ per game; a common pattern is that reducing pX far below 0.5 is needed for high performance. Interestingly, these adaptations are similar between XU and XI , despite very different explore modes (and differing performance
XU-intra(=,blind,100,G) on frostbite
XU-intra(=,blind,0.01,G) on frostbite
Frostbite
results). We would expect prolonged intrinsic exploration periods to be more useful than prolonged random ones, and indeed, comparing the high-rmedX variant (purple) across XU and XI , it appears more beneficial for the latter. Zooming in on specific games, a few results stand out: in XU mode, the only variant that escapes the inherent local optimum of PHOENIX is the blind, doubly adaptive one (purple), with the bandits radically shifting the exploration statistics over the course of training. In contrast, the best results on MONTEZUMA’S REVENGE are produced by the symmetric, informed trigger variant (light green), which is forced to retain a high pX . Finally, FROSTBITE is the one game where an informed trigger (red) clearly outperforms its blind equivalent (purple).
These insights are still limited to summary statistics, so Figure 5 looks in more depth at the detailed temporal structure within episodes (as in Figure 1, left). Here the main comparison is between blind and informed triggers, illustrating that the characteristics of the fine-grained within-episode structure can differ massively, despite attaining the same high-level statistics pX and medX . We can see quite a lot of variation in the trigger structure – the moments we enter exploration are not evenly spaced anymore. As a bonus, the less rigid structure of the informed trigger (and possibly the more carefully chosen switch points) end up producing better performance too.
Figure 6 sheds light on a complementary dimension, differentiating the effects of starting in explore or exploit mode. In brief, each of these can be consistently beneficial in some games, and consistently harmful in others. Another observation here is the dynamics of the bandit adaptation: when starting in exploit mode, it exhibits a preference for long initial exploit periods in many games (up to 10000 steps), but that effect vanishes when starting in explore mode (see also Appendix C). More subtle effects arise from the choice of parameterisation of switching rates. Figure 7 shows a stark qualitative difference on how probabilistic switching differs from step-count based switching, with the former spanning a much wider diversity of outcomes, which improves performance.

heading: 3.4 TAKE-AWAYS

text: Summarising the empirical results in this section, two messages stand out. First, there seems to be a sweet spot in terms of temporal granularity, and intra-episodic exploration is the right step towards finding it. Second, the vastly increased design space of our proposed family of methods gives rise to a large diversity of behavioural characteristics; and this diversity is not superficial, it also translates to meaningful performance differences, with different effects in different games, which cannot be reduced to simplistic metrics, such as pX . In addition, we provide some sensible rules-of-thumb for practitioners willing to join us on the journey of intra-episodic exploration. In general, it is useful to let a bandit figure out the precise settings, but it is worth curating its choices to at most a handful. Jointly using two bandits across factored dimensions is very adaptive, but can sometimes be harmful when they decrease the signal-to-noise ratio in each other’s learning signal. Finally, the choice of the uncertainty-based trigger should be informed by the switching modes (see Appendix B for details).

heading: 4 DISCUSSION

text:
Time-based exploration control The emphasis of our paper was on the benefits of heterogeneous temporal structure in mode-switching exploration. Another potential advantage over monolithic approaches is that it may be easier to tune hyper-parameters related to an explicit exploration budget (e.g., via pX ) than to tune an intrinsic reward coefficient, especially if extrinsic reward scales change across tasks or time, and if the non-stationarity of the intrinsic reward affects its overall scale.
Diversity for diversity’s sake One role of a general-purpose exploration method is to allow an agent to get off the ground in a wide variety of domains. While this may clash with sample-efficient learning on specific domains, we believe that the former objective will come to dominate in the long run. In this light, methods that exhibit more diverse behaviour are preferable for that reason alone because they are more likely to escape local optima or misaligned priors.
Related work While not the most common approach to exploration in RL, we are aware of some notable work investigating non-trivial temporal structure. The z-greedy algorithm (Dabney et al., 2020) initiates contiguous chunks of directed behaviour (‘flights’) with the length sampled from a heavy-tailed distribution. In contrast to our proposal, these flights act with a single constant action instead of invoking an explore mode. Campos et al. (2021) pursue a similar idea, but with flights along pre-trained coverage policies, while Ecoffet et al. (2021) chain a ‘return-to-state’ policy to an explore mode. Maybe closest to our XI setting is the work of Bagot et al. (2020), where periods of intrinsic reward pursuit are explicitly invoked by the agent. Exploration with gradual change instead of abrupt mode switches generally appears at long time-scales, such as when pursuing intrinsic rewards (Schmidhuber, 2010; Oudeyer & Kaplan, 2009) but can also be effective at shorter timescales, e.g., Never-Give-Up (Badia et al., 2020b). Related work on the question of which states to prefer for exploration decisions (Tokic, 2010) tends not to consider prolonged exploratory periods.
Relation to options Ideas related to switching behaviours at intra-episodic time scales are wellknown outside of the context of exploration. In the options framework in hierarchical RL, the goal is to chain together a sequence of sub-behaviours into a reward-maximising policy (Sutton et al., 1999; Mankowitz et al., 2016). Some work has looked at using options for exploration too (Jinnai et al., 2019a; Bougie & Ichise, 2021). In its full generality, the options framework is a substantially more ambitious endeavour than our proposal, as it requires learning a full state-dependent hierarchical policy that picks which option to start (and when), as well as jointly learning the options themselves.
Limitations Our proposed approach inherits many typical challenges for exploration methods, such as sample efficiency or trading off risk. An aspect that is particular to the intra-episode switching case is the different nature of the off-policy-ness. The resulting effective policy can produce state distributions that differ substantially from those of either of the two base mode behaviours that are being interleaved. It can potentially visit parts of the state space that neither base policy would reach if followed from the beginning of the episode. While a boon for exploration, this might pose a challenge to learning, as it could require off-policy corrections that treat those states differently and do not only correct for differences in action space. Our paper does not use (non-trivial) off-policy correction (see Appendix A) as our initial experimentation showed it is not an essential component in the current setting (see Figure 15). We leave this intriguing finding for future investigation.
Future work With the dimensions laid out in Section 2, it should be clear that this paper can but scratch the surface. We see numerous opportunities for future work, some of which we already carried out initial investigations (see Appendix B). For starters, the mechanism could go beyond two-mode and switch between exploit, explore, novelty and mastery (Thomaz & Breazeal, 2008), or between many diverse forms of exploration, such as levels of optimism (Derman et al., 2020; Moskovitz et al., 2021). Triggers could be expanded or refined by using different estimations of uncertainty, such as ensemble discrepancy (Wiering & Van Hasselt, 2008; Buckman et al., 2018), amortised value errors (Flennerhag et al., 2020), or density models (Bellemare et al., 2016; Ostrovski et al., 2017); or other signals, such as salience (Downar et al., 2002), minimal coverage (Jinnai et al., 2019a;b), or empowerment (Klyubin et al., 2005; Gregor et al., 2016; Houthooft et al., 2016).
Conclusion We have presented an initial study of intra-episodic exploration, centred on the scenario of switching between an explore and an exploit mode. We hope this has broadened the available forms of temporal structure in behaviour, leading to more diverse, adaptive and intentional forms of exploration, in turn enabling RL to scale to ever more complex domains.

heading: A DETAILED EXPERIMENTAL SETUP

heading: A.1 ATARI ENVIRONMENT

text:
We use a selection of games from the widely used Atari Learning Environment (ALE, Bellemare et al. (2013)). It is configured to not expose the ‘life-loss’ signal, and use the full action set (18 discrete actions) for all games (not the per-game reduced effective action spaces). We also use the sticky-action randomisation as in (Machado et al., 2018). Episodes time-out after 108k frames (i.e. 30 minutes of real-time game play).
Differently from most past Atari RL agents following DQN (Mnih et al., 2015), our agent uses the raw 210 × 160 RGB frames as input to its value function (one at a time, without frame stacking), though it still applies a max-pool operation over the most recent 2 frames to mitigate flickering inherent to the Atari simulator. As in most past work, an action-repeat of 4 is applied, over which rewards are summed.

heading: A.2 AGENT

text:
The agent used in our Atari experiments is a distributed implementation of a value- and replay-based RL algorithm derived from the Recurrent Replay Distributed DQN (R2D2) architecture (Kapturowski et al., 2019). This system comprises of a fleet of 120 CPU-based actors (combined with a single TPU for batch inference) concurrently generating experience and feeding it to a distributed experience replay buffer, and a single TPU-based learner randomly sampling batches of experience sequences from replay and performing updates of the recurrent value function by gradient descent on a suitable RL loss.
The value function is represented by a convolutional torso feeding into a linear layer, followed by a recurrent LSTM (Hochreiter & Schmidhuber, 1997) core, whose output is processed by a further linear layer before finally being output via a Dueling value head (Wang et al., 2016). The exact parameterisation follows the slightly modified R2D2 presented by Dabney et al. (2020) and Schaul et al. (2021). Refer to Table 1 for a full list of hyper-parameters. It is trained via stochastic gradient descent on a multi-step TD loss (more precisely, a 5-step Q-learning loss) with the use of a periodically updated target network (Mnih et al., 2015) for bootstrap target computation, using mini-batches of sampled replay sequences. Replay sampling is performed using prioritized experience replay (Schaul et al., 2016) with priorities computed from sequences’ TD errors following the scheme introduced by Kapturowski et al. (2019). As in R2D2, sequences of 80 observations are used for replay, with a prefix of 20 observations used for burn-in. In a slight deviation from the original, our agent uses a fixed replay ratio of 1, i.e. the learner or actors get throttled dynamically if the average number of times a sample gets replayed exceeds or falls below this value; this makes experiments more reproducible and stable.
Actors periodically pull the most recent network parameters from the learner to be used in their exploratory policy. In addition to feeding the replay buffer, all actors periodically report their reward, discount and return histories to the learner, which then calculates running estimates of reward, discount and return statistics to perform return-based scaling (Schaul et al., 2021). If applicable, the episodic returns from the actors are also sent to the non-stationary bandit(s) that adapt the distribution over exploration parameters (e.g., target ratios ρ or period lengths nX ). In return, the bandit(s) provide samples from that distribution to each actor at the start of a new episode, just like Schaul et al. (2019).
Our agent is implemented with JAX (Bradbury et al., 2018), uses the Haiku (Hennigan et al., 2020), Optax (Budden et al., 2020b), Chex (Budden et al., 2020a), and RLax (Hessel et al., 2020) libraries for neural networks, optimisation, testing, and RL losses, respectively, and Reverb (Cassirer et al., 2020) for distributed experience replay.

heading: A.3 TRAINING AND EVALUATION PROTOCOLS

text:
All our experiments ran for 200k learner updates. With a replay ratio of 1, sequence length of 80 (adjacent sequences overlapping by 40 observations), a batch size of 64, and an action-repeat of 4 this corresponds to a training budget of 200000×64×40×1×4 ≈ 2B environment frames (which
is less than 10% of the original R2D2 budget). In wall-clock-time, one such experiment takes about 12 hours using 2 TPUs (one for the batch inference, the other for the learner) and 120 CPUs.
For evaluation, a separate actor (not feeding the replay buffer) is running alongside the agent using a greedy policy (ε = 0), and pulling the most recent parameters at the beginning of each episode. We follow standard evaluation methodology for Atari, reporting mean and median ‘human-normalised’ scores as introduced in (Mnih et al., 2015) (i.e. the episode returns are normalised so that 0 corresponds to the score of a uniformly random policy while 1 corresponds to human performance), as well as the mean ‘human-capped’ score which caps the per-game performance at human level. Error bars or shaded curves correspond to the minimum and maximum values across these seeds.

heading: A.4 RANDOM NETWORK DISTILLATION

text:
The agent setup for theXI experiments differs in a few ways from the default described above. First, a separate network is trained via Random Network Distillation (RND, (Burda et al., 2018)), which consists of a simple convnet with an MLP (no recurrence); for detailed settings, see RND section in Table 1. The RND prediction network is updated jointly with the Q-value network, on the same
data. The intrinsic reward derived from the RND loss is pursued at the same discount γ = 0.997 as the external reward in G. The Q-value network is augmented with a second head that predicts the Q-values for the intrinsic reward; this branches off after the ‘Post-LSTM linear layer’ (with 256), and is the same type of dueling head, using the same scale normalisation method (Schaul et al., 2021). In addition, the 5-step Q-learning is adapted to use a simple off-policy correction, namely trace-cutting on non-greedy actions (akin to Watkins Q(λ) with λ = 1), separately for each learning head.3 The XI policy is the greedy policy according to the Q-values of the second head. Note that because of these differences in set-up, and especially because the second head can function as an auxiliary learning target, it may be misleading to compare XI and XU results head-to-head: we recommend looking at how things change within one of these settings (across variants of intraepisodic exploration or the baselines), rather than between them.

heading: A.5 HOMEOSTASIS

text:
The role of the homeostasis mechanism is to transform a sequence of scalar signals xt ∈ R (for 1 ≤ t ≤ T ) into a sequence of binary switching decisions yt ∈ {0, 1} so that the average number of switches approximates a desired target rate ρ, that is , 1T ∑ t yt ≈ ρ, and high values of xt correspond to a higher probability of yt = 1. Furthermore, the decision at any point yt can only be based on the past signals x1:t. One way to achieve this is to exponentiate x (to turn it into a positive number x+) and then set an adaptive threshold to determine when to switch. Algorithm 1 describes how this is done in pseudo-code. The implementation defines a time-scale of interest τ := min(t, 100/ρ), and uses it to track moving averages of three quantities, namely the mean and variance of x, as well as the mean of x+.
Algorithm 1 Homeostasis Require: target rate ρ
1: initialize x← 0, x2 ← 1, x+ ← 1 2: for t ∈ {1, . . . , T} do 3: obtain next scalar signal return xt 4: set time-scale τ ← min(t, 100ρ ) 5: update moving average x← (1− 1τ )x+ 1 τ xt 6: update moving variance x2 ← (1− 1τ )x2 + 1 τ (xt − x) 2
7: standardise and exponentiate x+ ← exp ( xt−x√ x2 ) 8: update transformed moving average x+ ← (1− 1τ )x+ + 1 τ x +
9: sample yt ∼ Bernoulli ( min ( 1, ρ x +
x+ )) 10: end for
In our informed trigger experiments we use value promise as the particular choice of trigger signal xt = Dpromise(t−k, t). As discussed in Section3.1, when using a bandit, its choices for target rates are ρ ∈ {0.1, 0.01, 0.001, 0.0001}.

heading: B OTHER VARIANTS

text: The results we report in the main paper are but a subset of the possible variants that could be tried in this rather large design space. In fact, we have done initial investigations on a few of these, which we report below.

heading: B.1 ADDITIONAL EXPLORE MODES

text:
Softer explore-exploit modes The all-or-nothing setting with a greedy exploit mode and a uniform random explore mode is clear and simple, but it is plausible that less extreme choices could work well too, such as an ε-greedy explore mode with ε = 0.4 and an ε-greedy exploit mode with
3While this seemed like important aspect to us, it turned out to make very little difference in hindsight, see Figure 15.
ε = 0.1. We denote this pairing as XS . Preliminary results (see Figure 16) indicate that overall performance is mostly similar to XU , possibly less affected by the choice of granularity and triggers.
Different discounts Another category of explore mode (Xγ) is to pursue external reward but at a different time-scale (e.g., a much shorter discount like γ = 0.97). This results in less of a switch between explore and exploit modes, but rather in an alternation of long-term and short-term reward pursuits, producing a different kind of behavioural diversity. So far, we do not have conclusive results to report with this mode.

heading: B.2 ADDITIONAL INFORMED TRIGGERS

text:
Action-mismatch-based triggers Another type of informed trigger is to derive an uncertainty estimate from the discrepancies across an ensemble. For example, we can train two heads that use an identical Q-learning update but are initialised differently. From that, we can measure multiple forms of discrepancy, a nice and robust one is to rank the actions according to each head and compute how large the overlap among the top-k actions is.
Variance-based triggers Another type of informed trigger is to measure the variance of the Qvalues themselves, taken across such an ensemble (of two heads) and use that as an alternative uncertainty-based trigger.
Figure 8 shows preliminary results on how performance compares across these two new informed triggers, in relation to the value-promise one from Section 2.2. Overall, the action-mismatch trigger seems to have an edge, at least in this setting, and we plan to investigate this further in the future. From other probing experiments, it appears that for other explore modes, different trigger signals are more suitable.

heading: C ADDITIONAL RESULTS

text:
This section includes additional results. Wherever the main figures included a subset of games or variants (Figures 4, 5, 7) we show full results here (Figures 11, 12, 13, respectively), and the aggregated performances of Figure 3 are split out into individual games in Figure 10. Also, some of the learning curves from Figures 4 and 11 are shown in Figure 16. In addition, Figure 14 illustrates how the internal bandit probabilities evolve over time based on starting mode for the experiments shown in Figure 6. Lastly, we provide some bonus illustrations for the intra-episodic design decisions included in the namings of our variants in Figure 9 with the hope of facilitating the interpretation and intuition for intra-episodic variants and their resulting behaviours.
XI-intra(=,blind,p*,G)