Deep Reinforcement Learning at the Edge of the Statistical Precipice

Introduction

Research in artificial intelligence, and particularly deep reinforcement learning (RL), relies on evaluating aggregate performance on a diverse suite of tasks to assess progress. Quantitative evaluation on a suite of tasks, such as Atari games , reveals strengths and limitations of methods while simultaneously guiding researchers towards methods with promising results. Performance of RL algorithms is usually summarized with a point estimate of task performance measure, such as mean and median performance across tasks, aggregated over independent training runs.

A small number of training runs (Figure 1) coupled with high variability in performance of deep RL algorithms , often leads to substantial statistical uncertainty in reported point estimates. While evaluating more runs per task has been prescribed to reduce uncertainty and obtain reliable estimates , 3-10 runs are prevalent in deep RL as it is often computationally prohibitive to evaluate more runs. For example, 5 runs each on 50+ Atari 2600 games in ALE using standard protocol requires more than 1000 GPU training days . As we move towards more challenging and complex RL benchmarks (e.g., StarCraft ), evaluating more than a handful of runs will become increasingly demanding due to increased amount of compute and data needed to tackle such tasks. Additional confounding factors, such as exploration in the low-data regime, exacerbates the performance variability in deep RL – as seen on the Atari 100k benchmark – often requiring many more runs to achieve negligible statistical uncertainty in reported estimates.

Ignoring the statistical uncertainty in deep RL results gives a false impression of fast scientific progress in the field. It inevitably evades the question: “Would similar findings be obtained with new independent runs under different random conditions?” This could steer researchers towards superficially beneficial methods , often at the expense of better methods being neglected or even rejected early as such methods fail to outperform inferior methods simply due to less favorable random conditions. Furthermore, only reporting point estimates obscures nuances in comparisons and can erroneously lead the field to conclude which methods are state-of-the-art , ensuing wasted effort when applied in practice . Moreover, not reporting the uncertainty in deep RL results makes them difficult to reproduce except under the exact same random conditions, which could lead to a reproducibility crisis similar to the one that plagues other fields . Finally, unreliable results could erode trust in deep RL research itself .

In this work, we show that recent deep RL papers compare unreliable point estimates, which are dominated by statistical uncertainty, as well as exploit non-standard evaluation protocols, using a case study on Atari 100k (Section 3). Then, we illustrate how to reliably evaluate performance with only a handful of runs using a more rigorous evaluation methodology that accounts for uncertainty in results (Section 4). To exemplify the necessity of such methodology, we scrutinize performance evaluations of existing algorithms on widely used benchmarks, including the ALE (Atari 100k, Atari 200M), Procgen and DeepMind Control Suite , again revealing discrepancies in prior comparisons (Section 5). Our findings call for a change in how we evaluate performance in deep RL, for which we present a better methodology to prevent unreliable results from stagnating the field.

How do we reliably evaluate performance on deep RL benchmarks with only a handful of runs? As a practical solution that is easily applicable with 3-10 runs per task, we identify three statistical tools (Table 1) for improving the quality of experimental reporting. Since any performance estimate based on a finite number of runs is a random variable, we argue that it should be treated as such. Specifically, we argue for reporting aggregate performance measures using interval estimates via stratified bootstrap confidence intervals, as opposed to point estimates. Among prevalent aggregate measures, mean can be easily dominated by performance on a few outlier tasks, while median has high variability and zero performance on nearly half of the tasks does not change it. To address these deficiencies, we present more efficient and robust alternatives, such as interquartile mean, which are not unduly affected by outliers and have small uncertainty even with a handful of runs. Furthermore, to reveal the variability in performance across tasks, we propose reporting performance distributions across all runs. Compared to prior work , these distributions result in performance profiles that are statistically unbiased, more robust to outliers, and require fewer runs for smaller uncertainty.

Formalism

We consider the setting in which a reinforcement learning algorithm is evaluated on $M$ tasks. For each of these tasks, we perform $N$ independent runsA run can be different from using a fixed random seed. Indeed, fixing the seed may not be able to control all sources of randomness such as non-determinism of ML frameworks with GPUs (e.g., Figure A.13). which each provide a scalar, normalized score $x_{m,n}$, $m=1,\dots,M$ and $n=1,\dots,N$. These normalized scores are obtained by linearly rescaling per-task scoresOften the average undiscounted return obtained during an episode (see Sutton and Barto for an explanation of the reinforcement learning setting). based on two reference points; for example, performance on the Atari games is typically normalized with respect to a random agent and an average human, who are assigned a normalized score of 0 and 1 respectively . We denote the set of normalized scores by $x_{{1:M},{1:N}}$.

