Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Overview:

This paper provides an analysis of fitted Q-iteration in the off-policy reinforcement learning setting, for the setup where the value function class of interest is a class of neural networks. The provide bounds on the rate at which fitted Q iteration converges to a near-optimal policy under the assumption that the transition dynamics satisfy a certain notion of Holder smoothness. This result is motivated by the problem of understanding why deep Q-learning works, which the authors relate to the problem above via certain simplifying assumptions. The authors also extend this result to give similar guarantees for two-player zero-sum stochastic games.

Review:

This paper addresses an important and challenging problem, and the results appear technical sound. It is also fairly thorough and well-written. However, my overall feelings toward the result are mixed, because I believe the assumptions the authors make are so strong that they essentially remove most of the interesting problem structure, and consequently the results follow by straightforward application of known techniques. 

Two major challenges in understanding DQN are as follows:
1) Exploration: Why does the algorithm successfully explore and solve MDPs with large state spaces?
2) Generalization: How do the overparameterized neural networks used for value function approximation help with generalization (or exploration)?

The issue of exploration is assumed away by the authors, as they work in the batch/offline RL setting where examples (s,a,r,s') are i.i.d., and the assume that the so-called "concentrability coefficient", which measures mismatch between the data distribution and the data induced by the optimal policy, is bounded. This assumption is standard in the analysis of fitted Q-iteration for off-policy RL (eg, Munos and Szepesvari '08), but it implies that the algorithm does not need to solve a challenging exploration problem, since the data-gathering policy has good coverage. Unfortunately, the authors do not justify why this assumption should hold for DQN.

The standard analysis for off-policy fitted Q-iteration does not simply require that the concentratability coefficient is bounded, but also requires another strong assumption, which is that the function class is closed/complete under bellman updates. In general, this is a difficult property to verify, and it is well-known that fitted Q-iteration can cycle and fail to converge when it does not hold. This leads to the issue of generalization: The way the authors get around the issue of closedness/completeness is to work in the fully nonparametric regime: They take the class of neural nets under consideration to be large enough to approximate any Holder smooth function, then show that under mild assumptions on the dynamics this class of Holder smooth functions is closed under bellman updates. This is a good trick, but it has an unfortunate consequence, which is that by blowing up the class of neural networks, the generalization bound one can prove is quite weak. Ultimately, the generalization bound the authors give follows the standard rate for Holder-smooth functions in nonparametric statistics, which is exponential in dimension whenever the function class is $p$th order smooth for constant $p$. For example, when the class of functions is lipschitz the rate is $n^{-1/(2+d)}$, where $n$ is the number of examples. Since we are paying the fully nonparametric rate for generalization here, this begs the question of why neural nets were even used to begin with, which is not addressed.

To conclude, this is a certainly a challenging problem, but I don't think the paper is transparent about the limitations of the techniques (as described above) and I believe the title of the paper, "A theoretical analysis of deep Q-learning", is too strong given the shortcomings of the results.
review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: The authors provide a theoretical analysis of deep Q-learning based on the neural fitted Q-iteration (FQI) algorithm [1]. Their analysis justifies the techniques of experience replay and target network, both of which are critical to the empirical success of DQN. Moreover, the authors establish the algorithmic and statistical errors of the neural FQI algorithm.
Then, the authors propose the Minimax-DQN algorithm for the zero-sum Markov game with two players. They further establish the algorithmic and statistical convergence rates of the sequence of action-value functions obtained by the Minimax-DQN algorithm.

[1] Martin Riedmiller. Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method. In European Conference on Machine Learning, pp. 317–328. Springer, 2005.

The strengths of this paper are as follows.
1. This paper is theoretically sound. The authors establish the convergence rates with detailed proofs step by step. 
2. It is the first theoretical analysis that provides the errors of the neural FQI algorithm with a ReLU network. This analysis provides a rigorous approach to understand deep q-learning algorithms.
3. The authors propose an extension of DQN for the zero-sum Markov game with two players. They further analyze the convergence rates of the sequence of action-value functions obtained by the proposed algorithm.

Minor comments:
1. Page 2: In Notation, "$\|f\|_{2,v}$" may be "$\|f\|_{v,2}$"。
2. Page 3: In the 2th line of Section 2.2, "$\{d_j\}_{i=0}^{L+1}$" may be "$\{d_i\}_{i=0}^{L+1}$".


review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #2

Meta-review: The authors offer theoretical guarantees for a simplified version of the deep Q-learning algorithm. However, the majority of the reviewers agree that the simplifying assumptions are so many that the results do not capture major important aspects of deep Q-Learning (e.g. understanding good exploration strategies, understanding why deep nets are better approximators and not using neural net classes that are so large that can capture all non-parametric functions). For justifying the paper to be called a theoretical analysis of deep Q-Learning some of these aspects need to be addressed, or the motivation/title of the paper needs to be re-defined. 
Decision: Reject