Zhengying Liu
email: zhengying.liu@inria.fr

Zhen Xu
email: xuzhen@4paradigm.com

Shangeth Rajaa

Meysam Madadi
email: meysam.madadi@gmail.com

Julio C S Jacques Junior

Sergio Escalera
email: sergio@maia.ub.es

Adrien Pavao
email: adrien.pavao@gmail.com

Wei-Wei Tu

Isabelle Guyon
email: guyon@chalearn.org

Hugo Jair Escalante

Raia Hadsell

Towards Automated Deep Learning: Analysis of the AutoDL challenge series 2019

Keywords: Hyper-parameter optimization, AutoML, Deep Learning, AutoDL, Neural architecture search, benchmarks

We present the design and results of recent competitions in Automated Deep Learning (AutoDL). In the AutoDL challenge series 2019, we organized 5 machine learning challenges: AutoCV, AutoCV2, AutoNLP, AutoSpeech and AutoDL. The first 4 challenges concern each a specific application domain, such as computer vision, natural language processing and speech recognition. At the time of March 2020, the last challenge AutoDL is still on-going and we only present its design. 1 Some highlights of this work include: (1) a benchmark suite of baseline AutoML solutions, with emphasis on domains for which Deep Learning methods have had prior success (image, video, text, speech, etc); (2) a novel "anytime learning" framework, which opens doors for further theoretical consideration; (3) a repository of around 100 datasets (from all above domains) over half of which are released as public datasets to enable research on meta-learning; (4) analyses revealing that winning solutions generalize to new unseen datasets, validating progress towards universal AutoML 1. Its results will be presented in future work together with detailed introduction of winning solutions of each challenge.

c 2020 Z. Liu et al.

solution;

(5) open-sourcing of the challenge platform, the starting kit, the dataset formatting toolkit, and all winning solutions (All information available at autodl.chalearn.org).

Introduction

Machine Learning (ML) keeps delivering impressive novel applications in our daily lives. But it is still facing enormous challenges, preventing its more universal deployment by users having direct needs but no time or resources to hire ML experts. In fact, even for ML experts, effectively tuning hyper-parameters is still a daunting task, particularly for Deep Learning models, let alone addressing higher level aspects of model design, including problem definition, experimental design, data collection, preprocessing, design of metrics, computation of error bars, detection of bias in data, etc. Certainly, automating the entire modeling pipeline is still a far reaching goal, but the challenges we present in this paper allowed us to make great strides. We present here the results of the Automated Deep Learning (AutoDL) challenge series, addressing tasks in Computer Vision [START_REF] Liu | Towards automated computer vision: Analysis of the autocv challenges 2019[END_REF], Natural Language Processing (NLP), Speech Recognition, etc. With the solutions provided (and open-sourced) by the winners, users must only preprocess data to horseshoe-fit them in a generic tensor format to have automated algorithms train and test Deep Learning neural networks for them. The problems addressed are multi-label classification, in an amazingly broad range of application domains (medical imaging, object or gesture classification, satellite imaging, to name a few). Besides saving human effort, the benefit of such automated solutions include reproducibility and accountability, freeing us potentially from the variability of human solutions and possibly increasing reliability.

The AutoDL challenge series is part of a larger effort on Automated Machine learning (AutoML) with code submission in which the solutions of participants are blind tested on the CodaLab challenge platform. In all of our AutoML challenges we seek to enforce learning within a fixed time budget and limited computational resources. One particularity of AutoDL challenges, compared to previous AutoML challenges, is that we seek to enforce any-time learning, which encourages solutions performing reasonably good early on in the whole learning process. This is achieved by using the Area under the Learning Curve (ALC) metric, as explained in Section 3. To help participants develop their code, we provide a starting kit in Python with TensorFlow/PyTorch interfaces, sample "public" datasets and sample code submissions. Some basic facts about the challenge series are summarized in Table 1.

While most of our challenges are run in two phases (a feedback phase with immediate feedback on a leaderboard on N = 5 practice datasets and a final phase with a single evaluation on N = 5 final test datasets), in AutoCV, we evaluated the participants on the results of the feedback phase, to make it slightly easier. However, we ran privately a final test phase of which we report here the results. Since the 5 AutoCV final phase datasets were not disclosed, we re-used some in subsequent phases. AutoCV2 was run regularly in 2 phases. Even practice datasets during the feedback phase were not revealed to the participants (they were solely visible to their "autonomous agent").

Data

In AutoDL challenges, raw data (images, videos, audio, text, etc) are provided to participants formatted in a uniform tensor manner (namely TFRecords, a standard generic data format used by TensorFlow). For images with native compression formats (e.g. JPEG, BMP, GIF), we directly use the bytes. Our data reader decodes them on-the-fly to obtain a 4D tensor. Video files in mp4/avi format (without the audio track) are used in a similar manner. For text datasets, each example (i.e. a document) is a sequence of integer indices.

Each index corresponds to a word (for English) or character (for Chinese) in a vocabulary given in the metadata. For speech datasets, each example is represented by a sequence of floating numbers specifying the amplitude at each timestamp, similar to uncompressed WAV format. Lastly, tabular datasets' feature vector representation can be naturally considered as a special case of our 4D tensor representation.

For practical reasons, each dataset was kept under 4GB, which required sometimes reducing image resolution, cropping, and/or downsampling videos. We made sure to include application domains in which the scales varied a lot. We formatted around 100 datasets in total and used 61 of them for AutoDL challenges: 16 image, 9 video, 15 text, 15 speech and 6 tabular. The distribution of domain and size is visualized in Figure 1. More basic information/meta-features are presented in Table 3 in Appendix A. All datasets marked "public" can be downloaded on corresponding challenge websites, for example on the Get Data page of AutoDL challenge. All tasks are supervised multi-label classification problems, i.e. data samples are provided in pairs {X, Y }, X being an input 4D tensor of shape (time, row, col, chnl) and Y a target binary vector (withheld from in test data).

Evaluation Metrics

AutoDL challenges encourage any-time learning by scoring participants with the Area under the Learning Curve (ALC) (see example curves in Figure 2). The participants can train in increments of a chosen duration (not necessarily fixed) to progressively improve performance, until the time limit is attained. Performance is measured by the NAUC or Normalized Area Under ROC Curve (AUC) N AU C = 2 × AU C -1 averaged over all classes. Multi-class classification metrics are not being considered, i.e. each class is scored independently. Since several predictions can be made during the learning process, this allows us to plot learning curves, i.e. "performance" (on test set) as a function of time. Then for each dataset, we compute the Area under Learning Curve (ALC). The time axis is log scaled (see the xlabel's in Figure 2 for the formula used for time transformation) to put more emphasis on the beginning of the curve. In this way, we encouraged participants to develop techniques that improve performance rapidly at the beginning of the training process. This should be important to treat large redundant and/or imbalanced datasets and small datasets alike, e.g. by treating effectively redundancy in large training datasets or using learning machines pre-trained on other data if training samples are scarce. Finally, in each phase, an overall rank for the participants is obtained by averaging their ALC ranks obtained on each individual dataset. The average rank in the final phase is used to determine the winners.

Baselines

As each challenge (except for AutoDL) involves a specific domain, different baselines are provided for different challenges.

Baselines for AutoCV & AutoCV2

For AutoCV and AutoCV2, we introduced 3 baseline methods with varied complexity and computer resource requirements. Baseline 0 makes one single all-zero prediction and always gets 0 NAUC score (hence 0 ALC as well). Baseline 1 is a linear classifier. It uses a cross entropy loss and an Adam optimizer [START_REF] Diederik | Adam: A Method for Stochastic Optimization[END_REF]. If the input shape is variable, resize all images to a fixed shape 112 × 112. When the number of frames (time axis) is variable, sample 10 consecutive frames at random, both for training and testing. The scheduling strategy is to double the number of training steps at each iteration. Stop training and predicting when time budget is not enough for next iteration. Baseline 2 uses a neural network architecture determined by the tensor shape of the input examples. More concretely, 3D convolutional layer is repeatedly applied followed by a 3D max-pooling layer, until the number of neurons of the hidden layer is less than a pre-defined number (e.g. 1000), then apply a fully connected layer for classification. More details on these baselines can be found in [START_REF] Liu | Towards automated computer vision: Analysis of the autocv challenges 2019[END_REF]. Lastly, we also prepared two private baselines with fixed backbone architecture ResNet-50 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] and Inception-V3 [START_REF] Szegedy | Rethinking the Inception Architecture for Computer Vision[END_REF] but these baselines are only used by the organizers for testing and comparison purpose.

Baselines for AutoNLP

For AutoNLP, Baseline 0 uses a Support Vector Machine (SVM) as classifier. The input text is preprocessed by keeping only the alphanumeric characters and been vectorized with the Term Frequency Inverse Document Frequency (TF-IDF) vectorizer with a maximum vocabulary size of 20000. Baseline 1 follows [START_REF] Kim | Convolutional neural networks for sentence classification[END_REF] and uses a convolutional neural network (CNN). In this method, the text input data is preprocessed like in the previous baseline. The vocabulary is indexed and the integer sequence is then padded with a maximum sequence length. The model architecture consists of an Embedding layer with a dimension of 200, two 1D convolutional layers, a Maxpooling layer, two 1D convolutional layers, a Global Average pooling layer and a fully connected layer. Compared to Baseline 1, Baseline 2 uses pretrained word embedding weights in addition. This method uses the same preprocessing, vectorization and model architecture from the previous baseline with an embedding layer of dimension 300. The embedding layer weights are loaded with a pretrained embedding from FastText [START_REF] Bojanowski | Enriching word vectors with subword information[END_REF].

Baseline for AutoSpeech

The baseline method for AutoSpeech is relatively straightforward. Features are extracted on each dataset using Mel-Frequency Cepstral Coefficients (MFCC) [START_REF] Mermelstein | Distance measures for speech recognition, psychological and instrumental[END_REF], with shape padding. We then apply a CNN backbone model on the extracted preprocessed features, automatically adapting the number of layers according to the number of features. We train only one iteration or perform early stopping at convergence. For prediction, the same MFCC feature preprocessing is applied and use the trained model for inference.

Baseline for AutoDL

For the final (and still on-going, as of 8 March 2020) AutoDL challenge, we provide a baseline referred to as Baseline 3, which is a combination of the winner solutions of AutoCV (kakaobrain), AutoNLP (upwind flys) and AutoSpeech (PASA NJU ), using domain inference which depends only on the input shape of the 4D tensor. On tabular datasets (which are never used in above challenges), the model chosen is simply a fully connected neural network with 2 hidden layers of 256 neurons.

Challenge results

In this section, we present the results and analysis of AutoCV, AutoCV2, AutoNLP and AutoSpeech. Because of space constraints, we cannot provide details on winning solutions. However, the codes have been released and more details will be provided in an extended paper in preparation. We only consider the top-10 participants in the final phase of each challenge for all analyses. The names of the top-3 teams can be found in Table 2.

Learning curves obtained in each challenge

For a given task, we plot all learning curves of top-10 participants in the same figure, for a clear comparison. In Figure 2, four of such figures are shown, each from a different Table 2: Top-3 winners and Pearson correlation coefficient between average ranking vectors in feedback phase and final phase, with corresponding p-value. For all challenges except AutoCV2, the Pearson correlation is close to 1 with significant p-value, which means that the feedback phase results and final phase results are consistent, suggesting the generalization ability of these AutoDL methods. For AutoCV2, top-10 participants used very similar approaches (all similar to the solution of kakaobrain, in AutoCV), which makes the performances of different teams very close.

Challenge

Top

Generalization ability of AutoML methods

To evaluate the generalization ability of AutoML methods on unseen datasets, we compute the average rank over 5 datasets in both phases and consider their correlation (recall that datasets are DIFFERENT in each phase). This gives an average rank pair (r 1 , r 2 ) ∈ R 2 for each participant. When r 1 is close to r 2 , the method is considered to super-generalize, i.e. generalize in the AutoML sense to NEW datasets, not just to a different test set from the same datasets as in common ML challenges. We plot all these pairs (r 1 , r 2 ) in Figure 3. We observe that most participants' rank pairs are close to the diagonal, suggesting generalization ability for most methods. Some outliers such as LEAD are due to technical failure of code execution, e.g. with an out of memory (OOM) error. And to evaluate the soundness of the choice of datasets for evaluating generalization, we also compute the Pearson correlation coefficient for all r 1 , r 2 in Table 2 using ρ X,Y = cov(X, Y )/(σ X σ Y ).

Modeling difficulty of datasets

To benchmark the modeling difficulty of each task/dataset, Figure 4 shows the best-vs-worst performances among top-10 participants. We see that many datasets from AutoNLP such as PR1 to PR5 are found on the top-right, meaning that the performance variance is small. This could be due to the pre-trained word embedding weights from FastText [START_REF] Bojanowski | Enriching word vectors with subword information[END_REF] or BERT [START_REF] Devlin | Bert: Pre-training of deep bidirectional transformers for language understanding[END_REF] we provide in a Docker image shared by all participants. With these pre-trained word embedding, even weak classifiers could obtain relatively good performance. On the other hand, datasets from AutoSpeech such as data11 and data25 have large modeling difficulty, which might be related to the fact that raw speech datasets often require careful pre-processing steps in order to train a successful classifier.

Addressing the any-time learning problem

The Figure 5 informs on participant's effectiveness to address the any-time learning problem. We first factored out dataset difficulty by re-scaling ALC and NAUC scores (resulting scores on each dataset having mean 0 and variance 1). Then we plotted, for each participant, their fraction of submissions in which ALC is larger than NAUC (FRAC for short) vs. correlation(ALC, N AU C) (CORR for short). The participants in the bottom half of the figure did not address well the any-time learning problem because their FRAC is lower than 50%. Those participants did not perform well in the challenge either (small symbols). The participants that did well in the challenge (large symbols) are all in the upper right quadrant, with both FRAC larger than 50% and CORR larger than 0.7.

Discussion & Conclusion

The challenges AutoCV, AutoCV2, AutoNLP and AutoSpeech have allowed us to demonstrate that fully automated solution for one specific domain such as computer vision, natural language processing or speech recognition, is not as far away as many thought it was. The winning solutions have proven to be generalizable to unseen datasets, at least for each given domain. We have now publicly available software capable of handling any image, video, text and speech classification tasks without any human intervention whatsoever. However, whether these domain-specific approaches can be improved by cross-domain meta-learning methods is yet to be examined after the results of the final AutoDL challenge. For the any-time learning aspect, results show that methods having good any-time performance also have good final performance, but not always. This justifies our choice metric and suggests that it is harder than usual fixed-time performance metrics. The fact that there are learning curves crossing each other indicates that there is space for improvement in that respect. As for the repository of datasets that begins to take shape (already 100 datasets formatted), we benchmarked the datasets used in AutoDL challenges by participants' submissions and we see various modeling difficulty across different domains. The datasets we formatted together with our analysis will help the community push forward the study of meta-learning.

Figure 1 :

 1 Figure 1: Distribution of type, size and domain for all 61 AutoDL datasets.

Figure 2 :

 2 Figure2: Learning curves for one specific task in each challenge. From these curves, we can already see that the strategies used by participants vary a lot. The number of predictions (i.e. number of points on a learning curve) ranges from 1 (e.g. in (c), Kon on PR5 in AutoNLP final phase) to 789 of DeepWisdom on data24 in AutoSpeech final phase, in (d). And from whether the curve decreases dramatically at some point (e.g. in (a), base 1 and XH on ukulele), we can infer whether the submitted method uses a validation set to determine if a prediction should be made.

Figure 3 :

 3 Figure3: Generalization ability of AutoML methods. For each participant in a challenge, the average rank (over 5 datasets) in both phases is computed as x-axis and y-axis. When the scattered point is close to the diagonal, the feedback phase (with leaderboard feedback) result and final phase (with unseen datasets) result are consistent.

Figure 4 :

 4 Figure 4: Modeling difficulty of each task/dataset. The x-axis (resp. yaxis) is the minimum (resp. maximum) ALC among top-10 participants in each challenge-phase. Tasks on top-left have larger modeling difficulty, while those close to the diagonal have small performance variance and model difficulty.

Figure 5 :

 5 Figure 5: CORR vs FRAC (%(ALC > NAUC) vs correlation(ALC, NAUC)). ALC and NAUC were "scaled" (see text). The numbers in the legend are average scaled ALC and average rank of each participant. The marker size increases monotonically with average scaled ALC. 34 out of 40 participants have a CORR greater than 0.5 and 30 out of 40 participants have a FRAC above 0.5.

Table 1 :

 1 Basic facts on AutoDL challenges.

	Challenge	Begin date End date #Teams #Submis-#Phases
		2019	2019-20		sions
	AutoCV1	May 1	Jun 29	102	938	1
	AutoCV2	Jul 2	Aug 20	34	336	2
	AutoNLP	Aug 2	Aug 31	66	420	2
	AutoSpeech	Sep 16	Oct 16	33	234	2
	AutoDL	Dec 14	Mar 14	28	80	2

Table 3 :

 3 Datasets used in AutoDL challenges. "HWR" means handwriting recognition, "chnl" channel, and "var" variable size.

	Class	Sample number	Tensor dimension

Acknowledgments

This work was sponsored with a grant from Google Research (Zürich) and additional funding from 4Paradigm, Amazon and Microsoft. It has been partially supported by the Spanish projects TIN2015-66951-C2-2-R, RTI2018-095232-B-C22, TIN2016-74946-P (MINECO/FEDER, UE) and CERCA Programme / Generalitat de Catalunya and ICREA under the ICREA Academia programme. We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the GPU used for this research. It received in kind support from the institutions of the co-authors. We are very indebted to Olivier Bousquet and André Elisseeff at Google for their help with the design of the challenge and the countless hours that André spent engineering the data format. The special version of the CodaLab platform we used was implemented by Tyler Thomas, with the help of Eric Carmichael, CK Collab, LLC, USA. Many people contributed time to help formatting datasets, prepare baseline results, and facilitate the logistics. The full list can be found at https://autodl.chalearn.org.


Johan Ferret
email: jferret@google.com

Olivier Pietquin
email: pietquin@google.com

Matthieu Geist
email: mfgeist@google.com

Self-Imitation Advantage Learning

Keywords: Reinforcement Learning, Off-Policy Learning, Self-Imitation

Self-imitation learning is a Reinforcement Learning (RL) method that encourages actions whose returns were higher than expected, which helps in hard exploration and sparse reward problems. It was shown to improve the performance of on-policy actor-critic methods in several discrete control tasks. Nevertheless, applying self-imitation to the mostly action-value based off-policy RL methods is not straightforward. We propose SAIL, a novel generalization of self-imitation learning for off-policy RL, based on a modification of the Bellman optimality operator that we connect to Advantage Learning. Crucially, our method mitigates the problem of stale returns by choosing the most optimistic return estimate between the observed return and the current action-value for self-imitation. We demonstrate the empirical effectiveness of SAIL on the Arcade Learning Environment, with a focus on hard exploration games.

INTRODUCTION

Some approaches combine Reinforcement Learning (RL) and learning from (expert) demonstrations [START_REF] Hester | Deep q-learning from demonstrations[END_REF][START_REF] Piot | Boosted bellman residual minimization handling expert demonstrations[END_REF]. It is efficient, but having access to expert demonstrations might not be possible in many situations. An interesting and more practical alternative is to learn from oneself, by focusing on one's own instructive experiences. In the context of RL [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], self-imitation learning is a technique that takes advantage of this idea and proposes to learn from positive experiences, using actions whose payoff was superior to what had been predicted. It was introduced by Oh et al. [START_REF] Oh | Self-imitation learning[END_REF] for on-policy learning, where interaction data is obtained via a behaviour policy and is used to improve this policy, never to be reused again. In that context, self-imitation provides a practical way to revisit and reinforce interesting actions.

In the off-policy setting, agents learn instead from the behaviour of different policies than their own, while they are still periodically allowed to interact in the environment to generate new interaction data. Off-policy learning is attractive because it would make RL useful in situations where interacting in the environment is costly or impractical, which is the case in many real-world scenarios [START_REF] Dulac-Arnold | Challenges of real-world reinforcement learning[END_REF]. In the most extreme case, offline RL [START_REF] Levine | Offline reinforcement learning: Tutorial, review, and perspectives on open problems[END_REF], no interaction at all is possible and one must learn a policy just by looking at a dataset of past experiences generated by potentially many different policies. Sadly, the canonical form of self-imitation learning relies on a modified policy gradient [START_REF] Stuart | Temporal Credit Assignment in Reinforcement Learning[END_REF], which requires the ability to modify the current policy in a given direction. This requirement makes it incompatible with most off-policy methods [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF][START_REF] Kapturowski | Recurrent experience replay in distributed reinforcement learning[END_REF][START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF], whose policy is obtained by applying an exploration method on top of the current estimate of the optimal action-value. Since the policy is implicit, gradient ascent in the policy space is impractical. As an example, a straightforward adaptation of SIL for a standard offpolicy RL algorithm such as Deep Q-Networks [DQN,[START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF] seems out-of-reach. Indeed, the action-value network that is central to DQN encapsulates the two aspects SIL targets separately in the actor-critic: value estimation and decision-making.

The focus of this work is on providing a self-imitation method that is applicable across the full spectrum of off-policy methods. A common denominator to all off-policy algorithms is the use of the action-value to inform decision-making, be it with an implicit policy [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF], or an explicit one [START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF]. Hence, a way to control which actions are reinforced in off-policy learning is to artificially increase the reward of such actions. Staying in the line of reasoning of SIL, a natural idea is to use the difference between the observed return and the estimated value as the reward bonus. It turns out that doing so creates a problem because the observed return becomes stale over time, biasing action-value towards pessimism instead of optimism, and eventually reducing the self-imitation contribution to none. To circumvent this issue, we opt for the simple strategy of using the most optimistic between the return and the estimated action-value, with which we extend the benefits of self-imitation. We show a connection to Advantage Learning [AL, [START_REF] Leemon | Reinforcement learning through gradient descent[END_REF][START_REF] Bellemare | Unifying count-based exploration and intrinsic motivation[END_REF], an actiongap increasing off-policy algorithm.

Our contributions are the following: 1) we propose SAIL, a generalization of self-imitation learning for off-policy methods, 2) we show how it connects to Advantage Learning and complements it, 3) we demonstrate the practicality of our method in terms of simplicity, efficiency and performance on the Arcade Learning Environment [ALE, 8] benchmark, under several base off-policy RL methods. Notably, we report considerable performance gains on hard exploration games.