Confidence intervals (CIs) for a finite-sample score can be interpreted as an estimate of plausible values for the true score. A $\alpha\times 100\%$ CI computes an interval such that if we rerun the experiment and construct the CI using a different set of runs, the fraction of calculated CIs (which would differ for each set of runs) that contain the true score would tend towards $\alpha\times 100\%$, where $\alpha\in$ is the nominal coverage rate. 95% CIs are typically used in practice. If the true score lies outside the 95% CI, then a sampling event has occurred which had a probability of 5% of happening by chance.

Remark. Following Amrhein et al. , Wasserstein et al. , Romer , we recommend using confidence intervals for measuring the uncertainty in results and showing effect sizes (e.g., performance improvements over baseline) that are compatible with the given data. Furthermore, we emphasize using statistical thinking but avoid statistical significance tests (e.g., $p$-value < $0.05$) because of their dichotomous nature (significant vs. not significant) and common misinterpretations such as 1) lack of statistically significant results does not demonstrate the absence of effect (Figure 2, right), and 2) given enough data, any trivial effect can be statistically significant but may not be practically significant.

Case Study: The Atari 100k benchmark

We begin with a case study to illustrate the pitfalls arising from the naïve use of point estimates in the few-run regime. Our case study concerns the Atari 100k benchmark , an offshoot of the ALE for evaluating data-efficiency in deep RL. In this benchmark, algorithms are evaluated on only 100k steps (2-3 hours of game-play) for each of its 26 games, versus 200M frames in the ALE benchmark. Prior reported results on this benchmark have been computed mostly from 3 or 5 runs , and more rarely, 10 or 20 runs .

Our case study compares the performance of five recent deep RL algorithms, namely: (1) der and (2) otr , (3) drqdrq codebase uses non-standard evaluation hyperparameters. Instead, drq$(\varepsilon)$ corresponds to drq with standard $\varepsilon$-greedy parameters [14, Table 1] in ALE. See Appendix for more details. , (4) curl , and (5) spr . We chose these methods as representative of influential algorithms within this benchmark. Since good performance on one game can result in unduly high sample means without providing much information about performance on other games, it is common to measure performance on Atari 100k using sample medians. Refer to Appendix A.2 for more details about the experimental setup.

We investigate statistical variations in the few-run regime by evaluating 100 independent runs for each algorithm, where the score for a run is the average returns obtained in 100 evaluation episodes taking place after training. Each run corresponds to training one algorithm on each of the 26 games in Atari 100k. This provides us with $26\times 100$ scores per algorithm, which we then subsample with replacement to 3–100 runs. The subsampled scores are then used to produce a collection of point estimates whose statistical variability can be measured. We begin by using this experimental protocol to highlight statistical concerns regarding median normalized scores.

High variability in reported results. Our first observation is that the sample medians reported in the literature exhibit substantial variability when viewed as random quantities that depend on a small number of sample runs (Figure 2, left). This shows that there is a fairly large potential for drawing erroneous conclusions based on point estimates alone. As a concrete example, our analysis suggests that der may in fact be better than otr, unlike what the reported point estimates suggest. We conclude that in the few-run regime, point estimates are unlikely to provide definitive answers to the question: “Would we draw the same conclusions were we to re-evaluate our algorithm with a different set of runs?”

Statistical concerns cannot be satisfactorily addressed with few runs. While claiming improvements with 3 or fewer runs may naturally raise eyebrows, folk wisdom in experimental RL suggests that 20 or 30 runs are enough. By calculating 95% confidence intervalSpecifically, we use the $m/n$ bootstrap to calculate the interval between $[2.5^{th},97.5^{th}]$ percentiles of the distribution of sample medians (95% CIs). on sample medians for a varying number of runs (Figure 2, right), we find that this number is closer to 50–100 runs in Atari 100k – far too many to be computationally feasible for most research projects.

Changes in evaluation protocols invalidates comparisons to prior work. A typical and relatively safe approach for measuring the performance of an RL algorithm is to average the scores received in their final training episodes . However, the field has seen a number of alternative protocols used, including reporting the maximum evaluation score achieved during training or across multiple runs . A similar protocol is also used by curl and sunrise (Appendix A.4).

Results produced under alternative protocols involving maximum are generally incomparable with end-performance reported results. On Atari 100k, we find that the two protocols produce substantially different results (Figure 6), of a magnitude greater than the actual difference in score. In particular, evaluating der with curl’s protocol results in scores far above those reported for curl. In other words, this gap in evaluation procedures resulted in curl being assessed as achieving a greater true median than der, where our experiment gives strong support to der being superior. Similarly, we find that a lot of sunrise’s improvement over der can be explained by the change in evaluation protocol (Figure 6). Refer to Appendix A.4 for discussion on pitfalls of such alternative protocols.

Recommendations and Tools for Reliable Evaluation

Our case study shows that the increase in the number of runs required to address the statistical uncertainty issues is typically infeasible for computationally demanding deep RL benchmarks. In this section, we identify three tools for improving the quality of experimental reporting in the few-run regime, all aligned with the principle of accounting for statistical uncertainty in results.

