Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper introduces a finite time analysis of Q-learning with neural network function approximators across multiple layers and no iid assumption. 

[Pros]
+ Provides a novel way to analyze Q learning with nn function approximators that can be applied to other algorithms (notably in my mind, TD in actor critic where iid assumptions are often violated). 

[Cons]
+ The novelty is a bit unclear other than the non-iid assumption. We note that modern Q-learning tends to use batching so doesn't require much of an iid assumption anyways, but this allows for more robust proofs in TD settings with non-iid training.
+ The paper was a bit dense and hard to follow, we suggest reducing p.8 to have more discussion with references to proofs in the Appendix as in Chen2019. 
+ As the authors admit in open commentary, there is a mistake to be fixed which needs to be reviewed before acceptance. I think there is value to this work, however, would require seeing the change to assess a revision.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper provides a finite-time analysis of a neural Q-learning algorithm, where the data are generated from a Markov decision process and the action-value function is approximated by a deep ReLU neural network. When the neural function is sufficiently over-parameterized, the O(1/T) convergence rate is attained. 

Pros: This paper makes theoretical contribution to the understanding of neural Q-learning. This is an important but difficult task. The recent finite-time analysis on Q-learning either assumes a linear function approximation or an i.i.d. setting in the neural Q-learning. This paper makes a first attempt to study the neural Q-learning with Markovian noise. Overall, this paper is very easy to follow.  

Cons: In spite of its theoretical contributions, this paper has a few major issues.

1. The projection step relies on a parameter $\omega$ which is unknown in practice. In theorem, $\omega = C m^{-1/2}$ for some unknown constant $C$. It would be of practical interests to seek other proof techniques to avoid such projection step. For instance, Srikant and Yang (2019) and Chen et al. (2019) removed this projection step in the finite-time analysis of Q-learning with a linear function approximation. 

2. Assumption 5.3 is problematic for the considered neural Q-learning setting. The matrix $\hat{\Sigma}_{\pi}$ is of a very large dimension in the order of $O(m^2) * O(m^2)$ where the width of the neural network $m$ is assumed to diverge in the Theorem 5.4 for the over-parameterization purpose. Given the diverging dimension scenario, it is problematic to ensure Assumption 5.3. Moreover, it is unclear how to verify this condition in practice. In the literature, Melo et al. (2008) and Zou et al. (2019b) assumed a similar condition, which is OK because in the Q-learning with linear function approximation, this matrix reduces to the covariance matrix of the feature vector. 

3. The error rate in Theorem 5.4 is an increasing function of the layer $L$ in DNN, which is counterintuitive. A typically practical observation is that a larger $L$ is better. 



review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: [Summary]
This paper studies the convergence of Q-Learning when a wide multi-layer network in the Neural Tangent Kernel (NTK) regime is used as the function approximator. Concretely, it shows that Q-learning converges with rate O(1/T) with data sampled from a single trajectory (non-i.i.d.) of an infinite-horizon MDP + a certain (stationary) exploration policy. 

[Pros]
The results in this paper improve upon recent work on the same topic. It is able to handle multi-layer neural nets as opposed to two-layer, prove a faster rate O(1/T), and handle non-iid data (as opposed to iid data where (s,a,r,s’) are sampled freshly from the beginning at each step.)

The paper is generally well-written. The results and proof sketches are well presented and easy to follow. The proof seems correct to me from my check, including the indicator issue pointed out in the comments which I think can be easily fixed (by explicitly writing out the indicator and thus the Cauchy-Schwarz will still apply.)

[Cons]
The result in this paper seems more or less like a direct combination of existing techniques, and thus may be limited in bringing in new techniques / messages. Key technical bottlenecks that are assumed out in prior work are still assumed out in this paper with potentially different forms but essentially the same thing.

More concretely, the proof of the main theorem (Thm 5.4) seems to rely critically on Lemmas 6.2 and 6.3, both of which are rather straightforward adaptations of prior work:

Lemma 6.2 (concentration of stochastic gradients on linearized problem): Seems to me like almost the same as [Bhandari et al. 2018], expect that now the network is an affine function---rather than a linear function---of \theta, where the additional constant term f(\theta_0; s, a) depends on (s, a). 

Lemma 6.3 (good landscape of linearized problem): Comparing with prior work (Theorem 6.3, Cai et al. 2019), this Lemma works by directly assuming out the property of the arg-max operator in Assumption 5.3, which has a slightly different form from, but is essentially the same thing as (Assumption 6.1, Cai et al. 2019). 

To be fair, the paper has to deal with the linearization error of a multi-layer net, which is dealt with in Lemma 6.1 and should be valued. But still I tend to think the above adaptations are rather straightforward and technically not quite novel.

[Potential improvements]
I would like to hear more from the authors about the technical novelty in this paper, specifically how Lemma 6.1 - 6.3 compare with prior work. I would be willing to improve my evaluation if this can be addressed.

review_title: Official Blind Review #2

Meta-review: This was an extremely difficult paper to decide, as it attracted significant commentary (and controversy) that led to non-trivial corrections in the results.  One of the main criticisms is that the work is an incremental combination of existing results.  A potentially bigger concern is that of correctness: the main convergence rate was changed from 1/T to 1/sqrt{T} during the rebuttal and revision process.  Such a change is not trivial and essentially proves the initial submission was incorrect.  In general, it is not prudent to accept a hastily revised theory paper without a proper assessment of correctness in its modified form.  Therefore, I think it would be premature to accept this paper without a full review cycle that assessed the revised form.  There also appear to be technical challenges from the discussion that remain unaddressed.  Any resubmission will also have to highlight significance and make a stronger case for the novelty of the results.
Decision: Reject