Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper:  This paper aims to answer two questions, namely, 

(i) Do the performance profiles of deep
reinforcement learning algorithms designed for certain data regimes translate approximately linearly to a different sample complexity region? 

(ii) What is the underlying theoretical relationship between the performance profiles and sample complexity regimes?

To 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. 
strength_and_weaknesses: $\textbf{Strength:}$ 

- 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.

$\textbf{Weaknesses and Comments:}$

- 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. 

- 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. 

- 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 ...)

- (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. 






clarity,_quality,_novelty_and_reproducibility: See above. The authors may wish to add pointers to implementations adopted (I guess they are directly adopted from the source papers) for better reproducibility.
summary_of_the_review: The topic is interesting and important, but the paper might need further preparation for publication, in my opinion.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strengths:
- The problem of detecting which algorithms are best depending of whether we are interested in data efficiency or asymptotic performance is very important;
- The empirical comparison between different algorithms seems quite thorough.

Weaknesses:
- 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.
- 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.
clarity,_quality,_novelty_and_reproducibility: The paper is reasonably clear.

The quality of the experimental work is acceptable, but the theoretical results are not particularly surprising.

On the originality side, the paper tries to present itself as the first one recognizing a fundamental difference between algorithms configurations for asymptotic and data-efficient settings. 
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: ### Strength: 

- The paper is well-written and easy to follow. Extensive experiments well support the claimed result.
- Analysing the relationship between the performance profiles and sample complexity sounds interesting to me.

### Weakness:

- 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.
- 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. 
- 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. 
clarity,_quality,_novelty_and_reproducibility: - The paper is overall well written and easy to follow
- The distributional reinforcement learning is not quite clear to me. Many notations like $\mathcal Z, v_\max, v_\min$ are not well explained.
- I did not find the code for the reproducibility check.
- The novelty issue is discussed above
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper explores both theoretically and empirically the following questions:

1. 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)?

2. What is the underlying theoretical relationship between the performance profiles and sample complexity regimes?

Summary of theoretical results (in linear function approximation):
- 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. 

- Proves that distributional RL (with known finite support) has an intrinsically higher sample complexity than that of standard Q-learning.

- Proves that the sample complexity of distributional RL (with unknown support) can be significantly worse than that with known support.

The 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.  
strength_and_weaknesses: **Strengths:**

- The paper is very well written.

- The theoretical results are followed immediately by intuitive conclusions, making the paper very easy to follow. 

- The arguments are made very systematically, with great flow.

- The way in which they attack their questions from a theoretical viewpoint is very clever.

- The experiments are nicely executed, and the results are reliable in my view. 

**Weaknesses:**

- 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).

**References:**

[1] Nino Vieillard, Olivier Pietquin, Matthieu Geist (2020) *Munchausen Reinforcement Learning*. NeurIPS (Spotlight).

[2] Mehdi Fatemi, Arash Tavakoli (2022) *Orchestrated Value Mapping for Reinforcement Learning*. ICLR.


clarity,_quality,_novelty_and_reproducibility: The investigation is a very useful one, both from the theory and empirical sides. The paper is well-written and clear, with a nice and easy-to-follow flow. There may be other papers that have investigated similar questions, but to the best of my knowledge, no paper has investigated such questions in a focused manner and both from the theory and empirical sides, with empirical verifications focused on deep RL. 

**Questions:**

- Are the theoretical results of Section 4 currently only proven in the linear FA case?

**Minor:**

- Sec 2.1, line 3 of Par 1: $\mathcal{R}$ represents the **expected** reward function. Later in your equations (e.g. Eq 1) you use $\mathcal{R}(s,a,s')$, thus using $\mathcal{R}$ to refer both to the expected reward function and the deterministic reward function. The general form of a stochastic reward function is: $R \sim \mathcal{R}(.|s,a,s')$. I suggest using $R_t$ to refer to samples from $\mathcal{R}(.|s,a,s')$ in your equations, such as Eq 1.

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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
This paper studies the performance of deep RL algorithms in high-data and low-data regimes. The authors conducted analysis and experiments on distributional RL algorithms on different data-size regimes and discover that superior performance in one data-size does not indicate superior performance in the other regime. The authors proved that the gap between low-data and high-data regime performance could be arbitrarily large in the linear MDP case.

Strength:
- The topic is interesting and important from both the theoretical and empirical perspectives. 
- The paper is well-written and easy to follow. 
- The empirical comparison between different algorithms seems thorough.

Weakness:
- The discussion on distributional RL seems less related to the main point.
- The theoretical results seem to be not very compelling. The metareviewer also believes that theory is misaligned with the main argument in the paper: for instance, in Prop. 3.2, the lower bound is for "any algorithms," and the upper bound is for the "good algorithm" (of the high-data regime). It does not say anything about why the "good algorithm" in the low-data regime cannot beat other algorithms (e.g., a baseline algorithm).

justification_for_why_not_higher_score: The metareviewer believes the paper is not ready for publication. In addition to the valid concerns pointed out by the reviewers, the main theory in this paper does not seem convincing to prove their claim.
Decision: Reject