One-sentence Summary

Ezgi Korkmaz presents a principled analysis of deep reinforcement learning evaluation and design paradigms, establishing theoretical foundations of scaling laws and demonstrating that asymptotic performance rankings are not monotonic with data regimes, which reveals that canonical evaluation paradigms have led to incorrect conclusions and provides insights into scaling, capacity, and complexity.

Key Contributions

• The paper introduces theoretical foundations of scaling laws in deep reinforcement learning, formally characterizing the relationships among capacity, complexity, and sample complexity regimes.
• Large-scale experiments on the Arcade Learning Environment (100K and 200M frames) demonstrate that performance rankings of deep RL algorithms are not monotonic across data regimes, contradicting the assumption of monotonicity in a line of prior research.
• The analysis reveals that several baseline Q-learning algorithms outperform many recent methods claimed as state-of-the-art, and that canonical evaluation paradigms have led to incorrect conclusions in prior research.

Introduction

In deep reinforcement learning, the field has split into two dominant evaluation paradigms: algorithms are either optimized for high-data regimes (200 million frames) or pushed to excel in low-data regimes (100K interactions), with the latter spawning a major line of research that claims state-of-the-art status solely from low-data benchmark comparisons. The authors identify a critical but unspoken premise underlying this work: the assumption that an algorithm's performance profile is monotonic across sample-complexity regimes, meaning its relative ranking stays consistent from low-data to asymptotic settings. This implicit belief shapes canonical design and evaluation choices, systematically biasing conclusions and misdirecting research efforts for years. The authors' main contribution is a theoretical and empirical refutation of that monotonicity assumption. They introduce a principled analysis of scaling, capacity, and complexity in deep reinforcement learning, prove that the relationship between performance and sample complexity is non-monotonic, and demonstrate through extensive experiments that several classic Q-learning baselines outperform many recent algorithms that were claimed to be state-of-the-art under the flawed low-data evaluation paradigm.

Method

The authors formalize the problem within finite-horizon, undiscounted Markov decision processes (MDPs) with non-stationary policies and linear function approximation. An MDP is defined by a tuple $\langle S, \bar{M}, \mathcal{P}, \mathcal{R}, \mathcal{H} \rangle$⟨S,Mˉ,P,R,H⟩, where $S$S is the state set, $\mathcal{H}$H is the horizon, and for each time step $t \in [\mathcal{H}]$t∈[H] the transition kernel $\mathcal{P}_t(s' \mid s, a)$Pt​(s′∣s,a) and reward $\mathcal{R}_t(s, a, s')$Rt​(s,a,s′) may vary. A non-stationary policy $\pi = (\pi_1, \ldots, \pi_{\mathcal{H}})$π=(π1​,…,πH​) induces a state-action value function

$\mathcal{Q}_t^\pi(s, a) = \mathbb{E}\left[ \sum_{h=t}^{\mathcal{H}} \mathcal{R}_h(s_h, \pi_h(s_h), s_{h+1}) \;\big|\; s_h = s, a_h = a \right],$Qtπ​(s,a)=E[∑h=tH​Rh​(sh​,πh​(sh​),sh+1​)​sh​=s,ah​=a],

and the corresponding value function $\mathcal{V}_t^\pi(s) = \mathcal{Q}_t(s, \pi_t(s))$Vtπ​(s)=Qt​(s,πt​(s)). The optimal policy $\pi^*$π∗ satisfies $\mathcal{V}_t^*(s) = \sup_\pi \mathcal{V}_t^\pi(s)$Vt∗​(s)=supπ​Vtπ​(s). The learning objective is to minimize the regret over $K$K episodes,

$\operatorname{REGRET}(K) = \sum_{k=1}^{K} \left( \mathcal{V}_1^*(s_1^k) - \mathcal{V}_1^{\pi^k}(s_1^k) \right),$REGRET(K)=∑k=1K​(V1∗​(s1k​)−V1πk​(s1k​)),

where $s_1^k$s1k​ is the starting state of the $k$k-th episode and $\pi^k$πk is the policy used in that episode.

In the linear function approximation setting, each time step $t$t has a feature map $\phi_t: S \times A \to \mathbb{R}^{d_t}$ϕt​:S×A→Rdt​ and the state-action value function is parameterized as $\mathcal{Q}_t(\theta_t)(s, a) = \phi_t(s, a)^\top \theta_t$Qt​(θt​)(s,a)=ϕt​(s,a)⊤θt​. Recent results provide an algorithm achieving a regret bound that is optimal up to logarithmic factors under appropriate normalization assumptions:

$\operatorname{REGRET}(K) = \tilde{O}\!\left( \sum_{t=1}^{\mathcal{H}} d_t \sqrt{K} + \sum_{t=1}^{\mathcal{H}} \sqrt{d_t}\, \mathcal{I} K \right),$REGRET(K)=O~(∑t=1H​dt​K​+∑t=1H​dt​​IK),

where $\mathcal{I}$I is the inherent Bellman error. The lower bound matches this form, establishing that the derived rate is tight. A crucial property of the constructed MDP class $\mathcal{C}(\mathcal{I}, \{d_t\}_{t=1}^H)$C(I,{dt​}t=1H​) is that all its members share the same transition dynamics (up to state/action renaming) and use the same feature maps. Thus, varying the inherent Bellman error $\mathcal{I}$I and the feature dimensions $d_t$dt​ corresponds to varying the approximation accuracy and model capacity within a fixed underlying environment.