BACKGROUND AND NOTATIONS 2.1 Reinforcement Learning

We use the standard Markov Decision Processes (MDP) formalism [START_REF] Puterman | Markov Decision Processes[END_REF]. An MDP is a tuple 𝑀 = {S, A, 𝑃, 𝑅, 𝛾 }, where S is the state space, A is the action space, 𝑃 is the transition kernel, 𝑅 is the bounded reward function and 𝛾 ∈ [0, 1) is the discount factor. We note 𝜏 = {𝑠 𝑖 , 𝑎 𝑖 , 𝑟 𝑖 } 𝑖=[0,𝑇 ] a (random) trajectory and the associated return is 𝐺 = ∞ 𝑡 =0 𝛾 𝑡 𝑟 𝑡 . A policy 𝜋 ∈ Δ S A outputs action probabilities in a given state, and can be used for decision-making in a given environment. We place ourselves in the infinite-horizon setting, which means that we look for a policy that maximizes 𝐽 (𝜋) = E 𝜋 [𝐺 0 ]. The value of a state is the quantity

𝑉 𝜋 (𝑠) = E 𝜋 [ ∞ 𝑡 =0 𝛾 𝑡 𝑟 𝑡 |𝑆 0 = 𝑠].
The action-value of a state-action couple is the quantity

𝑄 𝜋 (𝑠, 𝑎) = E 𝜋 [ ∞ 𝑡 =0 𝛾 𝑡 𝑟 𝑡 |𝑆 0 = 𝑠, 𝐴 0 = 𝑎]. The Bellman operator T 𝜋 is T 𝜋 𝑉 (𝑠) = E 𝜋 [𝑟 (𝑠, 𝑎) + 𝛾𝑉 (𝑠 ′ )],
its unique fixed point is 𝑉 𝜋 . The Bellman optimality operator T * is defined as T * 𝑄 (𝑠, 𝑎) = E 𝜋 [𝑟 (𝑠, 𝑎) + 𝛾 max 𝑎 ′ 𝑄 (𝑠 ′ , 𝑎 ′ )], its unique fixed point is the optimal action value 𝑄 * . A policy belongs to the set of optimal policies iff 𝑄 𝜋 (𝑠, 𝑎) = 𝑄 * (𝑠, 𝑎).The action-gap [START_REF] Farahmand | Action-Gap Phenomenon in Reinforcement Learning[END_REF] 𝑔 𝑄 * of a particular state quantifies the difference between the value of the best action and that of the other actions: 𝑔 𝑄 * (𝑠, 𝑎) = max 𝑎 ′ 𝑄 * (𝑠, 𝑎 ′ ) -𝑄 * (𝑠, 𝑎). The advantage 𝐴 is the difference between the action-value and the value: 𝐴(𝑠, 𝑎) = 𝑄 (𝑠, 𝑎) -𝑉 (𝑠).

Actor-critic. Actor-critic methods use a policy and a value function. In the standard formulation, the value (from the critic) guides the policy via the policy gradient, L 𝑃𝐺 =log 𝜋 𝜃 (𝑎 𝑡 |𝑠 𝑡 )(𝐺 𝑡 -𝑉 𝜃 (𝑠 𝑡 )), while the value itself is updated via temporal difference on data generated by the actor:

L 𝑉 = 1 2 (𝑟 𝑡 + 𝛾𝑉 𝜃 (𝑠 𝑡 +1 ) -𝑉 𝜃 (𝑠 𝑡 )) 2 .
Off-policy RL. DQN [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] is an adaptation of Q-learning [START_REF] Christopher | Q-learning[END_REF] to the deep learning framework. It conserves the principal aspect of Q-learning, that is updating the current action-value towards a bootstrapped version of itself, following the temporal difference algorithm. The major difference with respect to Q-learning is the use of a function approximator for the action-value, instead of using a tabular representation. Past transitions are sampled from a replay buffer [START_REF] Lin | Self-improving reactive agents based on reinforcement learning, planning and teaching[END_REF], and, for stability, the action-value to be updated is compared to a target function, which is a previous and periodically updated version of the action-value function (whose parameters we note 𝜃 -). Rainbow [START_REF] Hessel | Rainbow: Combining improvements in deep reinforcement learning[END_REF] extends DQN by combining several independently proposed algorithmic innovations [START_REF] Marc G Bellemare | A distributional perspective on reinforcement learning[END_REF][START_REF] Fortunato | Noisy networks for exploration[END_REF][START_REF] Schaul | Prioritized experience replay[END_REF][START_REF] Van Hasselt | Deep reinforcement learning with double q-learning[END_REF][START_REF] Wang | Dueling network architectures for deep reinforcement learning[END_REF], and showed to be a strong baseline on the Atari Learning Environment benchmark. IQN [START_REF] Dabney | Implicit Quantile Networks for Distributional Reinforcement Learning[END_REF] is a distributional RL approach that estimates the whole distribution of the returns, instead of the mean as in standard Q-learning. More precisely, it approximates the continuous quantile function of the return distribution by sampling input probabilities uniformly. In terms of performance, it (almost) bridges the gap with Rainbow while not having any prioritized replay and using single-step bootstrapping.

Self-Imitation Learning

