Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a convergence analysis of projected Neural TD - Temporal Difference learning using a neural network for function approximation, and a projection step onto a norm ball of fixed radius around the initial iterate. The authors show sublinear convergence with an approximation error of $\mathcal{O}(\epsilon + \frac{1}{\sqrt{m}})$, where $m$ is the width of all hidden layers of the network. The paper mainly builds on the idea of ``gradient splitting'' which was previously used to analyze TD learning with linear function approximation [Liu and Olshevsky, 2021].  
strength_and_weaknesses: I find the analysis and results of the paper interesting - quantifying the first order progress term using arguments from gradient splitting is a good idea. However, I feel the extension from linear -> neural network function approximation is fairly straightforward from a technical point of view. Straightforward extensions can make for good papers - my main complaint is that the authors need to do a much better job of putting their contributions in perspective of prior results. Some comments:

1) The three relevant papers are Cai et. al. (2019), Xu and Gu (2020) and Cayci et. al. (2021). The authors reference problems in that analysis - that the projection radius needs to shrink at a rate of $\mathcal{O}(m^{-1/2})$ -- but don't specifically compare the results in these papers to their results presented in Theorem 1. 

My understanding is that most of these papers also characterize the quality of solutions that Neural TD converges to - for example, see section 4 in Cai et. al. (2019) - the approximation error here may be non-vanishing but there is a characterization of the limit point in terms of the solutions of the projected Bellman equation. The results in Cayci et. al. (2021) seems stronger. In addition to provide a projection free analysis, they also give guidance about scaling the network width for a given value of target error. It seems that in their results, $\epsilon$ can be arbitrary large and there is now guidance on how to select $\omega$. 

I request the authors to provide a more detailed, clear and transparent comparison to past work - highlighting the strengths and weaknesses of their approach as well as results vis-a-vis past work. That would be immensely useful. Maybe an empirical comparison to projection free and max-norm scaling methods of Cayci et. al. (2021) is also useful. 

2) While the main paper is well written, I think the Appendix requires some work in clear writing. Instead of saying 'By Lemma A.5 and eq(13)' can you kindly write out each expression and bound term by term? Can the equations be properly numbered to show how '$g(\theta_t)$ can be rewritten as' .. Similar comments go for the proof of non i.i.d case. I assume most inequalities to be correct (since the resulting bounds make sense), I don't think these have been properly justified. I think it is really bad to put the onus on reviewers to parse badly written proofs - the burden must be on the authors to write in a clear and easy to follow manner.


 
clarity,_quality,_novelty_and_reproducibility: Main body of the paper is clearly written - see comments above regarding the Appendix.
summary_of_the_review: I am inclined to recommend accepting this work conditional on the authors putting their results in better perspective as compared to prior work as well as improving proofs in the Appendix.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides a convergence analysis of Neural TD Learning with a projection onto a ball of fixed radius around the initial point. 
strength_and_weaknesses: The paper provides some new results on the convergence of TD learnign with neural network. 
The results seem interesting. 
Weaknesses of the paper are summarized as follows:
1) The definition of semi-norm in eq (5) is not defined. 
Moreover, the definition caligraphic N would not be a norm. It is a semi-norm.
Some discusssions would be needed. 
2) In the definition of fully connected neural network, is there a bias term? Usually, NN has bias parameter in each layer. 
It should be clarified.
3) It is not discussed why the final weight b is fixed. 
4) Assumption 2.4. requires that activation function is l-Lipschitz. However, to my knowledge, most popular activation functions are not globally Lipschitz. 
Some discusssions would be needed. 
5) In the result of Theorem 3.1, caligraphic N is not a norm. Therefore, we may not have any useful convergence result using the semi-norm because semi-norm may be zero for nonzero input. 
6) Moreover, in the left-hand side, the average cannot go inside the V since it is nonlinear. Then how can we derive a conclusion for theta_t?

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, and includes somewhat new results.
Some points need to be clarified, and they are given in the previous comments. 
summary_of_the_review: The paper seems to contain interesting results. 
However, some assumptions are strong to be practical, and some convergence results need to be clarified more as indicated in my previous comments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence of the temporal-difference (TD) algorithm with overparametrized neural networks. Compared with previous works, it weakens the projection step radius to a constant level by using a different analyzing techniques. The paper also provides simulation results to support the theories.
strength_and_weaknesses: Strength: the paper uses new techniques to analyze the convergence of neural TD. In particular, it utilize a combination of D-norm and Dirichlet norm to characterize the distance to the true value function. The reviewer believes that the analysis brings insight to the reinforcement learning community.

Weakness: The theoretical result seems a weak increment. It is not clear why changing the projection radius to constant can help the TD learning in practice. In fact, since the essential models considered are still linear models implied by the neural tangent kernel (NTK), the generalization error will be the same as the settings of previous neural TD works. From the computation cost perspective, it will be more interesting if the authors can show that the projection step can be totally discarded (just as most NTK works on supervised works do).
clarity,_quality,_novelty_and_reproducibility: The writing of the paper is clear and the techniques in the paper are novel.
summary_of_the_review: The paper uses novel techniques to modify the previous analysis of the global convergence of neural TD. The reviewer believes that the result, although not quite strong, is helpful to the understanding of such a problem.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Authors derived a new bound for Neural TD projecting for a fixed policy using arbitrary set of layers within the ball with radius \omega around a starting parameter \theta_0. They showed that the approximation error is bounded by O(\epsilon + 1 / \sqrt(m)) where m is the width of the neural network and \epsilon is the approximation quality of the best neural network within that ball. The main advantage of the new theorem is that it relaxed four conditions of the previous proofs: 1) small projection radius, 2) linearization around the initial condition, 3) restriction on policies, and 4) limited to a single layer network. Authors provided insight on the effect of m by running experiments for policy evaluation across three toy domains with both a random and well-trained policies.
strength_and_weaknesses: Strengths:
+ Given the wide usage of neural TD this paper provides a great contribution for the community
+ The paper is well-written overall while being a theoretical paper

Weaknesses
- More tips around the applicability of the theorems to practitioners would have been great. For example ReLU, a widely used function, does not satisfy the assumption of the theorem.
- I could not find the constant value of the omega for the results shown.


Minor errors:
Page 2: pi(s,a) -> \pi (s,a)
Page 4: \sigma is and activation -> \sigma is an activation
clarity,_quality,_novelty_and_reproducibility: Overall the paper reads very well. However, I did not check the proof of the theorem in detail.
summary_of_the_review: Overall a great and well-written paper with a major theoretical step.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper provides a convergence analysis of Neural TD Learning, an approximate temporal difference method for policy evaluation that uses a neural network for function approximation. The authors provide an approximation bound. The reviewers generally appreciated the work and found the proofs technically correct. TD learning is core to reinforcement learning, and its extension to neural networks enhances it to a more practical and powerful setting. Convergence analysis of this algorithm is an important contribution to the community; likewise, I recommend accepting this paper.

justification_for_why_not_higher_score: Reviewers felt that the work is somewhat incremental.

justification_for_why_not_lower_score: The work fills a gap in the literature.
Decision: Accept: poster