We first reaffirm the importance of reporting interval estimates to indicate the range within which an algorithm’s aggregate performance is believed to lie. Concretely, we propose using bootstrap CIs with stratified sampling for aggregate performance, a method that can be applied to small sample sizes and is better justified than reporting sample standard deviations in this context. While prior work has recommended using bootstrap CIs for reporting uncertainty in single task mean scores with $N$ runs , this is less useful when $N$ is small (Figure A.18), as bootstrapping assumes that re-sampling from the data approximates sampling from the true distribution. We can do better by aggregating samples across tasks, for a total of $MN$ random samples.

To compute the stratified bootstrap CIs, we re-sample runs with replacement independently for each task to construct an empirical bootstrap sample with $N$ runs each for $M$ tasks from which we calculate a statistic and repeat this process many times to approximate the sampling distribution of the statistic. We measure the reliability of this technique in Atari 100k for variable $N$, by comparing the nominal coverage of 95% to the “true” coverage from the estimated CIs (Figure 6) for different bootstrap methods (see and Appendix A.5). We find that percentile CIs provide good interval estimates for as few as $N=10$ runs for both median and IQM scores (Section 4.3).

2 Performance Profiles

Most deep RL benchmarks yield scores that vary widely between tasks and may be heavy-tailed, multimodal, or possess outliers (e.g., Figure A.14). In this regime, both point estimates, such as mean and median scores, and interval estimates of these quantities paint an incomplete picture of an algorithm’s performance [24, Section 3]. Instead, we recommend the use of performance profiles , commonly used in benchmarking optimization software. While performance profiles from Dolan and Moré correspond to empirical cumulative distribution functions without any uncertainty estimates, profiles proposed herein visualize the empirical tail distribution function (Section 2) of a random score (higher curve is better), with pointwise confidence bands based on stratified bootstrap.

By representing the entire set of normalized scores $x_{1:M,1:N}$ visually, performance profiles reveal performance variability across tasks much better than interval estimates of aggregate metrics. Although tables containing per-task mean scores and standard deviations can reveal this variability, such tables tend to be overwhelming for more than a few tasks.In addition, standard deviations are sometimes omitted from tables due to space constraints. In addition, performance profiles are robust to outlier runs and insensitive to small changes in performance across all tasks .

In this paper, we propose the use of a performance profile we call run-score distributions or simply score distributions (Figure 7, right), particularly well-suited to the few-run regime. A score distribution shows the fraction of runs above a certain normalized score and is given by

One advantage of the score distribution is that it is an unbiased estimator of the underlying distribution $F(\tau)=\tfrac{1}{N}\sum_{m=1}^{M}F_{m}(\tau)$. Another advantage is that an outlier run with extremely high score can change the output of score distribution for any $\tau$ by at most a value of $\tfrac{1}{MN}$.

It is useful to contrast score distributions to average-score distributions, originally proposed in the context of the ALE as a generalization of the median score. Average-score distributions correspond to the performance profile of a random variable ${\bm{\bar{}}{X}}$, $\hat{F}_{\bar{X}}(\tau)=\hat{F}(\tau;{\bar{x}}_{1:M})$, which shows the fraction of tasks on which an algorithm performs better than a certain score. However, such distributions are a biased estimate of the thing they seek to represent. Run-score distributions are more robust than average-score distributions, as they are a step function in $1/MN$ versus $1/M$ intervals, and typically has less variance: $\sigma_{X}^{2}=\tfrac{1}{M^{2}N}\sum_{m=1}^{M}F_{m}(\tau)(1-F_{m}(\tau))$ versus $\sigma_{\bar{X}}^{2}=\tfrac{1}{M^{2}}\sum_{m=1}^{M}F_{{\bar{X}_{m}}}(\tau)(1-F_{{\bar{X}_{m}}}(\tau))$. Figure 7 illustrates these differences.

3 Robust and Efficient Aggregate Metrics

Performance profiles allow us to compare different methods at a glance. If one curve is strictly above another, the better method is said to stochastically dominateA random variable $X$ has stochastic dominance over random variable $Y$ if $P(X>\tau)\geq P(Y>\tau)$ for all $\tau$, and for some $\tau$, $P(X>\tau)>P(Y>\tau)$. the other . In RL benchmarks with a large number of tasks, however, stochastic dominance is rarely observed: performance profiles often intersect at multiple points. Finer quantitative comparisons must therefore entail aggregate metrics.

We can extract a number of aggregate metrics from score distributions, including median (mixing runs and tasks) and mean normalized scores (matching our usual definition). As we already argued that these metrics are deficient, we now consider interesting alternatives also derived from score distributions.

