Reinforcement learning evaluation

Overview

A deep RL method is usually scored on several tasks, with only three to ten independent training runs per task, and the paper reports one summary number for the whole set. The cited paper argues that such point estimates hide statistical uncertainty, which can be as large as the gaps papers report between methods 2108.13264 §1. Its benchmark is Atari 100k, where the noise is largest 2108.13264 §3.

This page covers how results are reported, not how the reward is designed. Before a reward is trained on, its soundness is a separate question. A review of driving rewards finds no systematic validation method, only a manual set of sanity checks, and proposes an automatic framework as future work 2405.01440 §5.3. The review runs no experiments, so it gives no evidence on how well any check works.

The shared idea of every variant below: treat each training run as a random draw, so that any statistic over the runs is itself random. Report the uncertainty next to the number, or show the whole distribution of runs 2108.13264 §2. Scores are first rescaled so that two reference points, for example a random agent and an average human on Atari, map to 0 and 1 2108.13264 §2.

Variants

Stratified bootstrap confidence intervals

Resample the runs with replacement, separately for each task, so each bootstrap sample keeps N runs per task. Recompute the aggregate on each sample and take the percentile interval 2108.13264 §4.1. The paper reports good coverage for the median and the interquartile mean with as few as N = 10 runs 2108.13264 §4.1. The BCa variant was less effective in this few-run setting 2108.13264 app. A.5. With N = 3, intervals come out too narrow, so a higher nominal coverage may be needed 2108.13264 §4.1. Card: Deep Reinforcement Learning at the Edge of the Statistical Precipice.

Performance profiles (score distributions)

Plot, for each threshold tau, the fraction of all runs over all tasks that score above tau 2108.13264 eq. 1. One outlier run moves the curve by at most 1/(MN), where M is the number of tasks and N the runs per task 2108.13264 §4.2. The shaded 95% band is pointwise, one band per threshold, not a joint band for the whole curve 2108.13264 §4.2. The paper contrasts this with average-score distributions, which use per-task means, are biased and have higher variance 2108.13264 §4.2. The x-axis scale affects how the curve reads; a non-linear axis can spread the region where most runs lie 2108.13264 app. A.6.

Interquartile mean (IQM)

Pool all runs of all tasks, discard the lowest and highest 25%, and average the rest 2108.13264 §4.3. The paper finds it more statistically efficient than the median, with considerably less bias 2108.13264 app. A.2. The paper recommends it as the main aggregate 2108.13264 tab. 1. See Contradictions for the run count.

Optimality gap

Measure the average shortfall below a threshold gamma, with each run clipped at gamma 2108.13264 §4.3. The default gamma is 1.0, which suits human- or min-max-normalised scores 2108.13264 app. A.7. With no preferred threshold, the paper suggests plotting the gap over a range of thresholds 2108.13264 app. A.7.

Average probability of improvement

For two algorithms X and Y, average over tasks the probability that a run of X beats a run of Y. The paper estimates each task's value with the Mann-Whitney U statistic over all run pairs, counting ties as one half 2108.13264 §4.3 2108.13264 app. A.7. The metric does not measure how large an improvement is 2108.13264 §4.3.

When to use which

The paper's default settings are 50,000 bootstrap resamples for aggregates and 2,000 for profiles and probability of improvement 2108.13264 app. A.5. It gives no runtime figures for them.

Implementation sketch

Python-flavoured pseudocode of the common core. Scores have shape (N, M): runs along the first axis, tasks along the second. The bootstrap accepts any metric.

# Stratified percentile bootstrap for any aggregate  [arxiv:2108.13264 §4.1]
# Input:  scores (N, M), metric(scores) -> float
# Output: lower and upper interval bounds

def stratified_bootstrap_ci(scores, metric, reps=50000, level=0.95):
    num_runs, num_tasks = scores.shape
    estimates = []
    for rep in range(reps):
        # Draw run indices with replacement, separately for each task  [§4.1]
        idx = random_integers(num_runs, size=(num_runs, num_tasks))
        resample = scores[idx, arange(num_tasks)]
        estimates.append(metric(resample))
    # Percentile interval over the bootstrap estimates  [§4.1] [app. A.5]
    tail = (1.0 - level) / 2.0
    return quantile(estimates, tail), quantile(estimates, 1.0 - tail)

# Interquartile mean over all runs of all tasks  [arxiv:2108.13264 §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))
    # Cut 25% of the pool from each end  [§4.3]
    cut = int(0.25 * len(pooled))
    return mean(pooled[cut:len(pooled) - cut])

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

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

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

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

# Average probability that X beats Y on a 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):
    per_task = []
    for task in range(scores_x.shape[1]):
        # Mann-Whitney U over all run pairs; ties count one half  [app. A.7]
        u = mann_whitney_u(scores_x[:, task], scores_y[:, task])
        per_task.append(u / (scores_x.shape[0] * scores_y.shape[0]))
    # Average over tasks  [§4.3] [app. A.7]
    return mean(per_task)

Where the variants differ: only the metric and the trimming. The bootstrap and the profile are shared across all of them.

Contradictions

None between the two cards: 2405.01440 reports no results, so it cannot disagree with the numbers in 2108.13264. Inside 2108.13264, its stated run count for the interquartile mean differs from its released code. The paper says the IQM keeps floor(NM/2) runs 2108.13264 §4.3. The released rliable library calls scipy's trim_mean with proportion 0.25 over the flattened array. Per the card's reading of that code, which was not run and whose source is not in this repository, scipy cuts int(0.25 n) values from each end. That leaves n - 2 floor(n/4) runs, which equals floor(n/2) only when NM is divisible by 4. For NM = 10, the paper keeps 5 runs and the library 6. Check the result on your own data before you rely on either count.

Papers

• Deep Reinforcement Learning at the Edge of the Statistical Precipice: stratified bootstrap intervals, performance profiles, IQM, optimality gap and probability of improvement, with an Atari 100k case study. Released as the rliable library (Apache-2.0).
• A Review of Reward Functions for Reinforcement Learning in the context of Autonomous Driving: reviews the reward terms of RL driving papers and notes the lack of reward validation. Runs no experiments, so it adds no evaluation numbers.