Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Vanilla Q learning often suffers from the over estimation problem i.e, it might choose bad actions initially which gets reinforced later on. Double Q learning maintains two Q functions $Q^A$ and $Q^B$ which are used to update each other. This helps in the case of random rewards. However, the complicated coupled dynamics of $Q^A$ and $Q^B$ makes the analysis much harder. Even though there are many satisfactory analyses for vanilla Q learning, double Q learning is lacking in this front.  This paper attempts to fill in this gap by giving a non-asymptotic convergence analysis of DQL, which is much better than the previous analyses in terms of every parameter. 

In both the synchronous and asynchronous case (i.e all cases updated at once or updated from a stream of off-policy data respectively) they obtain a time complexity of $O(1/\epsilon^2(1-\gamma)^7)$ where $\epsilon$ is the target error and $\gamma$ is the discount factor. The proof technique mentioned in Section 3.3 considers the error propagation dynamics and analyzes the iterations using standard concentration inequalities.
main_review: I think this is an important problem with lots of recent interest. The paper is fairly well written and makes a good attempt at obtaining a finite time analysis of DQL. As mentioned in the paper, the results are worse than the guarantees obtained for the vanilla Q learning in terms of the discount factor $\gamma$ which is the major drawback of the work.

All in all, I expect that the techniques established here would be useful in further investigation of DQL and eventually show that it outperforms vanilla Q learning.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studied double Q-learning in RL and established finite time convergence analysis for both synchronous/asynchronous version of the algorithm. The complexity result improves the existing result in terms of the dependency on parameters such as $\epsilon, 1-\gamma, \cdots$.
main_review: This papers studied Double Q-learning, which is one of the most widely used technique in RL. The authors established the non-asymptotic convergence result of both synchronous/asynchronous Double Q-learning for tabular discounted MDP. In particular, the paper proved $O(\frac{1}{(1-\gamma)^7\epsilon^2})$ time complexity for both methods (ignoring other constants), improving upon the existing result that adopts a decaying step size. This is achieved by using more aggressive constants step size and a more refined analysis. It still remains unknown if Double Q-learning is provably faster than Q-learning, and this paper serves as an important step towards understanding Double Q-learning.

With the prevalence of Double Q-learning methods in various applications, it is of great importance to understand its theoretical guarantee. Overall this paper is solid and very well written. 
limitations_and_societal_impact: See full review.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Thanks to the practical applicability of double Q-learning, this paper denoted to analyzing the finite-time convergence of double Q-learning algorithms with constant stepsizes. Building on existing analysis in Xiong etal'2020, the paper brings in some new analysis tools for nested stochastic approximation schemes and achieves faster non-asymptotic error bounds for double Q-learning. Some interesting observations are made on the practical usefulness of constant step in Q-learning. 

main_review: Originality.
The paper builds heavily upon and compares against the work by Xiong etal'2020, but provides a faster finite-time convergence of nested SA schemes for which double Q-learning can be taken as an interesting example; and the topic is interesting, yet most of the algorithm and analysis follows from existing ones with several new techniques. However, the work Xiong etal'2020 establishes high-probability bound (1-\delta) on the finite-time convergence error, while this paper focuses on the 

Quality.
The quality of this paper looks reasonabe and the bounds appear tighter than existing ones. 

Clarity.
The paper is mostly clear, well-written, and easy to follow.

Significance.
The authors' effort in mproving finite-time error bounds of double Q-learning is appreciated. However, the paper is very similar to the work by Xiong et al'2020 in terms of both the content, algorithm, analysis, and results. The practical implication of the improved results is not fully demonstrated. Whether the results shed light on designing new Q-learning algorithms, or helps advise the efficient use of Q-learning algorithms? How general are the results?  Numerical simulations are also encouraged to validate the theoretical claims. 

-----------
I have seen the rebuttal and read the other reviews, and updated the score. But I am still not convinced by the explanation of the "typo" and the merits of the paper relative to existing works. 
limitations_and_societal_impact: Strengths.

Improved high probability error bounds are derived. 
Interesting analysis involving some new tools. 

Major comments/limitations.

1. In general, function approximation is used, in particular nonlinear approximation? 
2. The paper missed comparison against a number of closely related works on two-timescale SA algorithms, Q-learning, and coupled Q-learning algorithms, especially the coupled Q-learning in [D. S. Carvalho, F. S. Melo, P. A. Santos'2020: A new convergent variant of Q-learning with linear function approximation].
3. It is not clear why in (5) (same for the asychronous setting), the noise term {εt}t is a sequence of i.i.d. random variables satisfying Eεt = E[TbtQ∗] − Q∗ = T Q∗ − Q∗ =0 ∈ RD. Then how the Markovian correlation between s and s' is handled? 
4. When and why the SA in (9) has only one unique fixed point? Under what conditions? Do the considered two double Q-learning algorithms obey these conditions?
5. What assumptions shall be made on the error \epsilon_t and bias term v_t for the general SA scheme to cover the two types of double Q-learning? These are important to be claimed as a general result.
6. No numerical simulations validate the claimed theoretical improvement vs the bound provided by Xiong etal'2020.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work studies the Double Q Learning algorithm for reinforcement learning under tabular settings. The main technical contribution is a refined convergence to the optimal Q function with high probability under a specification of constant step-size. This improves upon previous results which use a polynomial learning rates. No experiments are given to contrast whether the performance gap translates to substantial gains in practice.
main_review: 
The technical contribution of a novel convergence result for double Q learning is interesting, and clearly refines existing results on the performance of Double Q learning that require attenuating step-sizes. I agree that the results hinge upon some technical innovations illuminated on page 3, lines 68-75. However, I am not sure this alone is sufficient to warrant acceptance. That is because:

1) what algorithmic ideas are fundamentally new here? It is well-known in stochastic approximation that constant step-sizes can result in faster improvement but to looser limiting neighborhoods of convergence. In that sense, none of the results here are particularly surprising or innovative here.

2) The results here are restricted to tabular settings only, which limits their applicability/usefulness to preclude large-scale MDPs common in practice in technology today.

3) There seem to be no experiments contrasting whether the improved learning rates are actually borne  out in practice. 

Therefore, this work should really be evaluated on the technical novelty of the proofs alone. While the characterization of the error dynamics in 3.1 which gives rise to the main results is well-executed, I feel the lack of actual algorithmic innovation or experimental validation is difficult to overlook.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper received borderline reviews.  Some main issues were about lack of clarity, and of a lack of empirical validation of the theoretical benefits of the proposed constant step sizes.

I felt the rebuttal did help clarify some of the raised issues.  I would also encourage the authors to include the numerical experiments that they mentioned they ran in a future version of this paper.  Even if the authors are of the opinion that these do not strictly add new information and only validate the theory, it is important to consider a publication as primarily a means to communicate our findings to the larger research community, and such numerical experiments can help illustrate the main points, as well as augment the theory, if and when there are discrepancies.

For instance, I'd personally love to understand better whether the practical convergence rates match the current theory.  Is there an important 'gap' still between practical and theoretical convergence rates?  Would it be possible to do an even tighter analysis and find even-better bounds?  These are examples of questions that could help the reader better understand the significance of this work (not necessarily in terms of "does it work with neural nets?", but rather in terms of "what kind of further theoretical study does this enable?" or "what kind of research questions does this raise or answer?").

I think the paper has promise, but could benefit from another round of reviews, using the reviewers' comments to improve the work.  I therefore would like to strongly encourage the authors to consider how the paper could be made even better, and then resubmit (e.g., to a related venue).
Decision: Accept (Poster)