As an alternative to median, we recommend using the interquartile mean (IQM). Also called 25% trimmed mean, IQM discards the bottom and top $25\%$ of the runs and calculates the mean score of the remaining 50% runs (=$\lfloor NM/2\rfloor$ for $N$ runs each on $M$ tasks). IQM interpolates between mean and median across runs, which are 0% and almost $50\%$ trimmed means respectively. Compared to sample median, IQM is a better indicator of overall performance as it is calculated using 50% of the combined runs while median only depends on the performance ordering across tasks and not on the magnitude except at most 2 tasks. For example, zero scores on nearly half of the tasks does not affect the median while IQM exhibits a severe degradation. Compared to mean, IQM is robust to outliers, yet has considerably less bias than median (Figure A.17). While median is more robust to outliers than IQM, this robustness comes at the expense of statistical efficiency, which is crucial in the few-run regime: IQM results in much smaller CIs (Figure 2 (right) and 6) and is able to detect a given improvement with far fewer runs (Figures 6 and A.16).

As a robust alternative to mean, we recommend using the optimality gap: the amount by which the algorithm fails to meet a minimum score of $\gamma=1.0$ (orange region in Figure 8). This assumes that a score of 1.0 is a desirable target beyond which improvements are not very important, for example when the aim is to obtain human-level performance [e.g., 23, 3]. Naturally, the threshold $\gamma$ may be chosen differently, which we discuss further in Appendix A.7.

If one is interested in knowing how robust an improvement from an algorithm $X$ over an algorithm $Y$ is, another possible metric to consider is the average probability of improvement – this metric shows how likely it is for $X$ to outperform $Y$ on a randomly selected task. Specifically, $P(X>Y)=\tfrac{1}{M}\sum_{m=1}^{M}P(X_{m}>Y_{m})$, where $P(X_{m}>Y_{m})$ (Equation A.2) is the probability that $X$ is better than $Y$ on task $m$. Note that, unlike IQM and optimality gap, this metric does not account for the size of improvement. While finding the best aggregate metric is still an open question and is often dependent on underlying normalized score distribution, our proposed alternatives avoid the failure modes of prevalent metrics while being robust and requiring fewer runs to reduce uncertainty.

Re-evaluating Evaluation on Deep RL Benchmarks

Arcade Learning Environment. Training RL agents for 200M frames on the ALE is the most widely recognized benchmark in deep RL. We revisit some popular methods which demonstrated progress on this benchmark and reveal discrepancies in their findings as a consequence of ignoring the uncertainty in their results (Figure 9). For example, DreamerV2 exhibits a large amount of uncertainty in aggregate scores. While M-IQN claimed better performance than Dopamine RainbowDopamine Rainbow differs from that of Hessel et al. by not including double DQN, dueling architecture and noisy networks. Also, results in were reported using a single run without sticky actions. in terms of median normalized scores, their interval estimates strikingly overlap. Similarly, while C51 is considered substantially better than DQN , the interval estimates as well as performance profiles for DQN (Adam) and C51 overlap significantly.

Figure 9 reveals an interesting limitation of aggregate metrics: depending on the choice of metric, the ordering between algorithms changes (e.g., Median vs. IQM). The inconsistency in ranking across aggregate metrics arises from the fact that such metrics only capture a specific aspect of overall performance across tasks and runs. Additionally, the change of algorithm ranking between optimality gap and IQM/median scores reveal that while recent algorithms typically show performance gains relative to humans on average, their performance seems to be worse on games below human performance. Since performance profiles capture the full picture, they would often illustrate why such inconsistencies exist. For example, optimality gap and IQM can be both read as areas in the profile (Figure 8). The performance profile in Figure 10 (left) illustrates the nuances present when comparing different algorithms. For example, IQN seems to be better than Rainbow for $\tau\geq 2$, but worse for $\tau<2$. Similarly, the profiles of DreamerV2 and M-IQN for $\tau<8$ intersect at multiple points. To compare sample efficiency of the agents, we also present their IQM scores as a function of number of frames in Figure 10 (right).

DeepMind Control Suite. Recent continuous control papers benchmark performance on 6 tasks in DM Control at 100k and 500k steps. Typically, such papers claim improvement based on higher mean scores per task regardless of the variability in those scores. However, we find that when accounting for uncertainty in results, most algorithms do not consistently rank above algorithms they claimed to improve upon (Figure 11(c) and 11(b)). Furthermore, there are huge overlaps in 95% CIs of mean normalized scores for most algorithms (Figure 11(a)). These findings suggest that a lot of the reported improvements are spurious, resulting from randomness in the experimental protocol.