Self-imitation learning [SIL,[START_REF] Oh | Self-imitation learning[END_REF] provides a set of additional loss functions that complement the existing actor-critic losses, and encourage the agent to mimic rewarding past behavior. It relies on a replay buffer that stores past transitions {𝑠 𝑡 , 𝑎 𝑡 , 𝐺 𝑡 }, where the observed return 𝐺 𝑡 = +∞ 𝑖=0 𝛾 𝑖 𝑟 𝑡 +𝑖 is obtained once the episode is over. SIL operates off-policy, since its losses are calculated using past transitions from the replay buffer, implying that on-policy actor-critic methods that benefit from SIL become part on-policy, part off-policy. For a given transition (𝑠 𝑡 , 𝑎 𝑡 , 𝐺 𝑡 ), the additional policy and value losses are:

L sil 𝑃𝐺 = -log 𝜋 𝜃 (𝑎 𝑡 |𝑠 𝑡 )(𝐺 𝑡 -𝑉 𝜃 (𝑠 𝑡 )) + and L sil 𝑉 = 1 2 (𝐺 𝑡 -𝑉 𝜃 (𝑠 𝑡 )) 2 + ,
where the notation (𝑥) + = max(0, 𝑥) stands for the ReLU operator. The shared term (𝐺 𝑡 -𝑉 𝜃 (𝑠 𝑡 )) + is positive if the observed return outweighs the estimated value, in which case both the action probabilities and the value are increased. SIL also relies on prioritization [START_REF] Schaul | Prioritized experience replay[END_REF], as transitions are sampled from the replay buffer with probability 𝑃 (𝜏) ∝ (𝐺 𝑡 -𝑉 𝜃 -(𝑠 𝑡 )) + . As a result, transitions in which actions led to an unexpectedly high return get revisited more often, ensuring faster propagation of important reward signals.

A drawback of this formulation is that an explicit policy is required.Also, while it provides good empirical results, self-imitation in general might suffer from stochasticity, both in the environment dynamics and in the variance of the rewards. Indeed, the optimistic updates of SIL can lead to overestimating the value of actions that bring high rewards once in a while. See Sec. 4.5 for a more in-depth discussion about the role of stochasticity.

Advantage Learning

Advantage Learning (AL) is an action-gap increasing algorithm introduced by Baird [START_REF] Leemon | Reinforcement learning through gradient descent[END_REF] and further studied by Bellemare et al. [START_REF] Bellemare | Unifying count-based exploration and intrinsic motivation[END_REF]. It corresponds to the following modified Bellman operator, T 𝐴𝐿 𝑄 (𝑠, 𝑎) = T * 𝑄 (𝑠, 𝑎) + 𝛼 (𝑄 (𝑠, 𝑎)max 𝑎 ′ 𝑄 (𝑠, 𝑎 ′ )), which translates to the following reward modification: r𝐴𝐿 (𝑠, 𝑎) = 𝑟 (𝑠, 𝑎) + 𝛼 (𝑄 (𝑠, 𝑎)max 𝑎 ′ 𝑄 (𝑠, 𝑎 ′ )). It can be seen as adding the advantage 𝑄 (𝑠, 𝑎) -𝑉 (𝑠) to the reward, with 𝑉 (𝑠) = max 𝑎 𝑄 (𝑠, 𝑎) (hence the name). Generally speaking, increasing the action-gap makes the RL problem easier, as it facilitates the distinction from experience between the optimal action and the others. In practice, AL was shown to bring consistent performance improvement across the whole support of Atari games for off-policy agents [START_REF] Bellemare | Unifying count-based exploration and intrinsic motivation[END_REF].

SAIL: SELF-IMITATION ADVANTAGE LEARNING

In essence, self-imitation drives the policy towards actions whose returns are unexpectedly good. Off-policy methods usually optimize an action-value function, which only implicitly defines the policy through a given exploration method. Nevertheless, there is a sensible proxy for increasing the probability of picking an action: increasing its action-value (which is nothing more than a reward increase). Hence, we propose to adapt self-imitation for off-policy using the following modified reward:

r𝑆𝐴𝐼𝐿 (𝑠 𝑡 , 𝑎 𝑡 ) = 𝑟 (𝑠 𝑡 , 𝑎 𝑡 ) +𝛼 (max(𝐺 𝑡 , 𝑄 𝜃 -(𝑠 𝑡 , 𝑎 𝑡 )) -max 𝑎 𝑄 𝜃 -(𝑠 𝑡 , 𝑎)),
The corresponding loss function is:

L 𝑆𝐴𝐼 𝐿 = 1 2 r𝑆𝐴𝐼𝐿 (𝑠 𝑡 , 𝑎 𝑡 ) + 𝛾 max 𝑎 𝑄 𝜃 -(𝑠 𝑡 +1 , 𝑎) -𝑄 (𝑠 𝑡 , 𝑎 𝑡 ) 2 .
We now motivate this expression in more details. First, note that if we replace max(𝐺 𝑡 , 𝑄 (𝑠, 𝑎)) by 𝐺 𝑡 and apply the ReLU operator to the additional term we get the modified reward:

r (𝑠 𝑡 , 𝑎 𝑡 ) = 𝑟 (𝑠 𝑡 , 𝑎 𝑡 ) + 𝛼 (𝐺 𝑡 -max 𝑎 𝑄 𝜃 -(𝑠 𝑡 , 𝑎)) + , (1)
which would be a more straightforward adaptation of SIL, since it increases the action-value by the same term used in SIL for both policy and value updates. Empirically, this formulation compares unfavorably to ours (see Sec. 4.6). We posit it could be due to a limitation of self-imitation: the problem of stale returns. This problem is the following: when off-policy, the return used for self-imitation corresponds to the observed return of a policy that becomes increasingly different from the current one, under the hypothesis that the agent is still learning. Inevitably, returns become outdated. More precisely, these returns drift towards pessimism, since the agent mostly improves over time. As a result, the self-imitation [START_REF] Oh | Self-imitation learning[END_REF]. In past experiences (in faded red), the agent ("A") got the key ("K") but failed to reach the goal ("T"). The corresponding transitions still get sampled from the replay buffer, so actions leading to the key are paired with zero returns. This is inconsistent with the current policy (in red), which gets the key, opens the door and reaches the goal. SAIL avoids undervaluing the role of the key by using the most optimistic return estimate between the observed return and the current action-value.

bonus disappears for most transitions. In addition to making selfimitation ineffective, it could lead to emphasizing wrong signals and biasing the updates. We illustrate this phenomenon in Fig. 1. By exchanging the return for the maximum between the return and the current action-value estimate, our method forms a more optimistic return estimate, which promotes optimism and alleviates staleness. Additionally, by replacing the ReLU operator with the identity, we update our action-value estimate using information from both positive and negative experiences. Finally, compared to SIL, we do not make use of prioritization, as we think it emphasizes the impact of stochasticity on the algorithm. In our experiments, we measure the benefits of our method under increasing stochasticity in Sec. 4.5, and show that the gains over the baseline remain even when stochasticity is high. Second, the proposed modified reward can be decomposed as:

r𝑆𝐴𝐼𝐿 (𝑠 𝑡 , 𝑎 𝑡 ) = r𝐴𝐿 (𝑠 𝑡 , 𝑎 𝑡 ) + 𝛼 (𝐺 𝑡 -𝑄 𝜃 -(𝑠 𝑡 , 𝑎 𝑡 )) + ,
Thus, our approach actually combines AL, an action-gap increasing method, with SIL, which helps reproducing interesting trajectories from the past. We show next that it outperforms AL. We name the resulting algorithm Self-Imitation Advantage Learning (SAIL 1 ). It is: 1) general, i.e. compatible across a large spectrum of off-policy methods,2) easy to use, as it arranges existing quantities to form a reward bonus, and 3) lightweight, in the sense that it does not add much to the computational budget of the algorithm (other than computing discounted returns, which is neglectible). The pseudo-code is in Alg. 1.

