Deep Reinforcement Learning at the Edge of the Statistical Precipice

In plain words

Reinforcement learning papers usually report how well a new method did by training it a handful of times, often three to ten, and then quoting one summary number, such as the median score across games. Those few training runs are noisy. Run the same method again with different random starts and the summary can move a lot, so a small gain may be luck. This paper shows that this happens in practice, using the Atari 100k benchmark as the main example.

The authors propose a more careful way to report results. Instead of a single number, report a range of plausible values, obtained by resampling the runs. Show the whole spread of scores with a curve that reads as "what share of runs beat each score level". Summarise the results with a middle-of-the-distribution average that is hard to move with a few extreme runs. Compare two methods by how often one beats the other, not only by the gap between their averages.

The paper also re-examines several earlier comparisons with these tools and finds that some of them look different once the uncertainty is shown. A free library, rliable, computes the recommended numbers and plots.

TL;DR

The paper argues that point estimates from a few runs (3 to 10 per task) hide statistical uncertainty, which it finds can dominate the differences reported between methods §1. It recommends stratified bootstrap confidence intervals, performance profiles built from score distributions over all runs eq. 1, and three aggregates: the interquartile mean, the optimality gap at a threshold of 1.0, and the average probability of improvement §4 tab. 1. Its Atari 100k case study shows that sample medians have high variance and bias that depends on the algorithm §3. The rliable code (Apache-2.0) implements the statistics. All results are author-reported.

Problem

Deep RL evaluation usually compares point estimates of aggregate scores, such as mean or median normalised score across tasks, computed from a few independent runs §1. The authors give three reasons this is unreliable. First, the variability of those estimates is large: five runs on each of more than fifty Arcade Learning Environment games would take over 1,000 GPU training days, so more runs per task are usually not feasible §1. Second, the Atari 100k benchmark, which trains for 100k steps on each of its 26 games (about two to three hours of play), amplifies the noise §1 §3. Third, evaluation protocols differ between papers, and choices such as taking a maximum over evaluations can inflate reported scores §3 app. A.4.

Method

Setting. A method is evaluated on M tasks with N independent runs each. Each raw score is linearly rescaled with two reference points, for example a random agent and an average human for Atari, which map to 0 and 1 §2. A run is treated as a random draw, so any statistic computed from the runs is itself a random variable §2. Mean and median are the sample aggregates over task means. The paper also defines the true mean and median, the limits as the number of runs grows §2.

Step 1. Interval estimates (stratified bootstrap). Resample the runs with replacement independently for each task, so that each bootstrap sample again has N runs per task (MN draws in total). Compute the statistic on each sample, repeat many times, and take the percentile interval §4.1. The paper says percentile intervals gave good coverage for median and IQM with as few as N = 10 runs §4.1. Basic, bias-corrected and BCa variants were also tested; the paper reports that BCa was less effective in this few-run regime app. A.5.

Step 2. Performance profiles (score distributions). Plot, for each threshold tau, the fraction of all MN runs that score above tau. This is the score distribution eq. 1. It is an unbiased estimator of the underlying distribution, and a single outlier run changes it by at most 1/(MN) §4.2. Shade a pointwise 95% band from the stratified bootstrap §4.2. The paper contrasts this with average-score distributions, which use per-task means and move in steps of 1/M; they are biased and have higher variance §4.2.

Step 3. Aggregate metrics. Compute three metrics from the pooled runs §4.3:

• Interquartile mean (IQM): drop the lowest and highest 25% of runs pooled over all tasks, then average the rest. The paper calls it the 25% trimmed mean and says it keeps floor(NM/2) runs. IQM is more statistically efficient than the median and has considerably less bias §4.3 app. A.2.
• Optimality gap: how far the algorithm falls short of a threshold gamma, with gamma = 1.0 by default, which is sensible for human-normalised or min-max normalised scores §4.3 app. A.7. The paper suggests plotting the gap across thresholds when no threshold is preferred app. A.7.
• Average probability of improvement: for algorithms X and Y, the average over tasks of P(X_m > Y_m), estimated with the Mann-Whitney U statistic over all run pairs, with ties counted as one half §4.3 app. A.7. It does not measure the size of an improvement §4.3.

Recommendations. Report interval estimates instead of point estimates, show performance profiles for variability across tasks, and use IQM as the main aggregate with optimality gap and probability of improvement alongside tab. 1 §4.