Procgen benchmark. Procgen is a popular benchmark, consisting of 16 diverse tasks, for evaluating generalization in RL. Recent papers report mean PPO-normalized scores on this benchmark to emphasize the gains relative to PPO as most methods are built on top of it. However, Figure 12 (left) shows that PPO-normalized scores typically have a heavy-tailed distribution making the mean scores highly dependent on performance on a small fraction of tasks. Instead, we recommend using normalization based on the estimated minimum and maximum scores on ProcGen and reporting aggregate metrics based on such scores (Figure A.32). While publications sometimes make binary claims about whether they improve over prior methods, such improvements are inherently probabilistic. To reveal this discrepancy, we investigate the following question: “What is the probability that an algorithm which claimed improvement over a prior algorithm performs better than it?” (Figure 12, right). While this probability does not distinguish between two algorithms which uniformly improve on all tasks by 1% and 100%, it does highlight how likely an improvement is. For example, there is only a $40-50$% chance that UCB-DrAC improves upon PLR . We note that a number of improvements reported in the existing literature are only $50-70$% likely.

Discussion

We saw, both in our case study on the Atari 100k benchmark and with our analysis of other widely-used RL benchmarks, that statistical issues can have a sizeable influence on reported results, in particular when point estimates are used or evaluation protocols are not kept constant within comparisons. Despite earlier calls for more experimental rigor in deep RL (discussed in Appendix A.3), our analysis shows that the field has not yet found sure footing in this regards.

In part, this is because the issue of reproducibility is a complex one; where our work is concerned with our confidence about and interpretation of reported results (what Goodman et al. calls results reproducibility), others have highlighted that there might be missing information about the experiments themselves (methods reproducibility). We remark that the problem is not solved by fixing random seeds, as has sometimes been proposed , since it does not really address the question of whether an algorithm would perform well under similar conditions but with different seeds. Furthermore, fixed seeds might benefit certain algorithms more than others. Nor can the problem be solved by the use of dichotomous statistical significance tests, as discussed in Section 2.

One way to minimize the risks associated with statistical effects is to report results in a more complete fashion, paying close attention to bias and uncertainty within these estimates. To this end, our recommendations are summarized in Table 1. To further support RL researchers in this endeavour, we released an easy-to-use Python library, rliable along with a Colab notebook for implementing our recommendations, as well as all the individual runs used in our experimentsColab: bit.ly/statistical_precipice_colab. Individual runs: gs://rl-benchmark-data.. Again, we emphasize the importance of published papers providing results for all runs to allow for future statistical analyses.

A barrier to adoption of evaluation protocols proposed in this work, and more generally, rigorous evaluation, is whether there are clear incentives for researchers to do so, as more rigor generally entails more nuanced and tempered claims. Arguably, doing good and reproducible science is one such incentive. We hope that our findings about erroneous conclusions in published papers would encourage researchers to avoid fooling themselves, even if that requires tempered claims. That said, a more pragmatic incentive would be if conferences and reviewers required more rigorous evaluation for publication, e.g., NeurIPS 2021 checklist asks whether error bars are reported. Moving towards reliable evaluation is an ongoing process and we believe that this paper would greatly benefit it.

Given the substantial influence of statistical considerations in experiments involving 40-year old Atari 2600 video games and low-DOF robotic simulations, we argue that it is unlikely that an increase in available computation will resolve the problem for the future generation of RL benchmarks. Instead, just as a well-prepared rock-climber can skirt the edge of the steepest precipices, it seems likely that ongoing progress in reinforcement learning will require greater experimental discipline.

Societal Impacts

This paper calls for statistical sophistication in deep RL research by accounting for statistical uncertainty in reported results. However, statistical sophistication can introduce new forms of statistical abuses and monitoring the literature for such abuses should be an ongoing priority for the research community. Moving towards reliable evaluation and reproducible research is an ongoing process and this paper only partly addresses it by providing tools for more reliable evaluation. That said, while accounting for uncertainty in results is not a panacea, it provides a strong foundation for trustworthy results on which the community can build upon, with increased confidence. In terms of broader societal impact of this work, we do not see any foreseeable strongly negative impacts. However, this paper could positively impact society by constituting a step forwards in rigorous few-run evaluation regime, which reduces computational burden on researchers and is ‘‘greener’’ than evaluating a large number of runs.

Acknowledgments

We thank Xavier Bouthillier, Dumitru Erhan, Marlos C. Machado, David Ha, Fabio Viola, Fernando Diaz, Stephanie Chan, Jacob Buckman, Danijar Hafner and anonymous NeurIPS’ reviewers for providing valuable feedback for an earlier draft of this work. We also acknowledge Matteo Hessel, David Silver, Tom Schaul, Csaba Szepesvári, Hado van Hasselt, Rosanne Liu, Simon Kornblith, Aviral Kumar, George Tucker, Kevin Murphy, Ankit Anand, Aravind Srinivas, Matthew Botvinick, Clare Lyle, Kimin Lee, Misha Laskin, Ankesh Anand, Joelle Pineau and Braham Synder for helpful discussions. We also thank all the authors who provided individual runs for their corresponding publications. We are also grateful for general support from Google Research teams in Montréal and elsewhere.

References

Appendix A Appendix

