Zap Q-Learning
The Zap Q-learning algorithm introduced in this paper is an improvement of Watkins' original algorithm and recent competitors in several respects. It is a matrix-gain algorithm designed so that its asymptotic variance is optimal. Moreover, an ODE analysis suggests that the transient behavior is a close match to a deterministic Newton-Raphson implementation. This is made possible by a two time-scale update equation for the matrix gain sequence. The analysis suggests that the approach will lead to stable and efficient computation even for non-ideal parameterized settings. Numerical experiments confirm the quick convergence, even in such non-ideal cases.
The paper makes the following contributions:
1) It shows that the asymptotic variance of tabular Q-learning decreases slower than the typical 1/n rate even when an exploring policy is used.
2) It suggests a new algorithm, Zap Q(lambda) learning to fix this problem.
3) It shows that in the tabular case the new algorithm can deliver optimal asymptotic rate and even optimal asymptotic variance (i.e., optimal constants).
4) The algorithm is empirically evaluated on both a simple problem and on a finance problem that was used in previous research.
Significance, novelty
---------------------
Q-learning is a popular algorithm, at least in the textbooks. It is an instance of the family of stochastic approximation algorithms which are (re)gaining popularity due to their lightweight per-update computational requirements.
While (1) was in a way known (see the reference in the paper), the present paper complements and strengthens the previous work. The slow asymptotic convergence at minimum must be taken as a warning sign. The experiments show that the asymptotics in a way correctly predicts what happens in finite time, too. Fixing the slow convergence of Q-learning is an important problem. The fix, while relatively straightforward (but not entirely trivial), is important. My only worry is about the computational cost associated with matrix inversions. Even with incremental updates (Sherman-Morrison), the per-update cost is O(d^2) when we have d features. This may be OK in some applications, but it is a limitation (not a show-stopper by any means). The empirical evaluations are of sufficient depth and breadth for a conference publication proposing a new method (I actually like the way that they are conducted). The condition A3 seems strong (as noted by the authors themselves).
I don't have high hopes for the generalization to the full linear feature-based case as in this Q-learning, as many of its relatives, tend not to have any strong guarantees (i.e., performance can be quite bad). However, this is not the problem of *this* paper. 
Soundness
---------
I believe that the results are sound. I could not check the long version (yet) as I was asked to write a review just two days ago (as an extra review) and I did not have the time to check the proofs. From what I understand about these type of proofs, I believe that the proof can go through but there are some delicate steps (e.g., nonsmooth right-hand side of the ODE). That the authors discovered that A3 is necessary for their proof to go through at least shows that they are quite careful and attentive to details. (I am siding with them in that I believe it may be possible to remove A3, but this won't be trivial).
The experiments are done with care; demonstrating nicely the effect of learning. Perhaps a sensitivity study could complement the experiments presented, but this is not critical in my opinion for a conference publication.
Quality of writing
------------------
Very well written pose. Some may say that perhaps fewer symbols could be used, but at the end the notation was consistent and systematic and I did not find the paper too hard to read.
Related work
------------
There is some similarity to [1-5], which would be good to cite. While these papers are definitely relevant (they seem to employ the same two-time scale logic in similar, TD/LMS context), the present paper is sufficiently different so that besides citing these as implementing the same idea in a different setting, no other modification is necessary to the paper.
Minor comments
--------------
* Perhaps Theorem 2.1 does not need Q2? 
* Line 120: "the gain sequence gamma" should be "the gain sequences gamma and alpha"
* Line 124: The uninitiated reader may find it hard to interpret the phrase "An ODE approximation holds".
* Numerical results: I expect the authors to share their code (github is excellent for this) or otherwise make it clear what parameter settings are used. A few details seem to be missing to replicate the experiments (e.g., what stepsize was used with RPJ?)
* Line 151: "the Watkins'": remove "the"
* Line 152: Which analysis does "this" refer to? (Middle of the page.)
* Figure 3: I am guessing W_n is the error. I am not sure whether this was introduced beforehand. Maybe just remind the reader if it was.
* Fig 4: Why is Speedy-Q not converging? Will it?? Overall vanilla Q-learning is not even that bad here..
* Line 174: "trails" should be "trials"?
* Line 202: How is the condition number defined given that A is not even symmetric, so it may have complex eigenvalues? Magnitudes I assume?
* Line 209: Hmm, I see W_n is defined here.. Move this up?
References
[1] H. Yao and Z-Q. Lie. Preconditioned temporal difference learning. In Proceedings of the
25th International Conference on Machine learning, 2008.
[2] H. Yao, S. Bhatnagar, and Cs. Szepesvari.  Temporal difference learning by direct preconditioning.  In
Multidisciplinary Symposium on Reinforcement Learning (MSRL), 2009.
[3]  Yao, H., Bhatnagar, S., and Szepesvári, Cs., LMS-2: Towards an Algorithm that is as Cheap as LMS and Almost as Efficient as RLS, CDC, pp. 1181--1188, 2009
[4] Pan, Yangchen, Adam M. White, and Martha White. "Accelerated Gradient Temporal Difference Learning." AAAI. 2017. 
[5] Givchi, A., & Palhang, M. (2014). Quasi Newton Temporal Difference Learning. ACML.