Case study protocol (Atari 100k). Five algorithms are compared: DER, OTR, DrQ(eps), CURL and SPR §3. For each algorithm, 100 independent runs were made on each of the 26 games, and a run's score is the average return over 100 evaluation episodes after training §3. Smaller run counts (3 to 100) are drawn by resampling this pool with replacement §3. The case study is used to show that median estimates have high variance and bias, that the run count needed for stable intervals is large, and that detecting a lift with medians needs many runs §3. It is an analysis of the protocol, not a new agent.

Pseudocode for the three aggregates, the score distribution and the bootstrap follows. Scores are an array of shape (N, M) for one algorithm, with runs along the first axis and tasks along the second.

# Stratified percentile bootstrap CI for an aggregate  [§4.1] [app. A.5]
# Input:  scores (N, M) per algorithm; metric(scores) -> float
# Output: lower and upper bound of the interval

def stratified_bootstrap_ci(scores, metric, reps=50000, size=0.95):
    # Shape of the score matrix: runs, then tasks  [§4.1]
    num_runs, num_tasks = scores.shape
    estimates = []
    for rep in range(reps):
        # Resample runs with replacement, independently for each task  [§4.1]
        indices = random_integers(num_runs, size=(num_runs, num_tasks))
        resample = scores[indices, arange(num_tasks)]  # (N, M)
        estimates.append(metric(resample))
    # Percentile interval over the bootstrap distribution  [§4.1] [app. A.5]
    low_q = (1.0 - size) / 2.0
    high_q = 1.0 - low_q
    return quantile(estimates, low_q), quantile(estimates, high_q)

# Interquartile mean over all runs of all tasks  [§4.3]
# Input:  scores (N, M)
# Output: scalar

def interquartile_mean(scores):
    # Pool every run of every task into one sorted list  [§4.3]
    pooled = sort(flatten(scores))
    # Number of values cut from each end: 25% of the pool  [§4.3]
    # Library cuts int(0.25 n) per end  [code: rliable/metrics.py#L70]
    cut = int(0.25 * len(pooled))
    # Mean of the middle 50% of the pooled runs  [§4.3]
    return mean(pooled[cut:len(pooled) - cut])

# Score distribution: share of all runs above each threshold  [§4.2] [eq. 1]
# Input:  scores (N, M), thresholds taus
# Output: one value per threshold, in [0, 1]

def score_distribution(scores, taus):
    # Strictly greater than tau, pooled over tasks and runs  [§4.2]
    return [mean(scores > tau) for tau in taus]

# Optimality gap below a threshold gamma (1.0 in the paper)  [§4.3] [app. A.7]
# Input:  scores (N, M), gamma
# Output: scalar, zero when every run reaches gamma

def optimality_gap(scores, gamma=1.0):
    # Clip each run at gamma, then measure the average shortfall  [§4.3]
    return gamma - mean(minimum(scores, gamma))

# Average probability that X beats Y on a random task  [§4.3] [app. A.7]
# Input:  scores_x (N, M), scores_y (K, M)
# Output: scalar in [0, 1]

def probability_of_improvement(scores_x, scores_y):
    num_runs_x, num_tasks = scores_x.shape
    num_runs_y = scores_y.shape[0]
    per_task = []
    for task in range(num_tasks):
        # U counts pairs with x above y; ties count one half  [app. A.7]
        pairs_won = mann_whitney_u(scores_x[:, task], scores_y[:, task])
        per_task.append(pairs_won / (num_runs_x * num_runs_y))
    # Average over tasks  [§4.3] [app. A.7]
    return mean(per_task)

The paper's own summary of the performance profile is one equation:

\hat{F}_X(\tau) = \frac{1}{M} \sum_{m=1}^{M} \frac{1}{N} \sum_{n=1}^{N} \mathbb{1}[x_{m,n} > \tau] eq. 1 §4.2

Hyperparameters

Results

Author-reported. Setup: Atari 100k (26 games, 100k steps, 5 algorithms, Tesla P100 GPUs) for the case study §3 app. A.2; Atari 200M, DM Control and Procgen for the re-evaluation §5. The paper gives most results as figures (score distributions, interval plots, rank plots), and the numbers below are the ones stated in the text. Figure values not stated in the text are not given here.

