A Large Scale Sample Complexity Analysis of Neural Policies in the Low-Data Regime
Authors: Ezgi Korkmaz
Venue: Submitted to ICLR 2023 (2023)

Abstract: The progress in reinforcement learning algorithm development is at one of its highest points starting from the initial study that enabled sequential decision making from high-dimensional observations. Currently, deep reinforcement learning research has had quite recent breakthroughs from learning without the presence of rewards to learning functioning policies without even knowing the rules of the game. In our paper we focus on the trends currently used in deep reinforcement learning algorithm development in the low-data regime. We theoretically show that the performance profiles of the algorithms developed for the high-data regime do not transfer to the low-data regime in the same order. We conduct extensive experiments in the Arcade Learning Environment and our results demonstrate that the baseline algorithms perform significantly better in the low-data regime compared to the set of algorithms that were initially designed and compared in the large-data region.

Under review as a conference paper at ICLR 2023
A LARGE SCALE SAMPLE COMPLEXITY ANALYSIS OF NEURAL POLICIES IN THE LOW-DATA REGIME
Anonymous authors Paper under double-blind review
ABSTRACT
The progress in reinforcement learning algorithm development is at one of its highest points starting from the initial study that enabled sequential decision mak- ing from high-dimensiona observations. Currently, deep reinforcement learning research has had quite recent breakthroughs from learning without the presence of rewards to learning functioning policies without even knowing the rules of the game. In our paper we focus on the trends currently used in deep reinforcement learning algorithm development in the low-data regime. We theoretically show that the performance profiles of the algorithms developed for the high-data regime do not transfer the low-data regime in the same order. We conduct extensive experiments in the Arcade Learning Environment and our results demonstrate that the baseline algorithms perform significantly better in the low-data regime pared to the set of algorithms that were initially designed and compared in the large-data region.
INTRODUCTION
Reinforeement 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. 2013). Fol- lowing this initial study several different highly successful deep reinforcement learning algorithms have been proposed (Hasselt et al.] [2016b] Wang et al.] [016)] Hessel et al. [0018] (021) from target- ing different architectural ideas employing estimators 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 of amount of publications focused on push- ing the performance bounds of deep reinforcement learning policies in the low-data regime (aarats) al. 2021 Ye et al., 2021] Kaiser et al.) 2020 van Hasselt al., 20199: Kielak 2019) (i.e. with one hundred thousand environment interaction training). Several different unique ideas in current reinforcement learning research, from model-based reinforcement learning to increasing sample ef- ficiency with observation regularization, gained acceleration in several research directions based on policy performance comparisons demonstrated in the Arcade Learning Environment 100K bench- mark. However, we demonstrate that there is a significant overlooked assumption being made in this line of research without being explicitly discussed. This implicit assumption, that is commonly shared amongst a large collection of low-data regime studies carries significant importance due to the fact that these studies shape future research directions with incorrect reasoning; hence, influenc- ing the overall research efforts put in for particular research ideas for several years following. Thus, in our paper we target this implicit assumption and aim to answer the following questions:
How can we theoretically explain the relationship between asymptotic sample complexity versus the low-data regime sample complexity in deep reinforcement learning?
How would the performance profiles of deep reinforcement learning algorithms designed for the high-data regime transform to the low-data regime?
Can we expect the performance rank of algorithms to hold with variations on the number of samples used in policy training?
Hence, to be able to answer the questions raised above in our paper we focus on sample complexity in deep reinforcement learning and make the following contributions:

---