EXPERIMENTS

In this section, we aim to answer the following questions: 1) How does SAIL perform on various tasks, including hard exploration, using various off-policy algorithms as baselines? (see Sec. 4.2 & 4.3); 2) Does SAIL compare favorably to exploration bonuses? (see Sec. 4.4); 1 We take the liberty of inverting the middle letters to form a nice acronym. 3) What is the impact of stochasticity on SAIL? (see Sec. 4.5); and 4) How does SAIL compare to a more straightforward self-imitation algorithm? (see Sec. 4.6).

Experimental setting

We benchmark our method and baselines on the Arcade Learning Environment [START_REF] Marc G Bellemare | The arcade learning environment: An evaluation platform for general agents[END_REF], with sticky actions and no episode termination on life losses, following [START_REF] Marlos | Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents[END_REF]. Sticky actions make the Atari games stochastic by repeating the agent's previous action with a fixed probability (0.25 by default). Hard exploration games are games where local exploration methods fail to achieve high scores. We use the list of hard exploration games from [START_REF] Bellemare | Unifying count-based exploration and intrinsic motivation[END_REF], and set them apart with a bold font in bar plots. We use the Dopamine framework [START_REF] Samuel Castro | Dopamine: A Research Framework for Deep Reinforcement Learning[END_REF] to get reference implementations for the agents and setup our experiments. Whether using the base off-policy algorithms as is or in combination with SAIL, we use Dopamine reference hyperparameters for all methods, unless explicitly mentioned. The only SAIL-specific hyperparameter is 𝛼, that we set to 𝛼 = 0.9 in all experiments. The bonus term is also clipped in [-1, 1] (as are the rewards in ALE). We use 6 random seeds for comparative studies on subsets of games, and 3 random seeds for experiments on the 592 Atari games, due to the computational demand of such experiments.

For bar plots (e.g. Fig. 3), the mean relative improvement metric for a method 𝑋 compared to the baseline 𝑋 𝑏𝑎𝑠𝑒 is, for one game:

( 1

𝑁 200 ∑ 𝑡 =1 𝑠 𝑋 ,𝑡 -𝑠 𝑋 𝑏𝑎𝑠𝑒 ,𝑡 )/(| 1 𝑁 200 ∑ 𝑡 =1 𝑠 𝑋 𝑏𝑎𝑠𝑒 ,𝑡 | + 𝜖),
where {𝑠 𝑋 ,𝑡 } 𝑡 =1,...,200 are the game scores for method 𝑋 , collected every million steps in the environment, and averaged across all random seeds. This metric roughly measures by how much the performance of the proposed method increased or decreased compared to the baseline. For aggregated plots (e.g. Fig. 2), we report the human-normalized median score, a common metric to evaluate RL methods based on their performance across all games:

(s 𝑋 ,𝑡 -𝑠 𝑟𝑎𝑛𝑑𝑜𝑚 )/|𝑠 ℎ𝑢𝑚𝑎𝑛 -𝑠 𝑟𝑎𝑛𝑑𝑜𝑚 |,
where {s 𝑋 ,𝑡 } 𝑡 =1,...,200 are the median scores across all games for method 𝑋 , collected every million steps in the environment, and averaged across all random seeds. 𝑠 𝑟𝑎𝑛𝑑𝑜𝑚 is the end score of a random policy, and 𝑠 ℎ𝑢𝑚𝑎𝑛 that of the average human player, as reported in [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF], and completed for missing games as in [START_REF] Vieillard | Munchausen Reinforcement Learning[END_REF].

SAIL-DQN experiments

We report the performance of SAIL combined to DQN (abbreviated SAIL-DQN) against DQN on all Atari games in Fig. 3. We use the Dopamine DQN hyperparameters. We also report the same graph with AL-DQN as the baseline on Fig. 3. AL-DQN corresponds to the limit case of SAIL where the action-value estimate is always greater than the observed return, and makes for a stronger baseline than vanilla DQN. With the simple modification provided by SAIL, we get a nice average and median performance increase across all games (+101.4% average and +6.7% median), the gap being more apparent on hard exploration games where self-imitation shines the most (+361.6% average and +24.9% median relative improvement over AL-DQN).

We also zoom in on the performances of the three methods (DQN, AL-DQN and SAIL-DQN) on individual games. We choose four hard exploration games: Frostbite, Venture, Gravitar and PrivateEye. The scores are displayed on Fig. 4. On Frostbite and PrivateEye, SAIL-DQN outperforms C513 [START_REF] Marc G Bellemare | A distributional perspective on reinforcement learning[END_REF], a distributional RL agent that uses Adam [START_REF] Diederik | Adam: A method for stochastic optimization[END_REF], a more advanced optimizer than DQN's RMSProp [START_REF] Tieleman | Lecture 6.5-RMSProp: Divide the gradient by a running average of its recent magnitude[END_REF]. On PrivateEye, that has particularly sparse rewards, SAIL-DQN also outperforms IQN. Finally, we report the final performances on hard exploration games for all three methods in Table 1, and individual curves on all 59 games can be found in Fig. 12.

SAIL-IQN experiments

Since SAIL is a general self-imitation method for off-policy learning, it is straightforward to apply it to other off-policy agents. Hence, having demonstrated strong performance using DQN as a base agent in the previous subsection, we now turn towards a more advanced off-policy algorithm. We choose IQN, a strong distributional RL agent, and use the same IQN hyperparameters as [START_REF] Dabney | Implicit Quantile Networks for Distributional Reinforcement Learning[END_REF], which in contrast to those of Dopamine do not use n-step bootstrapping. We report the performance of SAIL combined to IQN (abbreviated SAIL-IQN) against IQN on all Atari games in Fig. 5, using the same metric as in previous graphs. We also compare SAIL-IQN to AL-IQN and to Rainbow across all games in the same figure. Despite the fact that Rainbow uses prioritized experience replay and n-step bootstrapping (with 𝑛 = 3), we report +80.3% average and +4% median relative performance increase for SAIL-IQN over Rainbow. Additionally, we display individual game performances of IQN, AL-IQN and SAIL-IQN in Fig. 6. We choose two hard exploration games: Montezuma's Revenge and Venture; and also on an easy exploration game: Seaquest, illustrating the versatility of SAIL. We report the final performances on hard exploration games of all three methods in Table 2, and individual curves on all 59 games in Fig. 13.

Finally, we compare several of the algorithms mentioned using the human-normalized median scores in Fig. 2, aggregating scores from all games. SAIL-IQN outperforms Rainbow (itself outperforming IQN), without using prioritization or n-step bootstrapping. SAIL-DQN outperforms C51 (itself outperforming DQN).

Comparison to Intrinsic Motivation

We compare SAIL-IQN to IQN with RND [START_REF] Burda | Exploration by random network distillation[END_REF], a popular intrinsic motivation method for exploration. While the two methods have different motivations, both modify the reward function and were shown to help in hard exploration tasks. RND uses two identical neural networks, the first of which is frozen after initialization. The second network has to predict the output of this random network. The prediction error is then used as a proxy of actual state-visitation counts to reward the agent. For RND, we use code and hyperparameters from Taïga et al. [START_REF] Ali Taïga | Benchmarking bonus-based exploration methods on the arcade learning environment[END_REF]. RND hyperparameters were calibrated for Rainbow, thus to be fair we use the same RND hyperparameters to study the combination of SAIL and RND (see below), and keep equal SAIL hyperparameters across agents. SAIL-IQN shows positive average and median relative improvement scores compared to RND-IQN (+72.2% average and +28.2% median relative improvement over RND-IQN, see Fig. 7).

On Montezuma's Revenge, which is an infamously hard exploration game, SAIL-IQN reaches a final score of 833 (for an average score of 513), while RND-IQN reaches a final score of 161 (for an average score of 45), and IQN scores 0 (final and average). SAIL can be combined to RND for further improvements: using RND (as is) and n-step bootstrapping (𝑛 = 3), SAIL-IQN reaches a final score of 5180 on Montezuma's Revenge. This ties SAIL-IQN with RND-Rainbow, which has the strongest score reported in Taïga et al. [START_REF] Ali Taïga | Benchmarking bonus-based exploration methods on the arcade learning environment[END_REF]. We display the evolution of that score in Fig. 8.

While we established the merits of SAIL compared to RND in terms of in-game Atari performance, SAIL has several other advantages over RND. 1) Consistency: while RND provides with better performance gains on specific games such as Montezuma's Revenge, we find that the gains are not consistent across all hard exploration games, matching the findings of Taïga et al. [START_REF] Ali Taïga | Benchmarking bonus-based exploration methods on the arcade learning environment[END_REF]. More precisely (not shown), using RND with IQN brought a great performance boost on two games (Montezuma's Revenge and Venture), but did not increase the median performance of IQN (-0.2% median relative improvement score). 2) Integration: SAIL requires two simple modifications to off-policy algorithms, saving returns to the replay buffer and modifying the action-value update (1 hyperparameter).

In comparison, RND requires two additional networks, separate optimizers and a reward modification (many hyperparameters). We acknowledge that this comparative benefit might be frameworkdependent. 3) Compute: on the same hardware, we find that standard IQN processes an average of 100 frames per second, against 95 for SAIL-IQN and 45 for RND-IQN, so completing experiments is more than twice faster when choosing SAIL over RND.

Impact of stochasticity

To quantify the impact of stochasticity on self-imitation, we perform an ablation and deactivate the sticky actions. Sticky actions [START_REF] Marc G Bellemare | The arcade learning environment: An evaluation platform for general agents[END_REF] introduce stochasticity in otherwise near-deterministic Atari games, by repeating the previous action of the agent with a fixed repeat probability. As in the standard settings of ALE, by default we use a repeat probability of 0.25, that is here set to 0. We report results on all Atari games in Fig. 9, similarly to the precedent section. As expected, SAIL brings a larger performance increase when we fall back to a near-deterministic setting but, interestingly, the results do not diverge much from the ones reported with the sticky actions (+231.6% versus +101.4% average, +12.7% versus +6.7% median).

We extend this experiment and instead increase the repeat probability, making environments more stochastic. We restrict ourselves to hard exploration games to limit the computational cost of the study. As Fig. 10 shows, the human-normalized median performance of SAIL-DQN decreases under higher action repeat probabilities. This phenomenon warrants further investigation, as we would have to tell apart the impact of stochasticity on SAIL from the general performance loss due to making the RL problem more difficult, which we leave for future work. Note that the performance of SAIL stays superior to that of DQN in the standard setting.

Comparison to straightforward SIL

We compare SAIL to the more straightforward self-imitation algorithm depicted Eq. ( 1), the alternate version of SAIL where we use the standard return alone, and a ReLU operator instead of the identity. We display average and median relative improvement scores with both DQN and IQN in Fig. 11.

RELATED WORK

Extending self-imitation learning. Guo et al. [START_REF] Guo | Generative adversarial self-imitation learning[END_REF] revisit GAIL [START_REF] Ho | Generative adversarial imitation learning[END_REF], an adversarial imitation method that encourages the agent to trick a discriminator into taking its behavior for expert behavior. Their method uses the agent's past behavior as expert behavior, identifying promising behavior in a similar way to standard self-imitation. Guo et al. [START_REF] Guo | Self-Imitation Learning via Trajectory-Conditioned Policy for Hard-Exploration Tasks[END_REF] use self-imitation over a diverse set of trajectories from the agent's past experience, showing that it helps on games where there are local minima that hinder learning. Tang [START_REF] Tang | Self-imitation learning via generalized lower bound qlearning[END_REF] studies the impact of importance sampling corrections and using n-step bootstrapping to replace the observed return in a generalized form of self-imitation, which is studied under the operator view. None of these methods explicitly target off-policy learning algorithms, and as such none have straightforward extensions to that setting.

RL for hard exploration tasks. Being able to solve hard exploration problems is an important target for RL. So far, quite different strategies have been developed to tackle these problems. Intrinsic motivation methods provide an additional source of reward to the agent, either for going to seldom visited areas of the state space [START_REF] Bellemare | Unifying count-based exploration and intrinsic motivation[END_REF][START_REF] Tang | # exploration: A study of count-based exploration for deep reinforcement learning[END_REF], or for experiencing novel things, that challenge its own predictions [START_REF] Burda | Exploration by random network distillation[END_REF][START_REF] Pathak | Curiosity-driven exploration by self-supervised prediction[END_REF][START_REF] Savinov | Episodic curiosity through reachability[END_REF]. Aytar et al. [START_REF] Aytar | Playing hard exploration games by watching youtube[END_REF] use expert demonstrations from human player-made videos as imitation data and create auxiliary tasks that incentive close-to-expert progression in the environment. Ecoffet et al. [START_REF] Ecoffet | Go-Explore: a New Approach for Hard-Exploration Problems[END_REF] propose an exhaustive exploration method that encourages the agent to visit promising areas of the state space while jointly learning how to get back to those areas if further exploration is needed. Badia et al. [START_REF] Puigdomènech Badia | Never Give Up: Learning Directed Exploration Strategies[END_REF] combine intrinsic motivation with an episodic motivation based on episodic memory. Paine et al. [START_REF] Le Paine | Making Efficient Use of Demonstrations to Solve Hard Exploration Problems[END_REF] uses expert demonstrations combined with a recurrent learner to solve partially observable hard exploration tasks. Badia et al. [START_REF] Puigdomènech Badia | Agent57: Outperforming the atari human benchmark[END_REF] uses a neural network to encapsulate multiple policies with different degrees of exploration and switches between policies using a multi-arm bandit algorithm. While SAIL proves to be useful for hard exploration, its main motivation is to learn properly from the agent's own instructive experiences. In that regard, it is not an exploration method per se, but could generally be combined to said exploration methods for further improvements, as we have illustrated with RND.