The paper also reports qualitative re-evaluation results. On Atari 200M, interval estimates for M-IQN and Dopamine Rainbow overlap strikingly on median §5. On DM Control, most algorithms do not consistently rank above the algorithms they claimed to improve upon §5. On Procgen, the authors report that a number of published improvements are only 50% to 70% likely §5.

Paper vs code

The official repository is google-research/rliable at the commit above (Apache-2.0). It implements the statistics and plots, not the Atari 100k agents. The agent code is in google/dopamine (labs/atari_100k), linked from the paper's appendix app. A.2. That repository was not cloned here, so the agent-level settings above are not checked against code.

Checked against rliable:

• Median and mean of task means match §2 metrics.py.
• Optimality gap is gamma minus the mean of the scores clipped at gamma, as described §4.3 metrics.py.
• Score distribution counts scores strictly above tau eq. 1 library.py.
• Probability of improvement uses a per-task Mann-Whitney test with alternative "greater", divided by NK, and returns 0.5 for identical task arrays app. A.7 metrics.py.
• Stratified bootstrap resamples runs with replacement independently for each task §4.1 library.py.
• Defaults: percentile method, 50,000 resamples for aggregates and 2,000 for profiles, 95% coverage app. A.5 library.py library.py.

Discrepancy:

• IQM run count. The paper says IQM keeps floor(NM/2) runs §4.3. The code calls scipy's trim_mean with proportion 0.25 over the flattened array metrics.py. In scipy's implementation, int(0.25 n) values are cut from each end, so n - 2 floor(n/4) values remain. This equals floor(n/2) only when n is divisible by 4. For example, with NM = 10 the paper keeps 5 runs and the code keeps 6. This is from reading scipy's implementation; I did not execute it here.

Pitfalls

• Two CI methods in the paper. The Atari 100k case study uses an m/n bootstrap for its medians §3, footnote, while the recommended method is the stratified percentile bootstrap §4.1. Do not mix the two when comparing numbers across the paper.
• Bootstrap intervals are too narrow at very small N. With 3 runs they underestimate the true 95% interval, so a higher nominal coverage may be needed §4.1.
• Per-game bootstrap needs far more runs. Per-game mean intervals reach the nominal coverage only with about 20 to 30 runs per game. Aggregate intervals over all games need far fewer app. A.3 app. A.5.
• Sample median bias depends on the algorithm. Its sign and size change with the algorithm being evaluated, so it cannot be corrected with a single offset §3.
• Maximum-over-evaluations protocols. Taking the best evaluation during training, or the best over hyperparameter settings, inflates scores. The paper says such results are generally incomparable with end-of-training results §3 app. A.4.
• Stratified bootstrap over tasks is a different question. Resampling tasks answers "how would the aggregate change with another set of tasks", and it gives much wider intervals app. A.5.
• Profile x-axis scaling changes the picture. The paper shows a non-linear axis that spreads the region where most runs lie. It also notes that the non-linear axis gives sub-linear utility of higher scores and prevents reading mean or IQM from the area under the curve app. A.6.
• Normalisation matters. The paper recommends min-max normalised scores for Procgen, because PPO-normalised means are dominated by a few tasks §5 app. A.7. It excludes record-normalised Atari scores because they come from much longer play than the 30-minute evaluation used there app. A.6.
• Probability of improvement does not show the size of a gain §4.3. The appendix also gives a significance-style reading (probability above 0.5 with an interval excluding 0.5, or an upper bound above 0.75) app. A.7. This sits uneasily with the paper's own advice to avoid significance tests [§2 remark].
• Bands are pointwise. The shaded 95% bands on a profile are computed separately at each threshold §4.2. Do not read them as a joint band for the whole curve.
• Bootstrap cost. The defaults are 50,000 resamples for aggregates and 2,000 for profiles app. A.5. The paper gives no runtime figures for them. Its case study needed about 18,200 training runs app. A.2.
• Reading median and mean off a profile. The median is the threshold where the profile crosses 0.5. For a non-negative score, the area under the profile gives the mean §4.2, figure caption.

Lineage

• Builds on: performance profiles of Dolan and Moré, from benchmarking optimisation software, adapted here to pooled RL runs §4.2. Stratified bootstrap of Efron, percentile and BCa intervals §4.1 app. A.5.
• Compared against: average-score distributions of the Arcade Learning Environment work §4.2; a probability-of-improvement profile from Recht et al. (2018), which compares each method with the best method using Welch's t-test §4.2 app. A.3.
• Superseded by: not known from this wiki.