Colab notebook for producing and analyzing performance profiles, robust aggregate metrics, and interval estimates based on stratified bootstrap CIs, as well as replicating the results in the paper can be found at bit.ly/statistical_precipice_colab.

Individual runs for Atari 100k. We released the 100 runs per game for each of the 6 algorithms in the case study in a public cloud bucket at gs://rl-benchmark-data/atari_100k.

Individual runs for ALE, Procgen and DM Control. For ALE, we used the individual runs from Dopamine baselines except for DreamerV2 , REM and M-IQN , for which the individual run scores were obtained from the corresponding authors. We release all the individual run scores as well as final scores for ALE at gs://rl-benchmark-data/ALE. The Procgen results were obtained from the authors of IDAAC and MixReg and are released at gs://rl-benchmark-data/procgen. For DM ControlDreamer results on DM control, obtained from the corresponding author, are based on hyperparameters tuned for sample-efficiency. Compared to the original paper , the actor-critic learning rates were increased to $3e-4$, the amount of free bits to 1.5, the training frequency, and the amount of pre-training to 1k steps on 10k randomly collected frames. The imagination horizon was decreased to 10., all the runs were obtained from the corresponding authors and are released at gs://rl-benchmark-data/dm_control.

See agarwl.github.io/rliable for a website for the paper.

A.2 Atari 100k: Additional Details and Results

Code. Due to unavailability of open-source code for der, and otr for Atari 100k, we re-implemented these algorithms using Dopamine , a reproducible deep RL framework. For curl and spr, we used the open-source code released by the authors while for drq, we used the source-code obtained from the authors. Our code for Atari 100k experiments is open-sourced as part of the Dopamine library under the labs/atari_100k folder. We also released a JAX implementation of the full Rainbow in Dopamine.

Hyperparameters. All algorithms build upon the Rainbow architecture and we use the exact same hyperparameters specified in the corresponding publication unless specified otherwise. Akin to drq and spr, we used $n$-step returns with $n=10$ instead of $n=20$ for der. drq codebase uses non-standard evaluation hyperparameters, such as a 5% probability of selecting random actions during evaluation ($\varepsilon$-eval$=0.05$). drq$(\varepsilon)$ differs drq in terms of using standard $\varepsilon$-greedy parameters [14, Table 1] including training $\varepsilon$ decayed to 0.01 rather than 0.1 and evaluation $\varepsilon$ set to 0.001 instead of 0.05. Refer to the gin configurations in labs/atari_100k/configs for more details.

Compute. For the case study on Atari 100k, we used Tesla P100 GPUs for all the runs. Each run spanned about 3-5 hours depending on the algorithm, and we ran a total of 100 runs / game $\times$ 26 games/algorithm $\times$ 6 algorithms = 15,600 runs. Additionally, we ran an additional 100 runs per game for der to compute a good approximation of point estimates for aggregate scores, which increases the total number of runs by 2600. Overall, we trained and evaluated 18,200 runs, which roughly amounts to 2400 days -- 3600 days of GPU training.

Comparing performance of two algorithms. When confidence intervals (CIs) overlap for two random variables $X$ and $Y$ overlap, we estimate the $95\%$ CIs for $X-Y$ to account for uncertainty in their difference (Figure A.16). For example, when using 5 runs, the median score improvement from drq$(\varepsilon)$ over der is estimated to lie within $(0.01,0.21)$ while that of SPR over DrQ lies within $(-0.09,0.18)$. Furthermore, while improvement from SPR over DER with $5$ to $15$ runs is not statistically significant, claiming ‘‘no improvement’’ would be misleading as evaluating more runs indeed shows that the improvement is significant.

Analyzing efficiency and bias of IQM. Theoretically, trimmed means, are known to have higher statistical efficiency for mixed distributions and heavy-tailed distributions (Cauchy distribution), at the cost of lower efficiency for some other less heavily-tailed distributions (normal distribution) than mean, as shown by the seminal work of Tukey . Empirically, on Atari 100k, IQM provides good statistically efficiency among trimmed estimators across different algorithms (Figure A.16) as well as has considerably small bias than median (c.f. Figure A.17 vs. Figure 3).

A.3 Related work on rigorous evaluation in deep RL

While prior work highlights various reproducibility issues in policy-gradient methods, this paper focuses specifically on the reliability of evaluation procedures on RL benchmarks and provides an extensive analysis on common deep RL algorithms on widely-used benchmarks.

For more rigorous performance comparisons on a single RL task, Henderson et al. , Colas et al. provide guidelines for statistical significance testing while Colas et al. focuses on determining the minimum number of runs needed for such comparisons to be statistically significant. Instead, this paper focuses on reliable comparisons on a suite of tasks and mainly recommends reporting stratified bootstrap CIs due to the dichotomous nature and wide misinterpretation of statistical significance tests (see Remark in Section 2). Henderson et al. , Colas et al. also discuss bootstrap CIs but for reporting single task mean scores – however, 3-5 runs is a small sample size for bootstrapping: on Atari 100k, for achieving true coverage close to 95%, such CIs require at least 20-30 runs per task (Figure A.18) as opposed to 5-10 runs for stratified bootstrap CIs for aggregate metrics like median, mean and IQM (Figure A.19).

