Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015)   from both algorithmic and statistical perspectives. In specific, we focus on the fitted Q iteration (FQI) algorithm with deep neural networks, which is a slight simplification of DQN that captures the tricks of experience replay and target network used in DQN. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by FQI. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players, which is deferred to the appendix due to space limitations.
This paper analyze the off-policy policy improvement algorithm with a very limited sparse ReLU function class. Although some of the results are interesting, I have lots of concern on the motivation of this work. I believe this paper is technically correct, but the authors focus on a very simplified case: they just use samples generated from a fixed sampling policy, which gets rid of the analysis of exploration and sample complexity that is a main focus of the reinforcement learning community. From my point of view, this may not be some analysis of reinforcement learning, at least not for Deep Q-learning, but more likely to be some learning theory of off-policy FQI. The main theorem investigates the statistical error and convergence rate of this problem, which can be of individual interest. But overall, I think the problem the authors want to solve is not a traditional reinforcement learning algorithm, and it is not appropriate to introduce the result as the theoretical analysis of Deep Q-Learning.
Detailed comments:
1. I think the assumption of Sparse ReLU network is too strong and generally not held in practice. Also, the optimization of such kind of network is painful, as the ell_0 constraint makes the optimization problem NP-hard. In other words, I think the authors only handle a very specific case under very ideal condition like assuming an oracles that can return the optimal network each turn.
2. The equivalence between FQI and target network is well-known and may not occupy so many places in Sec 3. Also, the results in Appendix B can be simply derived follows the recent development of neural network optimization. As this may be not the main contribution of this paper, I think it is better to omit these parts to make the paper more neat. 
3. Moreover, in appendix B, the authors assumed the function class as two-layer ReLU network, which is different from the assumption in the main text and cannot justify the global convergence of (3.4).
4. It is somewhat strange of assume a sampling distribution, as when we say Q-learning, we want to balance the exploration and exploitation given current estimation Q. Even in Deep Q-Learning, the data are sampled with \epsilon-greedy policy w.r.t the current Q network. This kinds of problems are more like off-policy policy improvement. I think call it the analysis of Deep Q-Learning is somehow not accurate and over-claimed. Maybe better called off-policy policy improvement with deep neural networks.
5. Theorem 4.4 is an interesting result as it shows that the error of the proposed algorithm can be decomposed into the a statistical error which depends on the smoothness of the operator Tf and an algorithm error that depend on the number of iterations. I am wondering what's the main technical differences between this work and [1], as I find the main difference is [1] don't give K-dependent algorithm error, instead assuming K have a order of log 1/epsilon to ensure algorithm error is smaller than \epsilon. I feel it's not so hard to derive a bound that combines statistical error and algorithm error for [1]. Also, FVI in [1] is not in spirit totally different from FQI in this paper given that [1] use the maximum operator over action when do FVI, not take expectation over the target policy. I hope the authors can clarify in their paper.
6. The authors don’t mention much of the target network in the main theorem. I know the generalization to the update with target network is not so hard, but as the authors mentioned so much time in the main text, shall it be better to include the result with target network?
Still, in my opinion, the main theorem has its own value. However, it is not proper to claim as a theoretical analysis of Deep Q-Learning. Also, I feel the function class is too restricted and the optimization issue in the proposed algorithms cannot be simply solved, and the main analysis is similar to [1] with little generalization to Holder smoothness. Thus, I tend to reject this paper.
[1] Munos, Rémi, and Csaba Szepesvári. "Finite-time bounds for fitted value iteration." Journal of Machine Learning Research 9.May (2008): 815-857.