Paper deep dive
Principled Analysis of Deep Reinforcement Learning Evaluation and Design Paradigms
Ezgi Korkmaz
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/10/2026, 2:16:20 AM
Summary
This paper critically analyzes deep reinforcement learning (DRL) evaluation and design paradigms, challenging the implicit assumption that algorithm performance rankings are monotonic across different sample complexity regimes. Through theoretical analysis and large-scale experiments on the Arcade Learning Environment, the authors demonstrate that asymptotic (high-data) performance does not reliably predict low-data regime performance. The work introduces scaling law foundations, proves non-monotonicity across regimes (Theorem 3.2), and highlights how canonical methodological choices have led to systematic bias and incorrect conclusions in recent DRL research.
Entities (12)
Relation Signals (8)
Asymptotic Performance → hasnonmonotonicrelationshipwith → Low-data Regime Performance
confidence 98% · asymptotic performance of reinforcement learning algorithms does not have a monotone relationship between performance rankings and data-regimes.
Theorem 3.2 → proves → Non-monotonicity Across Regimes
confidence 97% · Theorem 3.2 (Non-monotonicity Across Regimes). For any ϵ>0, let dα be any feature dimension...
Deep Reinforcement Learning → analyzes → Scaling Laws
confidence 95% · We introduce the theoretical foundations of scaling laws in reinforcement learning and show that the asymptotic performance...
Markov Decision Process → formalizes → Reinforcement Learning Problem
confidence 95% · The reinforcement learning problem is formalized as a Markov Decision Process (MDP) represented as a tuple...
Dueling Architecture → proposedby → Wang et al. 2016
confidence 95% · The dueling architecture (Wang et al. 2016) outputs two streams of fully connected layers...
Canonical Evaluation Paradigms → leadsto → Incorrect Conclusions
confidence 92% · canonical design and evaluation paradigms resulted in incorrect conclusions.
C51 → precedes → QR-DQN
confidence 90% · Following this baseline the QRDQN algorithm (Dabney et al. 2018b) is proposed to learn the quantile projection...
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Starting from the utilization of deep neural networks to approximate the state-action value function that led to winning one of the most challenging games, to algorithmic advancements that allowed solving problems without even explicitly stating the rules of the challenge at hand, reinforcement learning research has been the center of remarkable scientific progress for the past decade. In this paper, we focus on the key ingredients of this research progress and we analyze the canonical evaluation and design paradigms in reinforcement learning. We introduce the theoretical foundations of scaling laws in reinforcement learning and show that the asymptotic performance of reinforcement learning algorithms does not have a monotone relationship between performance rankings and data-regimes. We conduct large-scale experiments and our results demonstrate that a line of reinforcement learning research under the canonical design and evaluation paradigms resulted in incorrect conclusions. Our analysis and results provide a core analysis on scaling, capacity and complexity of deep reinforcement learning.
Tags
Links
- Source: https://arxiv.org/abs/2607.07769v1
- Canonical: https://arxiv.org/abs/2607.07769v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
52,778 characters extracted from source content.
Expand or collapse full text
Principled Analysis of Deep Reinforcement Learning Evaluation and Design Paradigms Ezgi Korkmaz Abstract Starting from the utilization of deep neural networks to approximate the state-action value function that led to winning one of the most challenging games, to algorithmic advancements that allowed solving problems without even explicitly stating the rules of the challenge at hand, reinforcement learning research has been the center of remarkable scientific progress for the past decade. In this paper, we focus on the key ingredients of this research progress and we analyze the canonical evaluation and design paradigms in reinforcement learning. We introduce the theoretical foundations of scaling laws in reinforcement learning and show that the asymptotic performance of reinforcement learning algorithms does not have a monotone relationship between performance rankings and data-regimes. We conduct large-scale experiments and our results demonstrate that a line of reinforcement learning research under the canonical design and evaluation paradigms resulted in incorrect conclusions. Our analysis and results provide a core analysis on scaling, capacity and complexity of deep reinforcement learning. 1 Introduction Founded on rigorous theoretical guarantees, reinforcement learning research achieved high acceleration upon the proposal of the initial study on approximating the state-action value function via deep neural networks (Mnih et al. 2015; Stiennon et al. 2020; Schrittwieser et al. 2020; Lee et al. 2024; Korkmaz 2025). A line of highly successful deep reinforcement learning algorithms have been proposed (Hasselt et al. 2016; Wang et al. 2016; Hessel et al. 2018, 2021; Kapturowski et al. 2023; Korkmaz 2024) from focusing on different architectural ideas to foundations targeting overestimation, all of which were designed and tested in the high-data regime, i.e. two hundred million frame training. An alternative recent line of research with an extensive amount of publications focused on pushing the performance bounds of deep reinforcement learning policies in the low-data regime, i.e. with one hundred thousand environment interaction training. Many different concepts in current reinforcement learning research, from architectural proposals to learning underlying dynamics of the environment, experienced accelerated progress and significant attention, growing into several major research fields, solely based on policy performance comparisons demonstrated in the low-data regime benchmark. In this paper, we focus on evaluation paradigms, implicit assumptions and canonical methodological choices made in deep reinforcement learning research and demonstrate that there is a significant overlooked underlying premise driving this line of research without being explicitly discussed: that the performance profiles of deep reinforcement learning algorithms have a monotonic relationship with different sample-complexity regimes. We show that this implicit assumption, that is commonly shared amongst a large collection of low-data regime studies, shapes how the canonical design and evaluation choices are made in deep reinforcement learning research and represents a prominent misdirection in scientific progress. The suboptimal conclusions obtained from these canonical choices shape future research directions with incorrect reasoning. We show that these methodological decisions fuel incorrect justifications and conclusions, thereby misdirecting research efforts toward certain concepts for several years. Thus, in our paper we target these underlying premises and aim to answer the following questions: What are the implicit assumptions and canonical choices in deep reinforcement learning research that fundamentally affect the conclusions made? What is the foundational relationship between sample complexity and the algorithmic performance from the data-scarce regime to the asymptotic regime? Hence, to be able to answer the questions raised above, in our paper we focus on underlying design and evaluation paradigms in deep reinforcement learning and make the following contributions: • We analyze the evaluation paradigms and canonical methodological choices in deep reinforcement learning research, and introduce the theoretical foundations on how these methodological choices affect algorithm design, performance comparisons and algorithmic conclusions. Our analysis lays the foundations on scaling, capacity and complexity of deep reinforcement learning. • Our theoretical analysis proves that the performance profile has a non-monotonic relationship with the asymptotic sample complexity and the low-data sample complexity regime. Regarding the central focus of the large scale implicit assumption instances, our results reveal that the canonical methodological choices made in a line of deep reinforcement learning research have led to incorrect justifications and conclusions. • We conduct large scale extensive experiments for a comprehensive and a diverse portfolio of deep reinforcement learning baseline algorithms in both the low-data regime and the high-data regime Arcade Learning Environment benchmark. Our results demonstrate that recent algorithms proposed and evaluated in the Arcade Learning Environment 100K benchmark are significantly affected by the implicit assumption on the relationship between performance profiles and sample complexity resulting in systematic bias in algorithmic evaluation. 2 Background and Preliminaries The reinforcement learning problem is formalized as a Markov Decision Process (MDP) represented as a tuple ⟨S,A,,ℛ,γ,ρ0⟩ S,A,P,R,γ, _0 where S represents the state space, A represents the set of actions, P represents the transition probability distribution on S×A×S× A× S, ℛ:S×A→ℝR:S× A represents the reward function, and γ∈(0,1]γ∈(0,1] represents the discount factor. The aim in reinforcement learning is to learn an optimal policy π(s,a)π(s,a) that maps state observations to actions π:S→Δ(A)π:S→ (A), which maximizes the expected cumulative discounted rewards R=at∼π(st,⋅)∑tγtℛ(st,at,st+1)R=E_a_t π(s_t,·) _tγ^tR(s_t,a_t,s_t+1). This objective is achieved by constructing a state-action value function that learns for each state-action pair the expected cumulative discounted rewards that will be obtained if action a∈Aa∈ A is executed in state s∈Ss∈ S. (s,a)=∑s′(s′|s,a)[ℛ(s,a,s′)+γ(s′)]Q(s,a)= _s P(s |s,a)[R(s,a,s )+ (s )] In settings where the state space and/or action space is large enough that the state-action value function (s,a)Q(s,a) cannot be held in a tabular form, a function approximator is used. Thus, for deep reinforcement learning the Q-function is approximated via deep neural networks θt+1=θt+α( _t+1= _t+α( ℛ(st,at,st+1) (s_t,a_t,s_t+1) +γ(st+1,argmaxa(st+1,a;θt);θt) + (s_t+1, *arg\,max_aQ(s_t+1,a; _t); _t) −(st,at;θt))∇θt(st,at;θt). -Q(s_t,a_t; _t)) _ _tQ(s_t,a_t; _t). Dueling Architecture: The dueling architecture (Wang et al. 2016) outputs two streams of fully connected layers for both estimating the advantage (s,a)A(s,a) for each action in a given state s, (s,a)=(s,a)−maxa(s,a)A(s,a)=Q(s,a)- _aQ(s,a) and the state values (s)V(s). In particular, the last layer of the dueling architecture contains the forward mapping (s,a;θ,α,β)=(s;θ,β)+((s,a;θ,α)−maxa′∈A(s,a′;θ,α))Q(s,a;θ,α,β)=V(s;θ,β)+ (A(s,a;θ,α)- _a ∈ AA(s,a ;θ,α) ) where θ represents the parameters of the convolutional layers and α and β represent the parameters of the fully connected layers outputting the advantage and state value estimates respectively. Inherent High-Capacity Models: The initial algorithm that has been proposed to have inherent high-capacity is C51. In particular, the projected Bellman update for the ithi th atom is computed as (Φθ(st,at))i ( _θ(s_t,a_t))_i =∑j−1[1−|[zj]vminvmax−zi|Δz]01 = _j^N-1 [1- |[Tz_j]^v_ max_v_ min-z_i| z ]^1_0 τj(st+1,maxa∈Aθ(st+1,a)) _j(s_t+1, _a∈ AEZ_θ(s_t+1,a)) where zi=vmin+iΔz:0≤i<z_i=v_ min+i z:0≤ i<N represents the set of atoms in categorical learning, and the atom probabilities are learnt as a parametric model (Bellemare et al. 2017) τi(st,maxa∈Aθ(st,a))=eθi(st,at)∑jeθj(st,at),Δz:=vmax−vmin−1 _i(s_t, _a∈ AEZ_θ(s_t,a))= e _i(s_t,a_t) _je _j(s_t,a_t)\>\> ,\>\> z:= v_ max-v_ minN-1 Following this baseline the QRDQN algorithm (Dabney et al. 2018b) is proposed to learn the quantile projection (st,at)=ℛ( (s_t,a_t)=R( st,at,st+1) s_t,a_t,s_t+1) +γ(st+1,argmaxa∈Az∼(st+1,at+1)[z]) + (s_t+1, *arg\,max_a∈ AE_z (s_t+1,a_t+1)[z]) with st+1∼(⋅|st,at)s_t+1 (·|s_t,a_t) where ∈ZZ∈ Z represents the quantile distribution of an arbitrary value function. Following this study the IQN algorithm (Dabney et al. 2018a) is proposed to learn the full quantile function instead of learning a discrete set of quantiles as in the QRDQN algorithm. The IQN algorithm objective is to minimize the loss function ℒ=1 = 1K ∑i=1∑j=1′ρδ(ℛ(st,at,st+1) _i=1^K _j=1^K _δ(R(s_t,a_t,s_t+1) (1) +γδj′(st+1,argmaxa∈Aβ(st,at))−δi(st,at)) + _δ _j(s_t+1, *arg\,max_a∈ AQ_β(s_t,a_t))-Z_ _i(s_t,a_t)) where ρδ _δ represents the Huber quantile regression loss, and β=∫01ℱ−1(δ)β(δ)Q_β= ^1_0F^-1_Z(δ)dβ(δ). Note that δ=ℱ−1(δ)Z_δ=F^-1_Z(δ) is the quantile function of the random variable Z at δ∈[0,1]δ∈[0,1]. 3 Low-data Regime versus Asymptotic Performance Our paper discovers both with extensive empirical analysis and theoretical investigation that asymptotic performance of reinforcement learning algorithms does not necessarily provide any information nor indication on their relative performance ranking in the low-data regime. The results provided in Section 6 extensively demonstrate that a large body of work in reinforcement learning research carried this assumption and resulted in incorrect conclusions. In this section, we introduce the foundational basis for our discovery revealed by our extensive empirical analysis in Section 6 in optimization of non-stationary policies, i.e. rewards and transitions that can vary with each step in an episode, in undiscounted, finite-horizon MDPs with linear function approximation. In particular, a finite horizon MDP is represented as a tuple ⟨S,A,,ℛ,ℋ⟩ S,A,P,R,H where S is the set of states, and A represents the set of actions. For each time step t∈[ℋ]=1,…,ℋt∈[H]=\1,…,H\, state s, and action a the transition probability kernel t(s′|s,a)P_t(s |s,a) gives the probability distribution over the next state, and the reward ℛt(s,a,s′)R_t(s,a,s ) gives the immediate rewards. A non-stationary policy π=(π1,…,πℋ)π=( _1,…, _H) induces a state-action value function given by tπ(s,a)=[∑h=tℋℛh(sh,πh(sh),sh+1)|sh=s,ah=a] _t^π(s,a)=E [ _h=t^HR_h(s_h, _h(s_h),s_h+1) |s_h=s,a_h=a ] where we let ah∼πh(sh)a_h _h(s_h), and the corresponding value function tπ(s)=t(s,πt(s))V_t^π(s)=Q_t(s, _t(s)). The optimal non-stationary policy π∗π^* has value function t∗(s)=tπ∗(s)V_t^*(s)=V_t^π^*(s) satisfying t∗(s)=supπtπ(s).V_t^*(s)= _πV_t^π(s). The objective is to learn a sequence of non-stationary policies πkπ^k for k∈1,…,k∈\1,…,K\ while interacting with an unknown MDP in order to minimize the regret, which is measured asymptotically over K episodes of length ℋH, Regret()=∑k=1(1∗(s1k)−1πk(s1k)) Regret(K)= _k=1^K (V_1^*(s^k_1)-V_1^π^k(s^k_1) ) where s1k∈Ss^k_1∈ S is the starting state of the k-th episode. Regret sums up the gap between the expected rewards obtained by the sequence of learned policies πkπ^k and those obtained by π∗π^* when learning for K episodes. In the linear function approximation setting there is a feature map ϕt:S×A→ℝdt _t:S× A ^d_t for each t∈[ℋ]t∈[H] that sends a state-action pair (s,a)(s,a) to the dtd_t-dimensional vector ϕt(s,a) _t(s,a). Then, the state-action value function t(s,a)Q_t(s,a) is parameterized by a vector θt∈ℝdt _t ^d_t so that t(θt)(s,a)=ϕt(s,a)⊤θtQ_t( _t)(s,a)= _t(s,a) _t. Recent theoretical work in this setting gives an algorithm along with a lower bound that matches the regret achieved by the algorithm up to logarithmic factors. Theorem 3.1 ((Zanette et al. 2020)). Under appropriate normalization assumptions there is an algorithm that learns a sequence of policies πkπ^k achieving regret Regret()=O~(∑t=1ℋdt+∑t=1ℋdtℐ) Regret(K)= O ( _t=1^Hd_t K+ _t=1^H d_tIK ), where ℐI is the inherent Bellman error. Furthermore, this regret bound is optimal for this setting up to logarithmic factors in dt,d_t,K and ℋH whenever =Ω((∑t=1ℋdt)2)K= (( _t=1^Hd_t)^2), in the sense that for any level of inherent Bellman error ℐI and sequence of feature dimensions dtt=1H\d_t\_t=1^H, there exists a class of MDPs (ℐ,dtt=1H)C(I,\d_t\_t=1^H) where any algorithm achieves at least as much regret on at least one MDP in the class. The class of MDPs (ℐ,dtt=1H)C(I,\d_t\_t=1^H) constructed in Theorem 3.1 additionally satisfies the following properties. First, every MDP in ∪ℐ,dtt=1H(ℐ,dtt=1H) _I,\d_t\_t=1^HC(I,\d_t\_t=1^H) has the same transitions (up to renaming of states and actions). Second, for each fixed value of the inherent Bellman error ℐI and the dimensions dtt=1H\d_t\_t=1^H, every MDP in (ℐ,dtt=1H)C(I,\d_t\_t=1^H) utilizes the same feature map ϕt(st,at) _t(s_t,a_t). Thus one can view the class (ℐ,dtt=1H)C(I,\d_t\_t=1^H) as encoding one ”underlying” true environment defined by the transitions, with varying values of ℐI and dtt=1H\d_t\_t=1^H corresponding to varying levels of function approximation accuracy, and model capacity for the underlying environment. For simplicity of notation we will focus on the setting where dt=d_t=d for all t∈1,…Ht∈\1,… H\ and write (ℐ,d)C(I,d) for the class of MDPs constructed in Theorem 3.1 for this setting. Utilizing this point of view, we can then prove the following theorem on the relationship between the performance in the asymptotic and low-data regimes. Theorem 3.2 (Non-monotonicity Across Regimes). For any ϵ>0ε>0, let dαd_α be any feature dimension, and let dβ=dα1−ϵ/2d_β=d_α^1-ε/2. Then there exist thresholds low<highK_low<K_high and inherent Bellman error levels ℐβ>ℐαI_β>I_α such that 1. There is an algorithm achieving regret Regretlow() Regret_low(K) when <lowK<K_low for all MDPs in (ℐβ,dβ)C(I_β,d_β). However, every algorithm has regret at least Ω~(dβϵ/2Regretlow()) (d_β^ε/2 Regret_low(K) ) when <lowK<K_low on some MDP M∈(ℐα,dα)M (I_α,d_α). 2. There is an algorithm achieving regret Regrethigh() Regret_high(K) when >highK>K_high for all MDPs in (ℐα,dα)C(I_α,d_α). However, every algorithm has regret at least Ω~(dαϵRegrethigh()) (d_α^ε Regret_high(K) ) on some MDP M∈(ℐβ,dβ)M (I_β,d_β) when >highK>K_high. Proof. Let ϵ>0ε>0 and consider dβ=dα1−ϵ2,ℐβ=1dαϵdβ,ℐα=1dα12+2ϵ,low=dα2+ϵ,high=dα2+4ϵd_β=d_α^1- ε2,I_β= 1d_α^ε d_β,I_α= 1d_α 12+2ε,K_low=d_α^2+ε,K_high=d_α^2+4ε We begin with the proof of part 1. Therefore, for <lowK<K_low, dβℐβ=dα−ϵ<dα1−ϵ2=dβ d_βI_βK=d_α^-εK<d_α^1- ε2 K=d_β K. Therefore, by Theorem 3.1 there exists an algorithm achieving regret Regretlow() Regret_low(K) =O~(ℋdβ+ℋdβℐβ) = O (Hd_β K+H d_βI_βK ) =O~(dβ) = O (d_β K ) in every MDP M∈(ℐβ,dβ)M (I_β,d_β). Further, since low=dα2+ϵ>Ω~(dα2)K_low=d_α^2+ε> (d_α^2 ), the lower bound from Theorem 3.1 applies to the class of MDPs (ℐα,dα)C(I_α,d_α) for all ∈[Ω~(dα2),low]K∈ [ (d_α^2 ),K_low ]. In particular, every algorithm receives regret at least Regret() Regret(K) =Ω~(ℋdα+ℋdαℐα) = (Hd_α K+H d_αI_αK ) >Ω~(ℋdβ11−ϵ/2) > (Hd_β 11-ε/2 K ) >Ω~(ℋdβϵ/21−ϵ/2dβ) > (Hd_β ε/21-ε/2d_β K ) Thus, Regret()>Ω~(dβϵ/2Regretlow()) Regret(K)> (d_β^ε/2 Regret_low(K) ). For part 2, note that for >highK>K_high we have both dαℐα=dα−2ϵ>dα−2ϵ⋅high>dα d_αI_αK=d_α^-2εK>d_α^-2ε K·K_high>d_α K and dβℐβ>dα−ϵ⋅low=dα1+ϵ>dβ d_βI_βK>d_α^-ε K·K_low=d_α^1+ε K>d_β K. Asymptotic vs Low-Data Regret in the Low-data Regime Regret in the High-data Regime Figure 1: Left: Scaling laws of reinforcement learning: Baseline comparison of algorithms that were proposed and developed in the high-data regime in the Arcade Learning Environment in both high-data regime and low-data regime. Middle: Regret in the low-data regime. Right: Regret in the high-data regime. Therefore by Theorem 3.1 that for >highK>K_high there exists an algorithm achieving regret Regrethigh() Regret_high(K) =O~(ℋdα+ℋdαℐα) = O (Hd_α K+H d_αI_αK ) =O~(ℋdαℐα). = O (H d_αI_αK ). for every MDP M∈(ℐα,dα)M (I_α,d_α). However, by the lower bound in Theorem 3.1, for >highK>K_high every algorithm receives regret at least Regret() Regret(K) =Ω~(ℋdβ+ℋdβℐβ) = (Hd_β K+H d_βI_βK ) >Ω~(ℋdβℐβ)=Ω~(ℋdα−ϵ) > (H d_βI_βK )= (Hd_α^-εK ) =Ω~(dαϵℋdα−2ϵ)=Ω~(dαϵℋdαℐα) = (d_α^εHd_α^-2εK )= (d_α^εH d_αI_αK ) >Ω~(dαϵRegrethigh()) > (d_α^ε Regret_high(K) ) ∎ Theorem 3.2 introduces the provable trade-off between performance in the low-data regime, i.e. <lowK<K_low, and the high-data regime, i.e. >highK>K_high. In particular, in the low-data regime lower capacity function approximation, i.e. lower feature dimension dβd_β, with larger approximation error, i.e. larger inherent Bellman error ℐβI_β, can provably outperform larger capacity models, i.e. feature dimension dαd_α, with smaller approximation error, i.e. inherent Bellman error ℐαI_α. Furthermore, the relative performance is reversed in the high-data regime >highK>K_high. Thus, asymptotic performance of an algorithm is neither indicative nor carries any relevant information on the expected performance of the algorithm when training data is scarce (i.e. limited). 4 The Assumption of Monotonicity and Performance Rankings The instances of the implicit assumption that the performance profile of an algorithm in the high-data regime will translate to the low-data regime monotonically appear in almost all of the studies conducted in the low-data regime. In particular, we see that when this line of work was being conducted the best performing algorithm in the high-data regime was an inherently high capacity model, i.e. based on learning the state action value distribution. Hence, there are many cases in the literature (e.g. DRQ, OTR, DER, CURL, SimPLE, Efficient-Zero) where all the newly proposed algorithms in the low-data regime are being compared to an algorithm that inherently produces a higher capacity model under the implicit assumption that an algorithm that is state-of-the-art in the high-data regime must be the state-of-the-art in the low-data regime. The large scale experiments provided in Section 6 demonstrate the impact of this implicit assumption and provide a guideline for a principled analysis and evaluation. In particular, the results reported in Section 6 prove that the performance profile of an algorithm in the high-data regime does not monotonically transfer to the low-data regime. Due to this extensive focus throughout the literature on low-data regime comparisons to algorithms that inherently learn higher capacity models, we provide additional theoretical analysis for the empirically observed sample complexity results in the low to high-data regime in deep reinforcement learning. The following proposition demonstrates a precise justification of these issues: whenever there are two different actions where the true mean state-action values are within ϵε, an approximation error of ϵε in total variation distance dTVd_TV for (s,a)D(s,a) of one of the actions can be sufficient to reverse the order of the means. Proposition 4.1 (Sufficiency of error of ϵε in total variation distance). Fix a state s and consider two actions a,a^a, a. Let (s,a)D(s,a) be the true state-action value distribution of (s,a)(s,a), and let (s,a)∼(s,a)Z(s,a) (s,a). Suppose that [(s,a)]=[(s,a^)]+ϵE[Z(s,a)]=E[Z(s, a)]+ε. Then there is a random variable Y such that dTV(,(s,a))≤ϵ and [(s,a^)]≥[].d_TV(Y,Z(s,a))≤ε\> and \>E[Z(s, a)] [Y]. The proof is provided in the supplementary material. Proposition 4.1 shows that to have the correct ranking of the actions the state-action value distribution must be learnt with error at most ϵε. Standard results on sample complexity for discrete distributions then imply that algorithms that learn the state-action value distribution with fixed support size k, i.e C51, require k/ϵ2k/ε^2 samples to achieve total variation distance at most ϵε. More advanced algorithms such as QRDQN and IQN do away with the assumption that the support is known. This allows a more flexible representation in order to more accurately represent state-action values, but, as we will show, leads to a further increase in the sample complexity. The QRDQN algorithm models it as a uniform mixture of N Dirac deltas on the reals i.e. (s,a)=1∑i=1δθi(s,a)Z(s,a)= 1N _i=1^N _ _i(s,a), where θi(s,a)∈ℝ _i(s,a) is a parametric model. Proposition 4.2 (Sample Complexity with Unknown Support). Let >ℳ≥2N>M≥ 2, ϵ>ℳ4ε> M4N, and θi∈ℝ _i for i∈[]i∈[N]. The number of samples required to learn a model of the form =1∑i=1δθiZ= 1N _i=1^N _ _i to within total variation distance ϵε is Ω(ℳϵ2) ( Mε^2 ). The proof is provided in the supplementary material. Note that the lower bound in Proposition 4.2 can be significantly larger than k/ϵ2k/ε^2 samples. Median Mean 20th th Percentile Median Mean 20th th Percentile Figure 2: Up: Human normalized median, mean and 20th th percentile results for the dueling algorithm, C51, IQN and QRDQN in the Arcade Learning Environment 100K benchmark. Down: Human normalized median, mean, and 20th th percentile results for the dueling algorithm, C51, IQN and QRDQN in the high-data regime towards 200 million frame. Table 1: Large scale comparison of Q-based deep reinforcement learning algorithms with human normalized mean, median and 20th th percentile results in the Arcade Learning Environment 100K benchmark for DQN (Mnih et al. 2015), deep Double-Q (Hasselt et al. 2016), dueling (Wang et al. 2016), Prior (Schaul et al. 2016), C51, QRDQN and IQN (Dabney et al. 2018a). Algorithms Human Normalized Median Human Normalized Mean 20th th Percentile DQN 0.0481± 0.0036 0.1535± 0.0119 0.0031± 0.0032 Double-Q 0.0920± 0.0181 0.3169± 0.0196 0.0341± 0.0042 Dueling 0.2304± 0.0061 0.2923± 0.0060 0.0764± 0.0037 C51 0.0941± 0.0081 0.3106± 0.0199 0.0274± 0.0024 QRDQN 0.0820± 0.0037 0.2171± 0.0098 0.0189± 0.0031 IQN 0.0528± 0.0058 0.2050± 0.0123 0.0091± 0.0011 Prior 0.0840± 0.0018 0.2792± 0.0123 0.0267± 0.0042 5 Principled Evaluation Framework In Section 6, we systematically explain and discuss the underlying design paradigms, the implicit assumptions and the methodological choices made in deep reinforcement learning research that led to incorrect conclusions. In this section we introduce the principled evaluation framework to ensure the research progress we obtain in deep reinforcement learning is reliable and scientifically robust. I. Assumptions matter: Performance rankings across regimes are non-monotone. I. Biases in Evaluation: Including algorithms in the comparison benchmark based on the monotonicity assumption will create biased evaluation. I. Core Algorithms: Core algorithms must be included in the comparison benchmarks. IV. Inherent Capacity: Inherent capacity and dimensionality will provide insights on performance rankings across regimes. V. Biases in Datasets: Creating datasets based on the monotonicity assumption will create biased benchmarks. 6 Large Scale Empirical Analysis The empirical analysis is conducted in the Arcade Learning Environment (ALE) (Mnih et al. 2015). The Double Q-learning algorithm is trained via Hasselt et al. (2016) initially proposed by van Hasselt (2010). The dueling algorithm is trained via Wang et al. (2016). The prior algorithm refers to the prioritized experience replay algorithm proposed by Schaul et al. (2016). The experiments are run with Haiku as the neural network library, Optax (Hessel et al. 2020) as the optimization library, and RLax for the reinforcement learning library (Babuschkin et al. 2020). All of the results are reported with the standard error of the mean. For the full list of algorithms, details on the hyperparameters, direct references and the detailed explanations of the baselines please see the supplementary material. To provide a complete picture of the sample complexity we conducted our experiments in both low-data, i.e. the Arcade Learning Environment 100K benchmark, and high data regime, i.e. baseline 200 million frame training. Note that human normalized score is computed as follows: ScoreHN=(Scoreagent−Scorerandom)/(Scorehuman−Scorerandom) Score_ HN=( Score_agent- Score_random)/( Score_human- Score_random). Alien Amidar Assault Asterix BankHeist ChopperCommand Hero JamesBond Kangaroo CrazyClimber MsPacman FrostBite RoadRunner Seaquest UpNDown Qbert Figure 3: The learning curves of Alien, Amidar, Asterix, BankHeist, ChopperCommand, Hero, CrazyClimber, JamesBond, Kangaroo, MsPacman, FrostBite, Qbert, RoadRunner, Seaquest and UpNDown with dueling architecture, C51, IQN and QRDQN algorithms in the Arcade Learning Environment with 100K environment interaction training. Implicit Assumptions on Monotonicity Cause Suboptimal and Incorrect Conclusions. Our extensive large-scale empirical analysis demonstrates that a major line of research conducted in the past five years resulted in incorrect conclusions. We show that a simple baseline algorithm from 2016 (Wang et al. 2016), by a systematic methodological choice was never included in the comparison benchmark, following the implicit assumption that appears in all of the recent line of research that we have discussed in detail in Section 4. We demonstrate that this baseline algorithm in fact performs much better than many recent algorithms that claimed to be better than the baselines, even including algorithms that are specifically built on top of the baseline algorithm. Figure 3 reports learning curves for the IQN, QRDQN, dueling and C51 in the Arcade Learning Environment low-data regime benchmark. These results demonstrate that the simple base algorithm dueling performs significantly better than a series of algorithms that were included in the comparison benchmark which inherently produced higher capacity models when the training samples are limited. Note that DRQ uses the dueling architecture without any high capacity inducing components. One intriguing takeaway from the results provided in Table 1 and Figure 4111DER2021 2021 refers to the re-implementation with random seed variations of the original paper data-efficient Rainbow (i.e. DER2019 2019) by van Hasselt et al. (2019). OTR refers to further implementation of the Rainbow algorithm by Kielak (2019). DRNeurIPSQ NeurIPS refers to the re-implementation of the original DRQ algorithm with the goal of achieving reproducibility with variation on the number of random seeds (Agarwal et al. 2021). is the fact that the simple baseline dueling algorithm performs 15% better than the DRNeurIPSQ NeurIPS implementation, and 11% less than the DRICLRQ ICLR implementation instead of 82% gain reported in the original paper. Providing Direct Comparison to Core Algorithms. Algorithms that are built on top of a core reinforcement learning algorithm must provide a direct comparison to the algorithm they are built on top of. The case of DRQ demonstrates the significance of the direct comparison to the core algorithm. As our paper discovers and describes extensively, the monotonicity assumption on the performance ranking across regimes led a line of work to benchmark against certain algorithms in the low-data regime, assuming that if an algorithm has the highest performance in the high-data regime it must have the top-ranked performance in the low-data regime. However, as we pointed out in our theoretical analysis this is a dangerous and incorrect assumption. The results reported in Figure 1 and Figure 4 demonstrate that these implicit assumptions in fact lead to incorrect and suboptimal conclusions. Non-Monotonicity of Performance Ranking Across Regimes. Table 1 reports the human normalized median, mean and 20th th percentile results over all of the MDPs from the 100K ALE benchmark for DQN, Double-Q, dueling, C51, QRDQN, IQN and Prior. One important takeaway from the results reported in the Table 1 is the fact that one particular algorithm performance profile in 200 million frame training will not directly transfer to the low-data region as predicted by our theoretical analysis in Section 3. Figure 2 reports the learning curves of human normalized median, mean and 20th th percentile for the dueling algorithm, C51, QRDQN, and IQN. These results once more demonstrate that the performance profile of the simple base algorithm dueling is significantly better than any core algorithm which inherently produced higher capacity models that was included in the comparison benchmark of the extensive low-data regime literature when the number of environment interactions are limited. Sample Complexity of C51 Sample Complexity of IQN Overall Comparison Figure 4: Left: Number of samples, i.e. environment interactions, required by the base algorithms that inherently produce higher capacity models to achieve the performance level achieved by the dueling algorithm. Center: Number of samples required by IQN to achieve the performance level achieved by dueling. Right: Overall comparison of algorithms recently developed in the low-data regime ALE 100K benchmark to the dueling algorithm that was designed in the high-data region. Biases in the Evaluation Criteria. The original paper of the DRICLRQ ICLR algorithm (Yarats et al. 2021) benchmarks against data-efficient Rainbow (DER) (van Hasselt et al. 2019) which inherently learns a higher capacity model. Our results show that the fact that the original paper that proposed data augmentation for reinforcement learning, i.e. DRICLRQ ICLR, on top of the dueling algorithm did not provide comparisons against the core algorithm that they are built on, i.e. dueling (Wang et al. 2016), resulted in inflated performance profiles for the DRICLRQ ICLR algorithm. For a fair, direct and transparent comparison we kept the hyperparameters for the baseline algorithms in the low-data regime exactly the same with the DRICLRQ ICLR paper (see supplementary material for the full list and high-data regime hyperparameter settings). More intriguingly, the comparisons provided in the DRICLRQ ICLR paper to the DER and OTR algorithms report the performance gained by DRICLRQ ICLR over DER is 82% and over OTR is 35%. However, if a direct comparison is made to the simple dueling algorithm as Table 1 demonstrates the performance gain is utterly restricted to 11%. Moreover, when it is compared to the reproduced results of DRNeurIPSQ NeurIPS our results reveal that in fact there is a performance decrease due to utilizing DRQ over dueling. Thus, while our paper introduces the foundations on the non-monotonicity of the performance profiles from large-data regime to low-data regime, it further provides the basis on how we can compare algorithms with a principled approach and scientific rigor allowing more concrete and accurate evaluation across data-regimes. Theoretical Analysis and the Inherent Bellman Error vs Dimensionality. The right and center plots of Figure 1 report regret curves corresponding to the theoretical analysis in Theorem 3.2 for various choices of the feature dimensionality d and the inherent Bellman error ℐI. In particular, the center plot shows the low-data regime where the number of episodes <1000K<1000, while the right plot shows the high-data regime where K is as large as 500000500000. Notably, the relative ordering of the regret across the different choices of d and ℐI is completely reversed in the high-data regime when compared to the low-data regime. Recall from Theorem 3.1 that the inherent Bellman error is a measure of the accuracy of function approximation under the Bellman operator corresponding to an MDP. Thus, the varying values of ℐI and d in Figure 1 correspond to a natural setting where increasing the number of model parameters (i.e. increasing d) corresponds to an increase in the accuracy of function approximation (i.e. a decrease in ℐI). Thus the results reported in Figure 1 demonstrate that, even in the natural setting where increased model capacity leads to increased accuracy, there can be a complete reversal in the ordering of algorithm performance between the low and high-data regimes. Figure 4 reports results on the number of samples required for training with the baseline algorithm that inherently produces higher capacity models to reach the same performance levels achieved by the dueling algorithm for every MDP from ALE low-data regime benchmark. These results once more demonstrate that to reach the same performance levels with the dueling algorithm, baseline algorithms that inherently learn higher capacity models require orders of magnitude more samples to train on. As discussed in Section 4, more complex representations for broader classes of distributions come at the cost of a higher sample complexity required for learning. One intriguing fact is that the original SimPLE paper in the low-data regime benchmarked against the Rainbow algorithm which is essentially a higher capacity model designed in the high-data regime by having the implicit assumption that the state-of-the art performance profile must transfer monotonically to the low-data regime. These instances of implicit assumptions also occur in DRICLRQ ICLR, CURL, SPR and Efficient-Zero (Ye et al. 2021) even when comparisons are made for more advanced algorithms such as MuZero. Datasets are Created and Founded on Implicit Assumptions. Thus far we have discussed the pivotal role of implicit assumptions on the algorithmic comparisons and developing baselines in deep reinforcement learning. However, this issue further extends back to even how the entire low-data regime benchmark was established, i.e. ALE 100K. The ALE 100K was initially created to allow researchers to work on a subset of games instead of full set of games used in the high-data regime (Kaiser et al. 2020), and this benchmark is currently used by any algorithm developed for the low data regime. However, the entire ALE 100K benchmark was in fact built on the selection bias of choosing games that performed better either with the proposed algorithm of the paper that proposed the entire benchmark (Kaiser et al. 2020), or with Rainbow, which we extensively demonstrated throughout the paper is an algorithm that is subjected to the implicit assumption bias on monotonicity across regimes. Thus the issues we explicitly discover and analyze in our paper are not limited to baselines but further extend to canonical benchmarks that we evaluate reinforcement learning algorithms on. Our paper discovers that the canonical methodological choices made in a major line of deep reinforcement learning research that is based on these implicit assumptions, give incorrect signals on why and what makes these algorithms work, and hence affect future research directions while misdirecting the possible current research efforts from ideas that could have worked during the algorithm design process. 7 Conclusion In this paper we aimed to answer the following questions: (i) How are the scaling laws of reinforcement learning formally characterized with respect to capacity and complexity? (i) What are the canonical methodological choices that fundamentally affect the progress in deep reinforcement learning research? and (i) What is the underlying theoretical relationship between monotonicity, the performance profiles and sample complexity regimes? To be able to answer these questions we provide theoretical analysis on the sample complexity of the baseline deep reinforcement learning algorithms. We conduct extensive experiments both in the low-data regime 100K Arcade Learning Environment and high-data regime baseline 200 million frame training. Both theoretical and empirical analysis provided in our paper demonstrate that the performance profiles of deep reinforcement learning algorithms do not have a monotonic relationship across sample complexity regimes. Our analysis reveals that the underlying assumption of the monotonic relationship of the performance characteristics and the sample complexity regimes is currently present in a major line of research including many recent state-of-the-art studies and this implicit assumption led these studies to result in incorrect conclusions. Our paper demonstrates that several baseline Q algorithms perform better than a line of recent algorithms claimed to be the state-of-the-art. Our paper establishes a principled analysis of deep reinforcement learning that characterizes the fundamental relationship between scaling, capacity and complexity. References R. Agarwal, M. Schwarzer, P. S. Castro, A. C. Courville, and M. G. Bellemare (2021) Deep reinforcement learning at the edge of the statistical precipice. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan (Eds.), p. 29304–29320. Cited by: footnote 1. I. Babuschkin, K. Baumli, A. Bell, S. Bhupatiraju, J. Bruce, P. Buchlovsky, D. Budden, T. Cai, A. Clark, I. Danihelka, C. Fantacci, J. Godwin, C. Jones, T. Hennigan, M. Hessel, S. Kapturowski, T. Keck, I. Kemaev, M. King, L. Martens, H. Merzic, V. Mikulik, T. Norman, J. Quan, G. Papamakarios, R. Ring, F. Ruiz, A. Sanchez, R. Schneider, E. Sezener, S. Spencer, S. Srinivasan, W. Stokowiec, and F. Viola (2020) The DeepMind Ecosystem External Links: Link Cited by: §6. M. G. Bellemare, W. Dabney, and R. Munos (2017) A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, Proceedings of Machine Learning Research, Vol. 70, p. 449–458. Cited by: §2. W. Dabney, G. Ostrovski, D. Silver, and R. Munos (2018a) Implicit quantile networks for distributional reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, J. G. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 1104–1113. Cited by: §2, Table 1. W. Dabney, M. Rowland, M. G. Bellemare, and R. Munos (2018b) Distributional reinforcement learning with quantile regression. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, S. A. McIlraith and K. Q. Weinberger (Eds.), p. 2892–2901. Cited by: §2. H. v. Hasselt, A. Guez, and D. Silver (2016) Deep reinforcement learning with double q-learning. Association for the Advancement of Artificial Intelligence (AAAI). Cited by: §1, Table 1, §6. M. Hessel, D. Budden, F. Viola, M. Rosca, E. Sezener, and T. Hennigan (2020) Optax: composable gradient transformation and optimisation External Links: Link Cited by: §6. M. Hessel, I. Danihelka, F. Viola, A. Guez, S. Schmitt, L. Sifre, T. Weber, D. Silver, and H. van Hasselt (2021) Muesli: combining improvements in policy optimization. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, M. Meila and T. Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, p. 4214–4226. Cited by: §1. M. Hessel, J. Modayil, H. van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. G. Azar, and D. Silver (2018) Rainbow: combining improvements in deep reinforcement learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, S. A. McIlraith and K. Q. Weinberger (Eds.), p. 3215–3222. Cited by: §1. L. Kaiser, M. Babaeizadeh, P. Milos, B. Osinski, R. H. Campbell, K. Czechowski, D. Erhan, C. Finn, P. Kozakowski, S. Levine, A. Mohiuddin, R. Sepassi, G. Tucker, and H. Michalewski (2020) Model based reinforcement learning for atari. In 8th International Conference on Learning Representations, ICLR 2020 [Spotlight Presentation], Cited by: §6. S. Kapturowski, V. Campos, R. Jiang, N. Rakicevic, H. van Hasselt, C. Blundell, and A. P. Badia (2023) Human-level atari 200x faster. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, Cited by: §1. K. P. Kielak (2019) Do recent advancements in model-based deep reinforcement learning really improve data efficiency?. CoRR. Cited by: footnote 1. E. Korkmaz (2024) Understanding and Diagnosing Deep Reinforcement Learning. In International Conference on Machine Learning, ICML 2024, Cited by: §1. E. Korkmaz (2025) Counteractive rl: rethinking core principles for efficient and scalable deep reinforcement learning. Advances in Neural Information Processing Systems 39: Annual Conference on Neural Information Processing Systems 2025, NeurIPS 2025 [Spotlight Presentation]. Cited by: §1. H. Lee, S. Phatale, H. Mansoor, T. Mesnard, J. Ferret, K. Lu, C. Bishop, E. Hall, V. Carbune, A. Rastogi, and S. Prakash (2024) RLAIF vs. RLHF: scaling reinforcement learning from human feedback with AI feedback. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Cited by: §1. V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, a. G. Bellemare, A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis (2015) Human-level control through deep reinforcement learning. Nature 518, p. 529–533. Cited by: §1, Table 1, §6. T. Schaul, J. Quan, I. Antonogloua, and D. Silver (2016) Prioritized experience replay. International Conference on Learning Representations (ICLR). Cited by: Table 1, §6. J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel, T. P. Lillicrap, and D. Silver (2020) Mastering atari, go, chess and shogi by planning with a learned model. Nat. 588 (7839), p. 604–609. External Links: Link, Document Cited by: §1. N. Stiennon, L. Ouyang, J. Wu, D. M. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano (2020) Learning to summarize with human feedback. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (Eds.), Cited by: §1. H. van Hasselt, M. Hessel, and J. Aslanides (2019) When to use parametric models in reinforcement learning?. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, and R. Garnett (Eds.), p. 14322–14333. Cited by: §6, footnote 1. H. van Hasselt (2010) Double q-learning. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta (Eds.), p. 2613–2621. Cited by: §6. Z. Wang, T. Schaul, M. Hessel, H. Van Hasselt, M. Lanctot, and Nando. De Freitas (2016) Dueling network architectures for deep reinforcement learning.. Internation Conference on Machine Learning ICML., p. 1995–2003. Cited by: §1, §2, Table 1, §6, §6, §6. D. Yarats, I. Kostrikov, and R. Fergus (2021) Image augmentation is all you need: regularizing deep reinforcement learning from pixels. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021 [Spotlight Presentation], Cited by: §6. W. Ye, S. Liu, T. Kurutach, P. Abbeel, and Y. Gao (2021) Mastering atari games with limited data. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021,, Cited by: §6. A. Zanette, A. Lazaric, M. J. Kochenderfer, and E. Brunskill (2020) Learning near optimal policies with low inherent bellman error. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, Vol. 119, p. 10978–10989. External Links: Link Cited by: Theorem 3.1.