The authors exploit this structure to prove a fundamental non-monotonicity in performance across data regimes. For simplicity, they consider a constant dimension $d_t = d$dt​=d and write $\mathcal{C}(\mathcal{I}, d)$C(I,d). The core theoretical result (Theorem 3.2) states that for any $\epsilon > 0$ϵ>0, setting $d_\beta = d_\alpha^{1 - \epsilon/2}$dβ​=dα1−ϵ/2​, there exist thresholds $K_{\text{low}} < K_{\text{high}}$Klow​<Khigh​ and inherent Bellman error levels $\mathcal{I}_\beta > \mathcal{I}_\alpha$Iβ​>Iα​ such that:

• In the low-data regime ($K < K_{\text{low}}$K<Klow​), an algorithm optimized for the lower-capacity model ($d_\beta$dβ​) with larger approximation error ($\mathcal{I}_\beta$Iβ​) provably achieves low regret on all MDPs in $\mathcal{C}(\mathcal{I}_\beta, d_\beta)$C(Iβ​,dβ​), whereas any algorithm must suffer at least $\widetilde{\Omega}\bigl(d_\beta^{\epsilon/2} \operatorname{REGRET}_{\text{low}}(K)\bigr)$Ω(dβϵ/2​REGRETlow​(K)) regret on some MDP in $\mathcal{C}(\mathcal{I}_\alpha, d_\alpha)$C(Iα​,dα​).
• In the high-data regime ($K > K_{\text{high}}$K>Khigh​), the ranking reverses: the higher-capacity, lower-error pair ($d_\alpha, \mathcal{I}_\alpha$dα​,Iα​) admits an algorithm with low regret on $\mathcal{C}(\mathcal{I}_\alpha, d_\alpha)$C(Iα​,dα​), while any algorithm on $\mathcal{C}(\mathcal{I}_\beta, d_\beta)$C(Iβ​,dβ​) suffers regret at least $\widetilde{\Omega}\bigl(d_\alpha^{\epsilon} \operatorname{REGRET}_{\text{high}}(K)\bigr)$Ω(dαϵ​REGREThigh​(K)).

Thus, the relative performance of different model capacities is not monotonic from low-data to asymptotic regimes. A larger model with superior asymptotic performance can be outperformed by a smaller model when data is scarce.

To further illuminate the empirical consequences, the authors analyze sample complexity in distributional reinforcement learning, where the state-action value distribution $\mathcal{D}(s,a)$D(s,a) is learned. Proposition 4.1 shows that if the true means of two actions differ by $\epsilon$ϵ, an error of $\epsilon$ϵ in total variation distance $d_{TV}$dTV​ for one action's distribution can reverse the action ranking. Consequently, learning the correct ordering demands distribution estimation with error below $\epsilon$ϵ. For a fixed-support categorical representation (e.g., C51), the sample complexity scales as $k / \epsilon^2$k/ϵ2, where $k$k is the support size. More flexible algorithms like QRDQN and IQN that do not assume a known support learn a uniform mixture

$\mathcal{Z}(s,a) = \frac{1}{N} \sum_{i=1}^{N} \delta_{\theta_i(s,a)}$Z(s,a)=N1​∑i=1N​δθi​(s,a)​

with learned atom locations $\theta_i(s,a)$θi​(s,a). Proposition 4.2 provides a lower bound: when $N > M \ge 2$N>M≥2 and $\epsilon > M/(4N)$ϵ>M/(4N), the number of samples required to learn such a model is $\Omega(M / \epsilon^2)$Ω(M/ϵ2). This lower bound can be substantially larger than the $k/\epsilon^2$k/ϵ2 rate of fixed-support methods, highlighting that the added flexibility of unknown support can further increase sample complexity and exacerbate the performance gap in low-data regimes. Together, these results formalize the theoretical underpinning for the observed non-transferability of asymptotic performance rankings to the data-scarce setting.

Experiment

This work presents a principled evaluation framework and a large-scale empirical analysis on the Arcade Learning Environment, revealing that common implicit assumptions about performance monotonicity across data regimes lead to biased algorithm comparisons and benchmarks. The experiments demonstrate that a simple baseline (dueling DQN) outperforms many recent, higher-capacity models in the low-data setting, and that theoretical regret analysis confirms performance rankings can reverse completely. These findings show that core algorithms must be directly compared, and that even widely used benchmarks like ALE 100K are built on selection biases that misdirect research progress.

In the low-data Arcade Learning Environment benchmark, the dueling architecture achieves the highest median and lower-tail performance, while double Q-learning reaches the highest mean score. The results show that simpler baselines can outperform more recent distributional methods, challenging the implicit assumption that high-data regime rankings directly transfer to low-data settings. Dueling attains a median human-normalized score more than double that of the next best algorithm, C51. Double-Q achieves the highest mean human-normalized score, exceeding all distributional algorithms in this comparison. IQN and QRDQN underperform both Double-Q and Dueling across mean, median, and 20th percentile metrics.

In low-data Arcade Learning Environment benchmarks, simpler architectures like dueling and double Q-learning outperform more recent distributional methods, challenging the assumption that high-data regime rankings directly transfer to limited-data settings. Dueling achieves the strongest median and lower-tail performance, while double Q-learning attains the highest mean score, with both surpassing distributional algorithms such as C51, IQN, and QRDQN. The findings indicate that distributional approaches may not be optimal when data is scarce.