Chan et al. propose metrics to measure the reliability of RL algorithms in terms of their stability during training and their variability and risk in returns across multiple episodes. While this paper focuses on reliability of evaluation itself, performance profiles showing the tail distribution of episodic returns, applicable for even a single task with multiple runs, can be useful for measuring reliability of an algorithm’s performance.

Jordan et al. propose a game-theoretic evaluation procedure for ‘‘complete’’ algorithms that do not require any hyperparameter tuning and recommend evaluating between 1,000 to 10,000 runs per task to detect statistically significant results. Instead, this work focuses on reliably evaluating performance obtained after the hyperparameter tuning phase, even with just a handful of runs. That said, run-score distributions based on runs with different hyperparameter configurations might reveal sensitivity to hyperparameter tuning.

An alternative to score distributions, proposed by Recht , is to replace scores in a performance profile by the probability that average task scores of a given method outperforms the best method (among a given set of methods), computed using the Welsh’s t-test . However, this profile is (1) also a biased estimate, (2) less robust to outlier runs, (3) is insensitive to the size of performance differences, i.e., two methods that are uniformly 1% and 100% worse than the best method are assigned the same probability, (4) is only sensible when task score distributions are Gaussian, as required by Welsh’s t-test, and finally, (5) the ranking of methods depends on the specific set of methods being compared in such profiles.

A.4 Non-standard Evaluation Protocols Involving Maximum

Even when adequate number of runs are used, the use of non-standard evaluation protocols can result in misleading comparisons. Such protocols commonly involve the insertion of a maximum operation inside evaluation, across or within runs, leading to a positive bias in reported scores compared to the standard approach without the maximum.

One seemingly reasonable but faulty argument for maximum across runs is that in a real-world application, one might wish to run an stochastic algorithm $A$ for $N$ runs and then select the best result. However, in this case, we are not discussing $A$ but another algorithm $A^{N}$, which evaluates $N$ random runs of $A$. If we are interested in $A^{N}$, taking maximum over $N$ runs only considers a single run of $A^{N}$. Since $A^{N}$ is itself stochastic, proper experimental methodology requires multiple runs of $A^{N}$. Furthermore, because learning curves are not in general monotonic, results produced under the maximum-during-training protocol are in general incomparable with end-performance reported results. In addition, such protocols introduces an additional source of positive statistical bias, since the maximum of a set of random variables is a biased estimate of their true maximum.

On Atari 100k, curl and sunrise used non-standard evaluation protocols. curl reported the maximum performance over 10 different evaluations during training. As a result, natural variability in both evaluation itself and in the agent’s performance during training contribute to overestimation. Applying the same procedure to curl’s baseline DER leads to scores far above those reported for curl (Figure 6, ‘‘der (curl’s protocol)’’). In the case of sunrise, the maximum was taken over eight hyperparameter configurations separately for each game, with three runs each. We simulate this procedure for der (also sunrise’s baseline), using a dummy hyperparameter. We find that a lot of sunrise’s improvement over der can be explained by this evaluation scheme (Figure 6, ‘‘der (sunrise’s protocol)’’).

A.5 Bootstrap Confidence Intervals

Bootstrap CIs for a real parameter $\theta$ are based on re-sampling with replacement from a fixed set of $K$ samples to create a bootstrap sample of size $K$ and compute the bootstrap parameter $\theta^{*}$ and repeating this process a numerous to create the bootstrap distribution over $\theta^{*}$. In this paper, we evaluate the following non-parametric methods for constructing CIs for $\theta$ using this bootstrap distribution:

Basic bootstrap, also known as the reverse percentile interval, uses the empirical quantiles from the bootstrap distribution of the parameter ${\widehat{\delta}}=\hat{\theta}-\theta$ for defining the $\alpha\times 100\%$ CI: $(2{\widehat{\theta\,}}-\theta_{(\alpha/2)}^{*},2{\widehat{\theta\,}}-\theta_{(1-\alpha/2)}^{*})$, where $\theta_{(1-\alpha/2)}^{*}$ denotes the $1-\alpha/2$ percentile of the bootstrapped parameters $\theta^{*}$ and ${\widehat{\theta}}$ is the empirical estimate of the parameter based on finite samples.

Percentile bootstrap. The percentile bootstrap proceeds in a similar way to the basic bootstrap, using percentiles of the bootstrap distribution, but with a different formula: $(\theta_{(1-\alpha/2)}^{*},\theta_{(\alpha/2)}^{*})$ for defining the $\alpha\times 100\%$ CI.