Sparse reward RL. There is a lot of ongoing effort regarding RL for sparse rewards as well, which is related to hard exploration and overlaps on many environments. In the goal-oriented setting, Andrychowicz et al. [START_REF] Andrychowicz | Hindsight experience replay[END_REF] propose to modify the replay buffer in hindsight and change the desired goal state by a state the agent actually visited, providing it with free reward signal. Lee et al. [START_REF] Young | Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update[END_REF] accelerate the propagation of sparse reward signals by sampling whole episodes from the replay buffer and performing updates starting from the end of the sampled episode. In a related way, Hansen et al. [START_REF] Hansen | Fast deep reinforcement learning using online adjustments from the past[END_REF] combine standard off-policy with episodic control, estimating the action-value as the convex combination of the action-value learned off-policy and another estimate from episodic memory. Trott et al. [START_REF] Trott | Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards[END_REF] use reward shaping to explore while avoiding local minima. They use sibling trajectories, pairs of trajectories that are different but equally initialized, to create goal states. Since the additions of SAIL to off-policy agents are purely restricted to the action-value updates, SAIL and sparse reward RL techniques could synergize well, which we leave for future experiments.

Misc. Self-imitation strives to reproduce unexpectedly good behavior, and promotes a form of optimism by doing so, since it does not question the likelihood of the high payoff observed. He et al. [START_REF] Frank S He | Learning to play in a day: Faster deep reinforcement learning by optimality tightening[END_REF] instead show that there are tractable bounds to the optimal action-value function and use them to increase the Q-function when it is inferior to the lower bound (resp. decrease when superior to the upper bound). Riquelme et al. [START_REF] Riquelme | Adaptive Temporal-Difference Learning for Policy Evaluation with Per-State Uncertainty Estimates[END_REF] propose an algorithmic scheme that combines TD and Monte Carlo estimation in an adaptive way. In contrast, our method uses the observed return for self-imitation, which is the Monte Carlo estimator for the return, while still conserving temporal difference for the action-value update.

DISCUSSION

In this work, we presented SAIL, a novel self-imitation method for off-policy learning. In comparison with standard self-imitation, SAIL revolves around the action-value function, which makes it compatible with many off-policy algorithms. SAIL is a simple, general and lightweight method that can be equivalently viewed as a modified Bellman optimality operator (that is related to Advantage Learning) or as a modified reward function. Notably, it combines the advantages of self-imitation, that is better reinforcement in sparse reward scenarios, and those of Advantage Learning, that is increasing the action-gap. We studied its performance in the Arcade Learning Environment and demonstrated that SAIL brought consistent performance gains, especially on hard exploration games, at virtually no cost.

Figure 1 :

 1 Figure 1: Illustration of the stale returns problem, in the Key-Door-Treasure environment[START_REF] Oh | Self-imitation learning[END_REF]. In past experiences (in faded red), the agent ("A") got the key ("K") but failed to reach the goal ("T"). The corresponding transitions still get sampled from the replay buffer, so actions leading to the key are paired with zero returns. This is inconsistent with the current policy (in red), which gets the key, opens the door and reaches the goal. SAIL avoids undervaluing the role of the key by using the most optimistic return estimate between the observed return and the current action-value.

Algorithm 1 :Figure 2 :

 12 Figure2: Human-normalized median performance of several off-policy methods. SAIL-IQN outperforms every other method, including Rainbow, which uses prioritized experience replay and n-step bootstrapping. SAIL-DQN, though based on DQN, outperforms C51, a distributional RL algorithm that uses a more advanced optimizer (Adam).

Figure 3 :

 3 Figure 3: SAIL-DQN outperforms both DQN (top) and AL-DQN (bottom), as shown on a relative scale on all Atari games. On hard exploration games (in bold), SAIL-DQN provides a +654.3% average and +71.8% median relative improvement over DQN, and a +361.6% average and +24.9% median relative improvement over AL-DQN.

Figure 4 :

 4 Figure 4: Performances of DQN, AL-DQN and SAIL-DQN on four hard exploration Atari games. On PrivateEye, despite sparse rewards, SAIL-DQN outperforms both C51 and IQN.

Figure 5 :

 5 Figure 5: SAIL-IQN outperforms both IQN (top), AL-IQN (middle) and Rainbow (bottom), as shown on a relative scale on all Atari games. SAIL is responsible for important gains over IQN and AL-IQN on sparse reward hard exploration games such as Montezuma's Revenge, PrivateEye, or Gravitar.

Figure 6 :

 6 Figure 6: Performances of IQN, AL-IQN and SAIL-IQN on three hard exploration Atari games and one easy exploration game (Seaquest), illustrating the versatility of SAIL.

Figure 7 :

 7 Figure 7: SAIL-IQN outperforms RND-IQN, as shown on a relative scale on all Atari games, including on Montezuma's Revenge, an infamously hard exploration game.

Figure 8 :

 8 Figure 8: Combining SAIL and RND elevates the performance of IQN and matches that of RND-Rainbow, the best reported in Taïga et al. [42] on Montezuma's Revenge.

Figure 9 :

 9 Figure 9: Improvement of SAIL-DQN over AL-DQN on all Atari games, without sticky actions. Result do not diverge from those in the standard ALE setting (+222.6% versus +101.4% average, +11.7% versus +6.7% median).

Figure 10 :

 10 Figure 10: Even under increased stochasticity, SAIL-DQN outperforms DQN in the standard setting (𝑝 = 0.25).

Figure 11 :

 11 Figure 11: Relative improvement of SAIL over self-imitation (strSIL), based on both DQN (top) and IQN (bottom). On hard exploration games (in bold), SAIL-DQN provides a +72.2% average and +45.2% median relative improvement over strSIL-DQN, and SAIL-IQN a +16.0% average and +22.3% median relative improvement over strSIL-IQN.

Figure 12 :

 12 Figure 12: Curves on all games for DQN-based methods.

Figure 13 :

 13 Figure 13: Curves on all games for IQN-based methods.

Table 1 :

 1 Final scores of several off-policy algorithms based on DQN, in hard exploration games.

		DQN AL-DQN SAIL-DQN
	Alien	2586	3514	4769
	Amidar	1167	1380	879
	BankHeist	594	909	915
	Freeway	25	22	23
	Frostbite	392	2833	7912
	Gravitar	299	540	1292
	Hero	17056	7672	30382
	Montezuma's Revenge	0	0	0
	MsPacman	3405	3973	3879
	Pitfall!	-84	-100	-27
	PrivateEye	-114	153	10068
	Qbert	10178	13426	9310
	Solaris	1437	2216	855
	Venture	35	371	989
	WizardOfWor	2020	5930	6906
	Zaxxon	4713	6221	10364

Table 2 :

 2 Final scores of several off-policy algorithms based on IQN, in hard exploration games.

		IQN	AL-IQN SAIL-IQN
	Alien	4262	5318	6245
	Amidar	1131	1311	1752
	BankHeist	1081	1105	1037
	Freeway	34	34	34
	Frostbite	5231	10058	10345
	Gravitar	766	1213	1375
	Hero	28636	16804	30083
	Montezuma's Revenge	0	0	833
	MsPacman	4656	5340	4669
	Pitfall!	-19	-280	-42
	PrivateEye	357	49	4956
	Qbert	10802	11440	15189
	Solaris	2165	1461	992
	Venture	74	19	1525
	WizardOfWor	5700	10222	8933
	Zaxxon	12024	11843	15296

We didn't report results for ElevatorAction, whose ROM failed to load in our setup.

C51 scores

on Frostbite and 4000 on PrivateEye. Scores are available here.