Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper investigate the role of optimization in value approximation with linear value function approximators leveraging tools from random matrix theory and random graph theory. The authors characterize the spectrum of the TD operator, and show that the resulting learning process demonstrates clear signatures of the double descent phase-transition near the critically parameterized cut-off.
strengths_and_weaknesses: The paper is well-written, and all of the proofs are correct as far as I understand. The result is relevant and is a necessary extension of the analysis on overparameterization in the supervised learning regime [^1]. 

A notable technical contribution is the introduction of a class of models for which the spectrum of TD can be computed. The experimental result is clearly presented and offers useful insight. The figures on the evolution of the maximum and minimum singular values, as well as the overall distribution in response to parameterization ratio and different types of graph clearly convey the main point of the paper.

[^1]: Kuzborskij and Szepesvári (no date) ‘On the role of optimization in double descent: A least squares study’, Advances in engineering education [Preprint].
questions: I think this paper is quite well-written as it is. I will update here if questions arise.
limitations: One of the issues that complicate the analysis of TD is the interplay between the sampling distribution, the transition matrix, and the function approximator itself. I think this work did a fantastic job.

It would obviously be beneficial to extend the analysis here to neural networks. However, I am not sure if the NTK regime is the best place as the authors indicated in the discussion because over-parameterized ReLU is just one way the network could be parameterized and it is known to contain bias towards low-complexity functions. Recent work [^2] [^3] have shown empirically how such issues could be addressed by modifying the parameterization itself.

Therefore instead of working with MLPs as they are, over-parameterized or not, the analysis offered here might just as well be abstract enough that it offers more insight than an analysis focused on particular types of overparameterized neural networks.

[^2]: Achiam, J., Knight, E. and Abbeel, P. (2019) ‘Towards Characterizing Divergence in Deep Q-Learning’, arXiv [cs.LG]. Available at: http://arxiv.org/abs/1903.08894.

[^3]: Yang, G., Ajay, A. and Agrawal, P. (2021) ‘Overcoming The Spectral Bias of Neural Value Approximation’, in International Conference on Learning Representations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a random graph model allowing to study the stability and optimization properties of the TD algorithm in RL. More specifically, this paper applies tools from random matrix theory to study the spectral distribution of the (projected) TD(0) operator and uses this understanding to study the behavior of the approximation and estimation error in different regimes of over- and under-parametrization as the size of the system diverges.
strengths_and_weaknesses: The paper is very well written, clearly introduces the reader to the fundamental concepts of random matrix theory that are needed to understand the results, and presents such results in a clear way. The paper addresses an important theoretical issue: understanding the role of overparametrization in RL, and does so, although under some relatively strong assumptions, discussing a nontrivial case and presenting some theoretical understanding of a previously unexplained phenomenon.. From a first reading of the supplementary material, the technical part of the paper seems sound. The numerics solidly corroborate the findings of the paper and hint to a new direction of research.

The main weakness of the paper is the significance: the model of random graph being investigated seems a bit artificial: it seems unclear from a first reading how many relevant problems in RL can be captured in this setting.
questions: My main question concerns the weakness highlighted above: I think the authors should stress in which sense the model they observe is a relevant one to the RL community, as else it might be perceived as being reverse-engineered.

If this is not possible this point should be discussed much more clearly in the conclusion as a limitation.
limitations: Depending on the answer to the previous question, the authors might have to address much more precisely the applicative limitations of the model being investigated.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the largely unexplored area of the overparameterization in RL and TD learning. 
strengths_and_weaknesses: Strengths: 
This paper studies the largely unexplored area of the overparameterization in RL and TD learning. 
It is a unique contribution, and the paper is well written. 

Weaknesses: 
The work includes interesting results, but the writing should be more syetematic for general readers. 
The presentation is rather sloppy. 
questions: Overall, the paper is well written and includes interesting results. Some comments to improve the paper are as follows. Please clarify them in the paper.  
1) This paper addresses off-policy TD learning. It is not clear until eq (2). It would be better to put more emphasis on that the paper considers off-policy TD.
2) Eq (2) would be be TD-learning because it does not include any samples. It is a determininstic algorithm . 
3) Needs some changes in expressions: e.g. "0 mean" can be replaced with "zero mean." What is the meaning of spectrum of TD?
4) What is the meaning of overparameterization in TD? Please clarify it in the paper. 
5) Overall, the paper is written based on languages used in deep learning fields. It would be better to consider readability for people in RL areas. 
6) More discussions are needed: why do we study spectrum of TD? 
limitations: The work includes interesting results, but the writing should be more syetematic for general readers.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper uses ideas from Random matrix theory to study the spectrum of the TD update operator under strong assumptions on the MDP graph. In doing so, the authors focus on the over-parameterized case where the number of parameters in the linear function approximation exceeds the total number of distinct (s, a) pairs. 


strengths_and_weaknesses: Strengths:

* Paper is well motivated and proposes making use of results from random matrix theory to analyze the spectrum of the TD operator.

Weaknesses:

* Section 3.2 appears weak, and unfortunately the assumptions here are very strong and a critical part of the paper. The justification for modeling the $P^\pi$ as a modification of a random graph is very unclear to me (Section 3.2) and this seems to be a key ingredient of the entire analysis.

* Motivation for several of the assumptions is clearly tractability but unclear takeaways from the analysis. This includes assumptions like random features, rank one transition matrix. The former seems okay but the latter is too strong and the justifications for this are very hand-wavy and unclear.

* Analysis of value estimation for TD learning under linear approximation has also been considered by Xiao et. al at ICLR 2022: https://openreview.net/forum?id=shbAgEsk3qM which the authors should discuss.



questions: * Proposition 4.1 assumes that the spectrum of the relevant matrix is real and positive but this can be easily violated which is the main challenge in going from least squares to the TD version. 

* In Proposition 4.2, again how can you justify assuming that the transition matrix is rank one just by taking the limit? This seems to be assuming away the main complexity of MDPs and lack of any structure in the graphs.

* There is a blurb about Wigner type matrices in Page 3, but I don't notice anything related in the rest of the paper. 

  

limitations: Adequate
review_title: null

Meta-review: metareview: The paper studies policy evaluation with linear TD(0) learning in the over-parameterized regime. Using random matrix and random graph theory, the paper characterizes the spectrum of the TD operator and use this to show that TD learning exhibits a double-descent phenomenon.

The reviewers found this technical paper to be clear and well-written. They also appreciated the novel analysis, extending results on learning in the important over-parameterized regime in supervised learning to reinforcement learning. However, there were also concerns about the limiting assumptions, in particular the asymptotically rank 1 transition matrix. The authors' response provided further discussion and motivation for this choice which the reviewers found convincing. Overall, while this paper does make strong assumptions, it also provides good insights and novel results that are likely to spark further research in this area. As a result, it is recommended to be accepted.
confidence: Less certain
Decision: Accept