Bias-corrected (bc) bootstrap – adjusts for bias in the bootstrap distribution.

Bias-corrected and accelerated (bca) bootstrap, by Efron , adjusts for both bias and skewness in the bootstrap distribution. This approach is typically considered to be more accurate and has better asymptotic properties. However, we find that it is not as effective as percentile methods in the few-run deep RL regime.

More technical details about bootstrap CIs can be found in . We find that bootstrap CIs for mean scores per game (computed using $N$ random samples) require many more runs than aggregate scores (computed using $MN$ random samples) for achieving true coverage close to the nominal coverage of 95% (c.f. Figure A.18 vs. Figure A.19).

Number of bootstrap re-samples. Unless specified otherwise, for computing uncertainty estimates using stratified bootstrap, we use 50,000 samples for aggregate metrics and 2000 samples for pointwise confidence bands and average probability of improvement. Using larger number of samples then the above specified values might result in more accurate uncertainty estimates but would be slower to compute.

Stratified bootstrap over tasks and runsThanks to David Silver and Tom Schaul for suggesting stratified bootstrapping over tasks.. With access to only 1-2 runs per task, stratified bootstrapping can be done over tasks (Figure A.22), to answer the question: ‘‘If I repeat the experiment with a different set of tasks, what performance an algorithm is I expected to get?’’ It shows the sensitivity of the aggregate score to a given task and can also be viewed as an estimate of performance if we had used a larger unknown population of tasks [e.g., 94, 90]. Compared to the interval estimates in Figure 9, bootstraping over tasks results in much larger uncertainty due to high variations in performance across different tasks (e.g., easy vs hard exploration tasks).

A.6 Visualizing score distributions

Choice of Normalization. We used existing normalization schemes which are prevalent on benchmarks including human normalized scores for Atari 100k and ALE, PPO normalized scores and Min-Max normalized scores for Procgen, and Min-Max Normalized scores (minimum scores set to zero) scores for DM Control. We do not use record normalized scores for ALE (Figure A.27) in the main text as ALE results are reported by evaluating agents for 30 minutes of game-play as opposed to record scores which were obtained using game play spanning numerous hours (e.g., Toromanoff et al. recommend evaluating agents for 100 hours). Furthermore, we recommend using Min-Max Normalized scores for Procgen instead of PPO Normalized scores (Figure A.21) to allow for comparisons to methods which do not build upon PPO .

Scaling x-axis in score distributions. Figure A.23 (right) and Figure A.24 (right) shows an alternative for visualizing score distributions where we simply scale the $x$-axis depending on the fraction of runs in a given region. This scaling more clearly shows the differences in algorithms by focusing on the regions where most of the runs lieThanks to Mateo Hessel for suggesting this visualization scheme and the difficulty progress metric..

A.7 Aggregate metrics: Additional visualizations and details

Alternative aggregate metrics. Different aggregate metrics emphasize different characteristics and no single metric would be sufficient for evaluating progress. While score distributions provide a full picture of evaluation results, we provide suggestions for alternative aggregate metrics to highlight other important aspects of performance across different tasks and runs.

Difficulty Progress: One might be more interested in evaluating progress on the hardest tasks on a benchmark . In addition to optimality gap which emphasizes all tasks below a certain performance level, a possible aggregate measure to consider is the mean scores of the bottom 25% of the runs (Figure A.25, left), which we call Difficulty Progress (DP-25).

Superhuman Probability: We also recommend reporting probability of being superhuman, $P(X>1)$, given by the number of runs above average human performance (Figure A.25, right) instead of number of games above average human performance , a commonly used metric on ALE.

Choice of $\gamma$ for optimality gap. When using min-max normalized scores or human-normalized scores, setting a score threshold of $\gamma=1$ is sensible as it considers performance on games below maximum performance or human performance respectively. If there is no preference for a specific threshold, an alternative is to consider a curve of optimality gap as the threshold is varied, as shown in Figure A.27, which shows how far from optimality an algorithm is given any threshold -- a small value of optimality gaps for all achievable score thresholds is desirable.

Probability of improvement. To compute the probability of improvement for a task $m$ for algorithms $X$ and $Y$ with $N$ and $K$ runs respectively, we use the Mann-Whitney U-statistic , that is,

Please note that if the probability of improvement is higher than 0.5 and the CIs do not contain 0.5, then the results are statistically significant. Furthermore, if the upper CI is higher than a threshold of 0.75, then the results are said to be statistically meaningful as per the Neyman-Pearson statistical testing criterion by Bouthillier et al. . We show the average probability of improvement metrics for Atari 100k and ALE in Figure A.29 and Figure A.28. These estimates show how likely an algorithm improves upon another algorithm.

Aggregate metrics on Atari 100k, Procgen and DM Control as well as ranking on individual tasks on DM Control are visualized in Figures A.30--A.33.