ABSTRACT Q-learning with neural network function approximation (neural Q-learning for short) is among the most prevalent deep reinforcement learning algorithms. Despite its empirical success, the non-asymptotic convergence rate of neural Qlearning remains virtually unknown. In this paper, we present 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. We prove that neural Q-learning finds the optimal policy with O(1/ √ T ) convergence rate if the neural function approximator is sufficiently overparameterized, where T is the number of iterations. To our best knowledge, our result is the first finite-time analysis of neural Q-learning under non-i.i.d. data assumption.
[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.