Principled Analysis of Deep Reinforcement Learning Evaluation and Design Paradigms

• Earlier algorithms were designed and tested with two hundred million training frames, while recent work targets one hundred thousand environment interactions, and low-data performance comparisons helped drive new research fields.Source: §1 · p. 1
• The implicit assumption that algorithm performance changes monotonically across sample-complexity regimes shapes canonical choices, yielding incorrect justifications and conclusions that misdirect research.Source: §1 · pp. 1–2
• Theoretical analysis proves that performance profiles have a non-monotonic relationship with low-data and asymptotic sample complexity, grounding analysis of reinforcement learning scaling, capacity, and complexity.Source: §1 · p. 1
• Large-scale Arcade Learning Environment experiments across low- and high-data regimes show that recent algorithms evaluated on ALE 100K face systematic evaluation bias from the implicit sample-complexity assumption.Source: §1 · p. 2

Background and Preliminaries

• A policy maps states to actions to maximize expected cumulative discounted reward, represented through a state-action value function.The problem is formalized as an MDP with state and action spaces, transition probabilities, rewards, a discount factor, and an initial-state distribution.Source: §2 · p. 2
• Deep reinforcement learning approximates the state-action value function with neural networks when large state or action spaces make tabular representation impractical.Source: §2 · p. 2

Dueling Architecture

• The dueling architecture (Wang et al. 2016) uses separate streams to estimate state values and action advantages, then combines them into action values.The passage defines advantage as Q(s, a) minus the maximum action value for state s.Source: §2 · p. 2

Inherent High-Capacity Models

• C51 models value distributions with categorical atoms, QRDQN learns quantile projections, and IQN learns the full quantile function rather than discrete quantiles (Bellemare, Dabney, and Munos 2017; Dabney et al. 2018b; Dabney et al. 2018a).C51 is identified as the initial algorithm proposed to have inherent high capacity.Source: §2 · p. 2

3 Low-data Regime versus Asymptotic Performance

• The analysis studies learning non-stationary policies by regret minimization in undiscounted finite-horizon MDPs with linear function approximation.The MDP permits rewards and transitions to vary at each episode step, and each time step uses a feature map to parameterize state-action values.Source: §3 · pp. 2–3
• For this setting, a theoretical algorithm’s regret bound is optimal up to logarithmic factors under the stated conditions.The result is paired with a lower bound applying to any algorithm for the constructed MDP class.Source: §3 · p. 3
• The constructed MDP classes preserve the underlying transitions and, for fixed approximation error and feature dimensions, the feature map, while varying approximation accuracy and model capacity.This shared-environment construction supports comparing models with different capacity and inherent Bellman error.Source: §3 · p. 3
• Lower-capacity models with larger approximation error can outperform higher-capacity models in the low-data regime, but their relative performance reverses in the high-data regime.Theorem 3.2 formalizes this trade-off across thresholds Klow and Khigh; the section concludes asymptotic performance is not indicative of expected performance when training data is scarce.Source: §3 · pp. 3–4

4 The Assumption of Monotonicity and Performance Rankings

• Section 6 experiments show that high-data performance profiles do not transfer monotonically to the low-data regime, challenging comparisons that assume high-data state-of-the-art algorithms remain best in low-data settings.The section notes that many low-data studies compare new algorithms against inherently higher-capacity models on this assumption.Source: §4 · p. 4
• When two actions’ true mean values differ by ϵ, a distribution approximation error of ϵ in total variation can suffice to reverse their ranking.Thus, correct action ranking requires learning the state-action value distribution with error at most ϵ.Source: §4 · p. 4
• k/ϵ² samples are required for C51 to learn a state-action value distribution with fixed support size k to total variation distance at most ϵ.This follows from standard sample-complexity results for discrete distributions.Source: §4 · p. 4
• QRDQN and IQN remove the known-support assumption for more flexible value representations, but unknown-support learning can require substantially more samples than k/ϵ².The section states that the lower bound in Proposition 4.2 can be significantly larger than k/ϵ² samples.Source: §4 · p. 4

• The framework is introduced to ensure deep reinforcement learning research progress is reliable and scientifically robust.Source: §5 · p. 4
• Performance rankings across data regimes are non-monotone, so rankings cannot be assumed to persist across regimes.Source: §5 · p. 5
• Including algorithms in comparison benchmarks based on a monotonicity assumption creates biased evaluations.Source: §5 · p. 5
• Core algorithms must be included in comparison benchmarks.Source: §5 · p. 5
• Inherent capacity and dimensionality provide insights into performance rankings across regimes.Source: §5 · p. 5
• Creating datasets based on a monotonicity assumption creates biased benchmarks.Source: §5 · p. 5

Experimental scope

• The experiments cover both low-data ALE 100K and high-data 200-million-frame training, with results reported using standard errors of the mean.Human-normalized scores are computed relative to random and human scores.Source: §6 · p. 5

Implicit Assumptions on Monotonicity Cause Suboptimal and Incorrect Conclusions

• In ALE 100K, the dueling baseline was omitted from comparisons despite outperforming many recent algorithms, including higher-capacity models.Figure 3 presents 100K learning curves for dueling, C51, IQN, and QRDQN; the paper argues that excluding dueling contributed to incorrect conclusions.Source: §6 · pp. 5–6, Figure 3 · p. 6

Providing Direct Comparison to Core Algorithms

• In the reported comparison, simple baseline dueling performed 15% better than DRQNeurIPS and 11% less than DRQICLR, rather than the 82% gain reported in the original paper.Source: §6 · p. 6

Non-Monotonicity of Performance Ranking Across Regimes

• Algorithm performance rankings do not transfer monotonically from 200-million-frame training to ALE 100K, and the analysis reports a complete reversal across regimes.This reversal also appears in the theoretical regret curves when feature dimensionality and inherent Bellman error vary, including when greater model capacity improves approximation accuracy.Source: §6 · pp. 6–7

Theoretical Analysis and the Inherent Bellman Error vs Dimensionality

• Higher-capacity baseline algorithms require orders of magnitude more samples than dueling to reach its performance across ALE 100K MDPs.Figure 4 compares the samples required by higher-capacity baselines and IQN to reach dueling’s performance, and gives an overall comparison of low-data algorithms to dueling.Source: §6 · p. 7, Figure 4 · p. 7

Datasets are Created and Founded on Implicit Assumptions

• ALE 100K’s game selection favored games on which its proposing algorithm or Rainbow performed better, extending evaluation bias from baselines to the benchmark itself.The paper says related implicit assumptions also shaped comparisons involving SimPLE, DRQICLR, CURL, SPR, and Efficient-Zero, including MuZero.Source: §6 · p. 7

7 Conclusion

• Deep reinforcement learning performance profiles are not monotonic across sample-complexity regimes, according to the paper’s theoretical and empirical analyses.The experiments cover the 100K-frame Arcade Learning Environment low-data regime and baseline 200-million-frame high-data training.Source: §7 · p. 8
• An implicit monotonicity assumption in a major line of recent research led studies to incorrect conclusions about performance characteristics across sample-complexity regimes.The paper says this assumption is present in many recent state-of-the-art studies.Source: §7 · p. 8
• Several baseline Q algorithms perform better than a line of recent algorithms claimed to be state-of-the-art.Source: §7 · p. 8
• The paper provides theoretical analysis of baseline deep reinforcement learning algorithms’ sample complexity to characterize scaling, capacity, and complexity.Its motivating questions also concern canonical methodological choices that affect progress in deep reinforcement learning research.Source: §7 · p. 8