Under review as a conference paper at ICLR 2023
We provide theoretical foundation the conttransferability of the performance profiles of deep reinforcement learning algorithms designed for the high-data regime to the low-data regime.
We theoretically demonstrate that the performance profile has a non-monotonic relation- ship with the asymptotic sample complexity and the low-data sample complexity region. Furthermore, we prove that the sample complexity of distributional reinforcement learning is higher than the sample complexity of baseline deep Q-network algorithms.
We conduct large scale extensive experiments for variety of deep reinforcement learning baseline algorithms in both the low-data regime and the high-data regime Arcade Learning Environment benchmark.
We highlight that recent algorithms proposed and evaluated in the Arcade Learning En- vironment 100K benchmark are significantly affected by the implicit assumption on the relationship between performance profiles and sample complexity.
2 BACKGROUND AND PRELIMINARIES
2.1 DEEP REINFORCEMEN LEARNING
The reinforcement learning problem formalized as a Markov Decision Process (MDP) represented as tuple (S, A, P, R, Pa) where S represents the state space, A represents the set of actions, P represents the transition probability distribution on x A S, R reward function, and 7 E (0, represents the discount factor. The aim in reinforcement learning is to learn an optimal policy (s, a) that maps state observations to actions т - A(A) that will maximize expected cumulative discounted rewards.
A + represents the
R = Bes (x(e))
Σ E''R(sen (t,
This objective is achieved by constructing state-action value function that learns for each state- action pair the expected cumulative discounted rewards that will be obtained if action E A is executed in state E S.
@(sr, = R(s,, an 8641) + Σ
In settings where the state space and/or action space is large enough that the state-action value function Q(s, a) cannot be held in a tabular form, a function approximator used. Thus, for deep reinforcement learning the Q-function is approximated via deep neural networks.
0t+1 + a(R(s at $141) 7 (S arg max ((s++1, a; (.);;,)))
Q(st, az; 0,) O.) Vo, Q(sr, ax; 0z).
Dueling Architecture: At the end of convolutional layers for given deep Q-Network, the dueling architecture outputs two streams fully connected layers for both estimating the state values (ss) and the advantage A(s, for each action in given state
A(s, a) Q(s, a) max ((s,a)
(3)
In particular, the last layer of the dueling architecture contains the forward mapping
Q(s, a, 8) Vss; + (A(s, - max A(s, a(s,a';0,a)) a))
(4)
a'EA
where 0 represents the parameters the convolutional layers and a and 3 represent the parameters of the fully connected layers outputting the advantage and state value estimates respectively.
Distributional Reinforcement Learning: The baseline distributional reinforcement learning algo- rithm C51 was proposed by Bellemare al. (2017). The projected Bellman update for the 4t atom computed as
T 2
Zzl 10
(o(s, Σ
(S141 max IE,2g (8141, a))
(5)
Az
AEA
2

---

Under review as a conference paper at ICLR 2023
where Umin + iA 0 S /V represents the set of atoms in categorical learning, and the atom probabilities are learnt as parametric model
el:(tci)))
Ta (5 max (s;,as Σj (ls()))))) where As =
Umax
Umin
(6)
Following this baseline algorithm Dabney et al. 2018b) proposed the QRDQN algorithm to learn the quantile projection of the state-action value distribution
T (st, ax) = R(s ae 8(+1) + 2 arg max Ez- ((
aEA
with 8:+11 ~ (() at) where Z E Z represents quantile distribution an arbitrary value function. Following this study Dabney et al. (2018a) proposed the IQN algorithm (i.e. implicit quantile networks) to learn the full quantile function instead of learning discrete set of quantiles as in the QRDQN algorithm. The IQN algorithm objective is minimize the loss function
X
c
E K
(8,4 Pa (R((R ar S441) + 22, (8e4 arg max Q,r(s,, a.) 28, (st, a.)
(8)
where P8 represents the Huber quantile regression loss, and 23 (2))3333(0)) Note that
28 == (6) the quantile function of the random variable Z d E 10.
3 LOW-DATA REGIME VERSUS ASYMPTOTIC PERFORMANCE
The high-level message of our empirical results is that comparing the asymptotic performance of two reinforcement learning algorithms does necessarily give useful information their relative performance in the low-data regime. In this section we provide mathematical motivation for this claim in the setting of finite-horizon MDPs with linear function approximation. In particular, finite horizon MDP is represented as a tuple (S, A, P, R, H) where S is the set of states, and A represents the set of actions. For each timestep E [ (1..... H}, state s, and action the transition probability kernel P $t. a,) gives the probability distribution over the next state, and the reward (&t, de, 8t+1) gives the immediate rewards. A non-stationary policy म = (,,,,..., TH) induces a state-action value function given by
(s ae) (st, des 8141) + Ee (n)a)))
sh41)))s44))) (1+1) sts az
where we let (s) be the action taken by the policy π in state and the corresponding value function (s.) (st, π (s:)). The optimal non- non-stationary policy x has value function V/2 V. (st) satisfying
VI (st) sup V.T (s:).
(10)
The objective to learn a sequence of non-stationary policies &² for E {I,..., XC} while interact- ing with unknown MDP in order to minimize the regret, which is measured asymptotically over K. episodes of length H.
REGRET = Σ (vi() E((i(t)) VT" v+(()1)
(11)
k=1
where =t E the starting state the k-th episode. words, regret sums up the gap between the expected rewards obtained by the sequence of learned policies x and those obtained by xt when learning for K episodes. In the linear function approximation setting there is a feature map Φi S x A - d for each t [?[] that sends state-action pair (s, to the dy-dimensional vector 6s(s, a). Then, the state-action value function (1 04) is parameterized by a vector 9 E de so that (8,)( a,) á, TT e,,
Recent theoretical work in this setting Zanette et al. 2020 gives an algorithm along with a lower bound that matches the regret achieved by the algorithm up logarithmic factors.
3

---

Under review as a conference paper at ICLR 2023
Theorem 3.1 (Zanette al. (2020)). Under appropriate normalization assumptions there is algorithm that learns a sequence of policies x achieving regret
H
REGRET(K) = Ô
Σ diVK + Σ V d
(12)
where I is the intrinsic Bellman error. Furthermore, this regret bound is optimal for this setting up logarithmic factors de, K and H whenever K. (((E de)²), in the sense that for any level of intrinsic Bellman error I, there exists class of MDPs where any algorithm achieves at least as much regret on at least one MDP in the class.
Utilizing this theorem performance in the asymptotic and low-data regimes.
then prove the following proposition the relationship between the
Proposition 3.2. For every > a > 8 > O, there exist two thresholds > 1, and a class of finite-horizon MDPs and feature maps or each of dimension de such that
1. Every algorithm receives regret at least REGRET(K) = = (aK. after K. L episodes.
2. There exists an algorithm receiving regret REGRET(K)) = Ô (BIC) after K. 2 U episodes.
Proof. Let - Vil
3 and apply the lower bound of Theorem 3.1 with intrinsic Bellman error
I. Let C = O( (a- By2
EE 2² Then after K. episodes for K. s C, the regret of any algorithm on the class of MDPs guaranteed by the theorem is at least
H
REGRET(X) = 5
Σ
dovk +
VoIK
=Ω
Σ 1=1
de divk K + BK
1=1
1=1
= 5
(a (a- BLVK
Σ
de
+ BK
+BK
2 ái((a -)K + 3K)
(aKC)
where the second equality follows from the choice of I, and the inequality from the fact that K. s 0( (T- (Σ d)) Next fix any constant 0 and let ((E ' de) r
Then for
2 u episodes the algorithm guaranteed by Theorem 3.1 achieves regret
H
H
REGRET( Ō
Σ
VK +
VdIK
= Ô Σ de d 3K
1=1
< OK + BK) = Ô (BK)
where the inequality follows from the bound K. 2 u = 1 d) TTx).
Intuitively Proposition 3.2 shows that in the linear function approximation setting, the gap between performance in the low-data regime (K. < episodes) and the high-data/asymptotic regime (K > U episodes) can be arbitrarily large. Thus, comparisons between algorithms in the asymptotic/high- data regime are not informative when trying to understand algorithm performance with limited data.
4 MEAN ESTIMATION VERSUS LEARNING THE DISTRIBUTION
To obtain theoretical insight into the larger sample complexity exhibited by distributional reinforce- ment learning we consider the fundamental comparison between learning the distribution ran- dom variable X' versus only learning the mean [E[2'. In base distributional reinforcement learning the goal is to learn a distribution over state itate-action values that has finite support. Thus, to get fun- damental understanding of the additional cost of distributional reinforcement learning, compare the sample complexity of learning the distribution of a finitely supported random variable with that of estimating the mean.

---

Under review as a conference paper at ICLR 2023
Proposition 4.1. Let X be real-valued random variable with support exactly i known values. Further, assume [X] < and let >>> O. Any algorithm that learns the distribution P(2) within total variation distance requires 2(k/c2) samples, while there exists algorithm estimate B[X] to within error using only O(1/e)) samples.
Proof. See appendix for the full proof.
Although Proposition 4. proves that distributional reinforcement learning has an intrinsically higher sample complexity than that of standard Q-learning, it does not provide insights into the comparison of an error of the mean with an error of in total variation distance. Hence, the following proposition demonstrates precise justification of the comparison: whenever there are two different actions where the true mean state-action values are within e, an approximation error of in total variation distance for the state-action value distribution of one of the actions is sufficient to reverse the order of the means.
Proposition 4.2. Fix state 8 and consider two actions a, a'. Let ((8,0 8, a) be the random variable distributed the true state-action value distribution of (8,a), and ((s a be the same for (8, a') Suppose that TE| (s, a)] = E[X(s, ('), + 6. Then there is a random variable y such that
(r, Se and [[[[(1 d')) RD).
Proof. Let be the infimum
=" inf E |[/ =-
(13)
i.e. r" is the first point in IR such that (s, a) takes values at least r" with probability exactly c. Next let the random variable y be defined by the following process. First, sample the random variable X(ss, a). If X(s a) 2 r", then output T" - 1. Otherwise, output the sampled value of (s)
Observe that the probability distributions of y and X's, a) are identical except at the point r" and on the interval [r", oo). Let be the Lebesgue measure on R. By construction of y the total variation distance is given by
2 //1
1
drv(Y,
= = =] du((2)
1 =T -- 11 -P) -" -1] 1]]
1
1
= PP =|| du(x) 2 + E.
2
(x)))))
Next note that the expectation of y is given by
EDI = c(7" - 1)+
2P(X(s, a) = dl(2)
(-00,7*)
c(7" 1) + a) fx-
2P x1) = du(z)
S ((T" 1) + E|x'(s, a)] -
E| a)] -
where the inequality follows from the fact that X' takes values larger than 7" with probability
To summarize, Proposition shows that, in the case where the mean state-action values are within unless the state-action value distribution is learned to within total-variation distance the incorrect action may be selected by the distributional reinforcement learning policy. Therefore, is natural to compare the sample complexity of learning the state-action value distribution to within total- variation distance e with the sample complexity of simply learning the mean to within error e, as is done in Proposition 4.1
5

---

Under review as a conference paper at ICLR 2023
5 SAMPLE COMPLEXITY WITH UNKNOWN SUPPORT
The setting considered in Proposition 4.1 most readily applies to the base distributional reinforce- ment learning algorithm C51, which attempts to directly learn a discrete distribution with known support in order to approximate the state-action value distribution. However, further advances in distributional reinforcement learning including QRDQN and IQN do away with the assumption that the support of the distribution is known. This allows more flexible representation in der to more accurately represent the true distribution on state-action values. but, as we will show, potentially leads els the distribution of state-action values as a uniform mixture of A Dirac deltas on the reals i.e. ((s, a) x Σ (s,(s,)) where (s a) R is parametric model.
further increase in the sample complexity. The QRDQN algorithm mod-
Proposition 5.1. Let > M 2 2, > required to learn a distribution of the form Z = 1 EN òø; to within total variation distance e is ((4)
M and 0; E for i E [M] The number of samples AN'
(M)
Proof. Let M 2 2 and D = (1,2,...., ,M S R. First we will show that any distribution p(2) supported on 2 E is within votal-variation distance 4N
& of a distribution of a random variable of
the form Z = v 2i-1 d0, for numbers 0g 'D. Indeed we construct such distribution as follows. First let p(z) be the rounded distribution obtained by rounding each probability p(z) to the nearest integer multiple of 4. The total variation distance between p(z) and p(z) is given by
N
N.
Σ
p(=) p(=)1 <
1 Σ
1 M 2N
(14)
4N"
Next partition the set of 0, into M groups G1, 92,...,, 9M, where group 9. has size Nf(=) (this
size is an integer by construction of p). Finally, for each 0, E G3 assign 0, 2. Thus for 2
Li=1 do. we have for each E D
N
P = Σ 10, = =]
N 16 = F(2).
(15)
Therefore, any distribution p(z) can be approximated to within total variation distance IV by distribution of the prescribed form. Thus, by the sample complexity lower bounds for learning discrete distribution with known support, for any M at least M samples are required to learn IN
M
22
distribution of the form
1 A.V. 50.- N
Depending the choice of parameters, the lower bound in Proposition 5.1 can be significantly
larger than that of Proposition 4.1 For example if the desired upproximation error is one can
N.. take M = T. In this case if the value of k in Proposition 4.1 satisfies k = o(N). then the sample complexity in Proposition 5.1 asymptotically larger than that of Proposition
6 LARGE SCALE EXPERIMENTAL INVESTIGATION
The experiments are conducted in the Arcade Learning Environment (ALE) (Bellemare et al. 2013
The Double Q-learning algorithm trained via Double Deep Q-Network (Hasselt et al. 20160g 6a) ini- tially proposed by van Hasseli (201)). The dueling algorithm is trained via Wang et al. (2016). The prior algorithm refers the prioritized experience replay algorithm proposed by (Schaul et al. (2166). The distributional reinforcement learning policies are trained via the C51 algorithm, IQN and QRDQN. To provide a complete picture the sample complexity we conducted our exper- iments in both low-data, i.e. the Arcade Learning Environment 100K benchmark, and high data regime, i.e. baseline 200 million frame training. All of the results are reported with the standard error of the mean in all of the tables and figures in the paper. The experiments run with JAX (Bradbury et al.] 2018), with Haiku as the neural network library, Optax (Hessel et al., 2020 as the optimization library, and RLa for the reinforcement learning library (Babuschkin al. 2020

---

Under review as a conference paper at ICLR 2023
Alien
Amidar
Assault
Asterix
BankHeist
ChomerConnaad
JamesBond
Kangaroo
CrazClimber
MsPacman
FrostBite
RoadRunner
Seaquest
UpNDown
Qbert
Figure The learning curves 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. See appendix for the full learning curves.
More details on the hyperparameters and direct references to the implementations can be found in appendix. Note that human normalized score is computed as follows:
Scoreagent Scorerandom
ScoreHN Score Score
(16)
Figure reppors learning curves for the IQN, QRDQN, dueling architecture and C51 for every MDP the Arcade Learning Environment low-data regime 100K benchmark. These results demonstrate that the simple base algorithm dueling performs significantly better than any distributional algo- rithm when the training samples are limited. For fair, direct and transparent comparison we kept the hyperparameters for the baseline algorithms in the low-data regime exactly the same with the DR QICLR paper (see appendix for the full list and high-data regime hyperparameter settings). Note that the QRQ algorithm uses the dueling architecture without any distributional reinforcement learn- ing. One intriguing takeaway from the results provided in Table and the Figure 4 is the fact that the simple base algorithm dueling performs 15% better than the DR DR NeuriPS impiementation. and 1% less than the DRQ ICLR implementation. Note that the original paper of the DR DR QCTR algorithm provides comparison only to data-efficient Rainbow (DER) (van Hasselt al., 2019) which inher- ently uses distributional reinforcement learning. The fact that the original paper that proposed data augmentation for deep reinforcement learning (i.e. DR QiCLR) on top of the dueling architecture did not provide comparisons with the pure simple base dueling architecture (Wang et al. 2016) resulted inflated performance profiles for the DR QILRR algorithm.
More intriguingly, the comparisons provided in the DR QICLR paper the DER and OTR algorithms report the performance gained by DR QICLR over DER 82% and over OTR 35% However, if
202 refers to the re-implementation with random seed variations the original paper data-efficient Rainbow (i.e. DER 2019 by van Hasselt et al. (2019). OTR refers to further implementation of the Rainbow al- gorithm by Kielak 2019). DR D Neuntss refers to the re-implmmetationn of the original DRQ algorithm published ICLR as spotlight presentation with the goal of achieving reproducibility with variation on the number of random seeds (Agarwal al. 202T

---

Under review as a conference paper at ICLR 2023
332
1.0
509
Oriicie www.emattieene
0.7
-005
(177)
Median
Mean
20 Percentile
Figure 2: Up: Human normalized median, mean and 20th percentile results for the dueling algorithm, C, IQN and QRDQN in the Arcade Learning Environment 100K benchmark. Down: Human normalized median, mean, and 20th percentile results for the dueling algorithm, C51, IQN and QRDQN in the high-data regime towards 200 million frame
Large scale comparison of Q-based deep reinforcement learning algorithms with human normalized mean, median and 20th percentile results the Arcade Learning Environment 100K benchmark for DQN (Mnih et al. 2015), deep Double- Q learning (Hasselt et al. 2016a), dueling architecture (Wang et al. 2016). Prior (Schaul et al. 2016) C51, QRDQI and IQN.
Table 1:
Algorithms
Human Normalized Median
Human Normalized Mean 20th Percentile
DQN
0.0031
0.1535=0.0119 0.3169=0.01%
0.0031+0.0032
Double- Q
0.0920=0.0181
0.0341=0.0042
Dueling
0.2304=0.0061
0.2923=0.0060
0.0764=0.0037
C51
10941=0.0081
0.3106=0.0199
0.0274++0.002
QRD@N
0.0820=0.0037
0.0098
0.0189++0.003
IQN
0.0528=0.0058
0.2050=0.0123
0.009110.0011
Prior
0.0840=0.0018
0.2792-0.0123
0.026710.0042
direct comparison is made to the simple dueling algorithm as Table demonstrates with the exact hyperparameters used as in the DR QCLR paper the performance gain utterly restricted to 11%. Moreover, when it is compared to the reproduced results of D it turns out that there is a performance decrease due to utilizing the DRQ algorithm over dueling architecture. Thus, the fact that our paper provides foundations the transsseferrbbttty of the performance profile results from large-data regime to low-data regime can influence future research to have more concrete and accurate performance profiles for algorithm development in the low-data regime.
Table reports the human normalized median, human normalized mean, and human normalized t0th percentile results over all of the MDPs from the 100K Arcade Learning Environment benchmark for DQN, Double-Q, dueling, C51, QRDQN, IQN and prior. One important takeaway from the results reported in the Table is the fact that one particular algorithm performance profile in 200 million frame training will not directly transfer to the low-data region. Figure 2 reports the learning curves of human normalized median, human normalized mean and human normalized 20th percentile for the dueling algorithm, C51, QRDQN, and IQN in the low-data region. These results once more demonstrate that the performance profile of the simple base algorithm dueling significantly better than any other distributional reinforcement learning algorithm when the number of environment interactions are limited.
The left and center plots of Figure Proposition 3.2 for various choices of the feature dimensionality and the intrinsic Bellman error I. In particular, the left plot shows the low-data regime where the number of episodes IC < 1000, while the right plot shows the high-data regime where IC is as large as 500000. Notably, the relative ordering of the regret across the different choices of d and I is completely reversed in the high-data
3 report regret curves corresponding to the theoretical analysis in
8

---

Under review as a conference paper at ICLR 2023
Negthe
Higedblo Pogee
2dC 513
PV
0415 mot 30
320 ale Xir
Haman Nemalcalad Median Scores
Regret in the Low-data Regime Regret in the High-data Regime
Distributional vs Baseline Q
Figure 3: Left: Regret in the low-data regime. Center: Regret in the high-data regime. Right: Distributional vs baseline Q 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.
8
(215-
(47
200
203
3000
Sample Complexity of C51
Sample Complexity of IQN
Overall Comparison
Figure 4: Left: Number of samples (i.e. environment interactions) required by the base distribu- tional reinforcement learning algorithm to achieve the performance level achieved by the dueling algorithm. Center: Number of samples required by IQN achieve the performance level achieved by dueling. Right: Overall comparison of algorithms recently developed in the low-data regime ALE 100K benchmark to the ducling algorithm that were designed the high-data region.
regime when compared to the low-data regime. Figure reports results on the number of samples required for training with the baseline distributional reinforcement learning algorithm to reach the same performance levels achieved by the dueling algorithm for each individual MDP from the Ar- cade Learning Environment low-data regime benchmark. These results once more demonstrate that to reach the same performance levels with the dueling algorithm, the baseline distributional rein- forcement learning algorithm requires orders of magnitude more samples to train on. As discussed in Section 5 more complex representations for broader classes of distributions come at the cost of higher sample complexity required for learning.
One intriguing fact is that the original SimPLE paper provides a comparison in the low-data regime of their proposed algorithm with the Rainbow algorithm which is essentially an algorithm that is designed in the high-data region by having the implicit assumption that the state-of-the art perfor- mance profile must transfer linearly to the low-data region. These instances of implicit assumptions also occur QICL CURL, SPR and Efficient-Zero even when comparisons are made for more advanced algorithms such as MuZero.
7 CONCLUSION
In this paper we aimed to answer the following questions: (1) Do the performance profiles of deep reinforcement learning algorithms designed for certain data regimes translate approximately lin- early to a different sample complexity region?, and (ii) What is the underlying theoretical relation- ship between the performance profiles and sample complexity regimes? ? To be able to answer these questions we provide theoretical investigation on the sample complexity of the bascline deep rein- forcement learning algorithms. We conduct extensive experiments both in the low-data region 100K Arcade Learning Environment and high-data regime baseline 200 million frame training. Our results demonstrate that the performance profiles of deep reinforcement learning algorithms do not have a monotonic relationship across sample complexity regimes. The implicit assumption of the mono- tonic relationship of the performance characteristics and the sample complexity regions that exists in many recent state-of-the-an art studies has been overly exploited. Thus, our results demonstrate that several baseline Q algorithms are almost as high performing as recent variant algorithms that have been proposed and shown the state-of-the-art.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C. Courville, and Mare G. Belle- mare. Deep reinforcement learning at the edge of the statistical precipice. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Informa- lion Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 29304-29320, 2021.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci, Jonathan Godwin, Chris Jones, Tom Hennigan, Matteo Hessel, Steven Kapturowski, Thomas Keck, lurii Kemaev, Michael King, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, John Quan, George Papamakarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Wojciech Stokowiee, and Fabio Viola. The Deep- Mind JAX Ecosystem, 2020. URL http::tttp/.... / www.tttwwwooooooooooooooocootttt deepmindi
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael. Bowling. The arcade learning envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research,, pp. 253-279, 2013.
Mare G. Bellemare, Will Dabney, and Rémi Munos. 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, volume 70 of Proceedings of Machine Learning Re- search, pp. 449-458. PMLR, 2017.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. htt.huu.commggggg /ptg////ogeeaaxxoooo
Clément I. Canonne. A short note learning discrete distributions. 2020. UtLhttp://arxxit
org/abs abs/ 22t/2202..110 11457 cite arxiv:2002. 1457Comment: This is review article; its intent is not to provide new results, but instead gather known (and useful) ones, along with their proofs, in single convenient location.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for dis- tributional reinforcement learning. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stock- holm, Sweden, July 10- 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp- 1104-1113, PMLR, 2018a.
Will Dabney, Mark Rowland, Mare G. Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Pro- ceedings 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 Ed- ucational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 2892-2901. AAAI Press, 2018b
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Association for the Advancement of Artificial Intelligence (AAAT), 2016a.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Thirtieth AAAI conference on artificial intelligence, 2016b.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Sheila A. Mcllraith and Kilian Q, Weinberger (eds.). Proceedings of the Thirty-Secont 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, pp. 3215-3222, AAAI Press, 2018.
10

---

Under review as a conference paper at ICLR 2023
Matteo Hessel, David Budden, Fabio Viola, Mihacla Rosca, Eren Sezener, and Tom Hennigan.
Optax: composable gradient transformation and optimisation, in jax!, 2020. URL http://
github.comm wttpm///deeemm.n///pptaaaa.
Matteo Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theo- phane Weber, David Silver, and Hado van Hasselt. Muesli: Combining improvements in policy optimization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 4214 4226. PMLR, 2021.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learninn for atari. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Kacper Piotr Kielak. Do recent advancements in model-based deep reinforcement learning really improve data efficiency? CoRR, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, are Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattic, Amir Sadik, Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518: 529-533, 2015.
Tom Schaul, John Quan, Ioannis Antonogloua, and David Silver. Prioritized experience replay. International Conference on Learning Representations (ICLR), 2016.
Hado van Hasselt. Double q-learning. In John D. Lafferty, Christopher K. I. Williams, John Shawe- Taylor, Richard S. Zemel, and Aron Culotta (eds.), Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceed- ings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pp. 2613-2621. Curran Associates, Inc., 2010.
Hado van Hasselt, Matteo Hessel, and John Aslanides. When to use parametric models in reinforce- ment learning? In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 14322-14333, 2019.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Marc Lanctot, and Nando. De Fre- itas. Dueling network architectures for deep reinforcement learning. Internation Conference on Machine Learning ICML. pp. 1995-2003, 2016.
Denis Yarats, Ilya Kostrikov, and Rob Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. In 9th International Conference on Learning Represen- tations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Weirui Ye, Li: Shaohuai, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Masteri:ng atari games witth limited data. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 25476-25489 2021.
Andrea Zanette, Alessandro Lazaric, Mykel J. Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In Proceedings of the 37th Interna- tional Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 10989. PMLR, 2020. URL http: / http:://proceedings mlr, m html
11

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 RESULTS ON THE COMPLETE LIST OF GAMES FROM ARCADE LEARNING ENVIRONMENT 100K BASELINE
Table reports the average scores obtained by the human player, random player, baseline Q- based gorrtthmm dueling architecture, baseline distributional reinforcement learning algorithm C51, QRD QN and IQN across all the games in the Arcade Learning Environment 100K baseline. These results once more demonstrate that the baseline Q-based algorithm performs significantly better than any distributional reinforcement learning algorithm as has also been explained in detail in Section
Table 2: Average returns for human, random, dueling Wang al. 2016 C51, QRD QN and IQN
across all the games in the Arcade Learning Environment 100K benchmark.
Games
Human
Random
C51
QRD@N
ION
Ducling
Alien
7127.7
227.8
547.16
509.57
330.81
705.58
Amidar
1719.5
5.8
78.41
55.70
74.98
199.31
Assault
742.0
222.4
465.30
314.58
488.55
503.82
Asterix
8503.3
210.0
475.90
367.32
286.26
705.16
BankHeist
753.1
14.2
22.81
21.53
18.17
243.19
BattleZone
37187.5
2360.0
2728.52
6238.27
3105,70
6880.37
Boxing
12.1
0.1
9.60
2.03
12.41
1.68
Breakout
30.5
1.7
11.35
16,50
15.09
8.28
ChopperCommand
7387.8
811.0
831.83
752.51
629.04
1313.90
Climber
35829.4
10780.5
71776.14
21366.42
22649.4 .44
17039.
DemonAttack
1971.0
152.1
789.09
198.01
1035.17
694.42
Freeway
29.6
0.0
20.42
5.98
19.37
5.93
FrostBite
4334.7
65.2
215.25
218.11
192.33
259.18
Gopher
2412.5
257.6
791.83
576.19
466.81
429.85
Hero
30826.4
1027.0
7097.47 42
1108.44
1322.63
8210.53
Jameshond
302.8
29.0
43.85
108.71
26.23
296.46
Kangaroo
3035.0
52.0
301.01
120.60
294.46
1914.86
Krull
2665.5
1598.0
3744.04
2040.50
2319.74
2867.78
KungFuMaster
22736.3
258.5
6877.62
11574.02
1526.76
5367.90
Mspacman
6951.6
307.3
917.78
749.29
533.98
1355.21
Pong
14.6
-20.7
11.17
-7.49
-10.86
-4.20
PrivateEye
69571.3
24.9
-103.30
-6.32
33.83
100.00
Qbert
13455.0
163.9
528.30
590.05
582.72
1710.23
RoadRunner
7845.0
11.5
3993.34
400.59
1202.20
6031.80
Seaquest
42054.7
68.4
163.69
183.25
213.87
351.10
UpNdDown
11693.2
533.4
1970.28
1622.67
1552.27
3553.12
Figure reports the learning curves of the complete list of the games in the Arcade Learaning Envi- ronment 100K benchmark; in particular, for Alien, Amidar, Asterix, BankHeist, BattleZone, Boxing, Breakout, ChopperCommand, Hero, CrazyClimber, JamesBond, Kangaroo, PrivateEye, MsPacman, FrostBite, Qbert, RoadRunner, Seaquest, Pong, Gopher, DemonAttack, Krull, and UpNDown with dueling architecture WWng et al. (2016). C51, IQN and QRDQN algorithms with 100K environ- ment interaction training. The learning curves reported in Figure 5 demonstrate that the number of samples required to obtain the performance level achieved via the simple base ducling architecture is significantly higher for any distributional reinforcement learning algorithm. Note that the dis- tributional reinforcement learning algorithm C51 represents the state-action value distribution as a discrete probability distribution supported on 51 fixed atoms evenly spaced between pre-specified minimum and maximum value. In contrast, QR-DQN represents the value distribution as the uni- form distribution over larger number of atoms with variable positions on the real line. Thus, QR-DQN is able to more accurately approximate broader class of state-action value distributions. Finally, IQN parameterizes the quantile function of the state-action value distribution via deep neural network, leading to yet more flexible representation of the state-action value distribution. discussed Section 5 more complex representations for broader classes of distributions come at the cost of higher sample complexity required for learning.
12

---

Under review as a conference paper at ICLR 2023
Alien
Amidar
A Assault
Asterix
Benk
RattleZone
Boxing
BreakOut
aeneenaaioo ChopperCommand
DrmonAttack
Hero
JamesBond
Kangaroo
Krall
CranClimber
MsPacman
FrostBite
RoadRunner
Seaquest
UpNDown
Pong
Gopher
Qbart
PrivateEye
Figure 5: The learning curves of Alien, Amidar, Asterix, BankHeist, BattleZZnee Boxing, Breakout, ChopperCommand, Hero, CrazyClimber, JamesBond, Kangaroo, PrivateFyee MsPacman, FrostBite, Qbert, RoadRunner, Seaquest, Pong. Gopher, DemonAttack, Krull, and UpNDown with dueling ar- chitecture Wang al. (2016), C51, IQN and QRDQN algorithms in the Arcade Learning Environ- ment with IOOK environment interaction training.
A.2 REPRODUCIBILITY AND CONFIGURATION DETAILS
The hyperparameter settings of all of the algorithms in our paper. double- dueling, QRD@N, and IΩN for the high-data region are exactly the same with the original papers that proposed these algorithms the high-data region. See the hyperparameter settings in Hasselt et al. (2016) for double- Q, Wang et al. (2016) for dueling architecture, Bellemare al. (2017) for C51, Dabney et al. (2018a) for ORD@N, and Dabney et al. (2018b) for IQN.
For fair and transparent comparison, DRRR paper for all of the baseline Q algorithms in the low-data region. Note that DRQ is observation regularization study; hence the hyperparameters in the DRQ paper specifically tuned for the purpose of the paper besides tuning for the Arcade Learning Environment 100K low- data regime. We did not tune any of the hyperparameters for the baseline algorithms (i.e. dueling
kept the hyperparameters exactly the same with the
13

---

Number of atoms Under review as a conference paper at ICLR 2023
architecture and distributional reinforcement learning algorithms). Hence, it is even further possible to conduct hyperparameter tuning and get better performance profile results with the simple baseline ducling architecture. For the purpose of this paper kept the hyperparameters exactly the same with the DR Q paper. However, we would strongly encourage further research to conduct hyper- parameter optimization to obtain better results from the baseline dueling architecture in the low-data regime.
Table Hyperparameter settings and architectural details for the dueling algorithm, double- leamn- ing, C51, QRDQN, and IQN in the low-data regime of the Arcade Learning Environment.
Hyperparameters
Settings
Grey-scaling
True
Observation down-sampling
(84, 84)
Action repetitions
4
Frames stacked
4
Batch Size
32
Update
Double-Q
Max Frames per episode
108000
Evaluation exploration epsilon
0.01
Min replay size for sampling
1600
Max gradient
10
Discount factor
0.99
Maximum absolute rewards Training steps
1
100000
Evaluation steps
125000
Exploration epsilon decay frame fraction
0.0125
Gradient error bound
0.03125
Optimizer
Adam 1
Replay period every
n-step length Exploration
10
e-greedy
e-decay
5000
51
Number quantiles
201
Umax
10
Q-Network channels
8 x 8, 4 x 4,3 x 32,64,64
O-Neworrk filter size
Network stride
(4, 4), (2, (1, 512
Q Network hidden units
We have also tried the hyperparameter settings reported in the data efficient Rainbow (DER) paper for C51, IQN and QRDQN in the low-data regime. The performance results are provided in Table 4 for the hyperparameter settings of DER. As can be seen, the hyperparameter settings of DRQUCLR gave better performance results also for C51, IQN and QRDQN in the low-data region. The results in Table ! also align with the claims of the DER paper in which there was not been extensive hyperparameter tuning conducted to achieve the results provided, and is possible to obtain better results by further hyperparameter tuning.
Table 4: Human normalized mean, human normalized median, and human normalized 20th per- centile results for the C51 algorithm, QRDQN, and IQN in the low-data regime of the Arcade Learning Environment with the hyperparameter settings reported in the DER paper.
Algorithms
Human Normalized Median Human Normalized Mean
Human Normalized 20th Percentile
CSI
0.0400=0000038
0.1352+40.005
0.0163
QRD@N
0.0003
0.0778
-0.0012++0.00
IQN
0.0202+000020
0.0590+1.0139
-0.0035+0000331
14

---

Under review as a conference paper at ICLR 2023
A.3 MEAN ESTIMATION VERSUS LEARNING THE DISTRIBUTION
Let X be real-valued random variable with support on exactly k known values. Further, assume [ < 1 and let O. Any algorithm that learns the distribution P(X) within total variation distance requires ((k/e²) samples, while there exists an algorithm to estimate [|X] to within error using only O(1/e²) samples.
Proposition A.I (Proposition 4.1
Proof. Learning distribution with known discrete support of size k requires (2(k/e²) samples to achieve total variation distance at most e with constant probability (Canonne) 2020). On the other hand, let , be independent samples of the random variable X and consider the sample mean
Nn
X
X
(17)
The expectation is given by [[[]] = E[A] and the variance is o² = (x).
- Further, since
[ < 1 we have that (X) < and so 2 < 4. Hence, by Chebyshev's inequality
1
P | X S 2n
(18)
Thus with n 0()) samples, & is within [[ with constant probability.
15


Reviews:
[{"review_id": "v1uU6s9ySIC", "reviewer": "Reviewer_88qX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper explores both theoretically and empirically the following questions:\n\n1. Do the performance profiles of deep RL algorithms designed for certain data regimes (high-data regime) maintain monotonicity when tried in a different data regime (e.g. low-data regime)?\n\n2. What is the underlying theoretical relationship between the performance profiles and sample complexity regimes?\n\nSummary of theoretical results (in linear function approximation):\n- The gap between performance in the low-data regime and the high-data/asymptotic regime can be *arbitrarily large*. Thus, comparisons between algorithms in the asymptotic/high-data regime are not informative when trying to understand algorithm performance in the low-data regime. \n\n- Proves that distributional RL (with known finite support) has an intrinsically higher sample complexity than that of standard Q-learning.\n\n- Proves that the sample complexity of distributional RL (with unknown support) can be significantly worse than that with known support.\n\nThe empirical study extensively that the performance of basic RL baselines (dueling DQN and Double DQN) are significantly better in low-data regimes than the SOTA methods in large-data regimes (various distributional RL methods). Thus, establishing the non-monotonic relationship between the performance in one data regime to another. Experiments are based on ALE 100k vs. 200M.  ", "summary_of_the_review": "Please see my comment in the previous section on **Clarity, Quality, Novelty and Novelty**, which leads to my advocating for accepting this paper.", "strength_and_weaknesses": "**Strengths:**\n\n- The paper is very well written.\n\n- The theoretical results are followed immediately by intuitive conclusions, making the paper very easy to follow. \n\n- The arguments are made very systematically, with great flow.\n\n- The way in which they attack their questions from a theoretical viewpoint is very clever.\n\n- The experiments are nicely executed, and the results are reliable in my view. \n\n**Weaknesses:**\n\n- The argument that results don't translate monotonically from low-data regime to high-data regime or vice versa is effectively based on the assumption that distributional methods represent the highest-performing methods in high-data regime. This however is not really true in my view, as there currently are (and I'm sure there will be many more) non-distributional RL methods that are on par with or outperform distributional methods (e.g., if I remember correctly, Munchausen DQN [1] and Linear-Logarithmic DQN [2] methods are some such instances). As such, I feel the paper does not tell us much concretely on whether a general argument regarding Objective 2 (i.e. question of what is the relationship between sample complexity in different data regimes).\n\n**References:**\n\n[1] Nino Vieillard, Olivier Pietquin, Matthieu Geist (2020) *Munchausen Reinforcement Learning*. NeurIPS (Spotlight).\n\n[2] Mehdi Fatemi, Arash Tavakoli (2022) *Orchestrated Value Mapping for Reinforcement Learning*. ICLR.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "qrYz4zb-FU7", "reviewer": "Reviewer_kZsD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the performance of the RL algorithms within the low data regime. Extensive experiments are carried out to demonstrate how well the performance profiles influence the sample complexity.", "summary_of_the_review": "I have no more comments besides the comments above. Given the concern about the contribution and novelty of this paper, I don't think this paper meets the ICLR's bar.", "strength_and_weaknesses": "### Strength: \n\n- The paper is well-written and easy to follow. Extensive experiments well support the claimed result.\n- Analysing the relationship between the performance profiles and sample complexity sounds interesting to me.\n\n### Weakness:\n\n- The word `Neural` in the title is not well supported in the paper. The results in Section 3 are built on a linear approximation following (Zanette et al. 2020). Sections 4 and 5 are regarding the sample complexity based on the concentration. There's no neural network analysis in this paper.\n- The novelty of Section 3, especially Proposition 3.2 is not significant. It is just some direct result of applying some basic algebra given (Zanette et al. 2020) for linear function approximation. \n- The contribution of Section 4 is not enough. It suggests that knowing the mean value is not sufficient for generating a good policy. In addition, learning the distribution would be more expensive compared with learning the mean value. I don't think this result is a new result given the existing RL literature. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mvz2gwF8zp", "reviewer": "Reviewer_CAyy", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes, theoretically and empirically, the sample complexity of DQN-based algorithm on the ALE benchmark. It shows that the algorithms considered better in terms of asymptotic performance are actually worse than simpler baselines in the Atari 100k benchmark for sample efficiency.", "summary_of_the_review": "In short, while I believe the study of the behavior of existing algorithms in the data-efficient and asymptotic setting to be an important avenue of research, I find both the theoretical analysis and the position of the current version of the paper to be particularly misleading and I thus recommend rejection.", "strength_and_weaknesses": "Strengths:\n- The problem of detecting which algorithms are best depending of whether we are interested in data efficiency or asymptotic performance is very important;\n- The empirical comparison between different algorithms seems quite thorough.\n\nWeaknesses:\n- The paper tries to position itself as the first one discovering that reinforcement learning algorithms created with the goal of having better asymptotic performance are not automatically the best one in terms of data efficiency. This is very misleading, since this is a well-know problem (see, e.g., DER [van Hasselt et al., 2019]), and also reduces the overall contribution of this paper.\n- The theoretical results seem to be not very compelling. In particular, despite contextualized for linear function approximation, Proposition 3.2 appears to be trivially true for practically any type of reinforcement learning algorithm. Likewise, the idea that learning a distribution potentially requires more samples compared to an expected value is common knowledge; more interesting and relevant is the interaction of such a learning process with representation learning, which has been shown to be one of the crucial aspects behind the success distributional reinforcement learning and is no object in the analysis presented in the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-qCENM6WVbr", "reviewer": "Reviewer_gGx6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": " This paper aims to answer two questions, namely, \n\n(i) Do the performance profiles of deep\nreinforcement learning algorithms designed for certain data regimes translate approximately linearly to a different sample complexity region? \n\n(ii) What is the underlying theoretical relationship between the performance profiles and sample complexity regimes?\n\nTo answer the first question, the authors conducted analysis and experiments on distributional RL algorithms on different sample complexity regimes and discover that the relationship is not monotonic (namely, superior performance in one sample complexity regime does not indicate superior performance in the other sample complexity regime). To answer the second question, the authors proved that the gap between low-data and high-data regime performance could be arbitrarily large in the linear MDP case. ", "summary_of_the_review": "The topic is interesting and important, but the paper might need further preparation for publication, in my opinion.", "strength_and_weaknesses": "$\\textbf{Strength:}$ \n\n- The topic raised is interesting and important from both the theoretical and empirical perspectives. From the theoretical side, the common sense of \"high sample efficiency\" is mostly described by regret analysis, which aims to capture the long-term asymptotic performance of RL algorithms as the number of interaction rises. In contrast, in empirical studies, achieving \"high sample efficiency\" typically means beating SOTA on benchmarks with limited number of interactions. I am happy to see that the authors finally decide to look into the low-sample regime performance through the lens of recent theory analysis of sample efficient RL.\n\n$\\textbf{Weaknesses and Comments:}$\n\n- The issue raised in this paper is more of a conceptual issue to me. To \"gain superior performance with limited data/interaction\" may not be accurately described as \"achieving high sample efficiency\" and does not indicate superior performance in rich data settings, but it is still an important research direction in the RL study. \n\n- The discussion on distributional RL seems less related to the main point of this paper, though it is still related. The authors may wish to discuss more on how the performance of distributional RL is related to the point, namely, the relationship between performance profile and sample complexity regime. \n\n- How may random seeds are utilized for the experiments?  Also, the experiments are not sufficient to me. It would be better if authors could give a more comprehensive survey on recent advances in exploration (e.g., RND, ICM ...)\n\n- (Minor) The authors may wish to explicitly claim the implicit assumption behind exploration works (that is, algorithm performance transfers monotonically between the low-sample regime and high-sample regime, if I am on the right track of this paper) in the second paragraph of the introduction. \n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject