Double Q-learning: New Analysis and Sharper Finite-time Bound
Authors: Lin Zhao
Huaqing Xiong
Yingbin Liang
Wei Zhang
Venue:  (2021)
Keywords: Double Q-learning
Finite-time analysis
Convergence rate
Stochastic approximation

Abstract: Double Q-learning \citep{hasselt2010double} has gained significant success in practice due to its effectiveness in overcoming the overestimation issue of Q-learning. However, theoretical understanding of double Q-learning is rather limited and the only existing finite-time analysis was recently established in \citet{xiong2020double} under a polynomial learning rate. This paper analyzes the more challenging case with a rescaled linear/constant learning rate for which the previous method does not appear to be applicable. We develop new analytical tools that achieve an order-level better finite-time convergence rate than the previously established result. Specifically, we show that synchronous double Q-learning attains an $\epsilon$-accurate global optimum with a time complexity of $\Omega\left(\frac{\ln D}{(1-\gamma)^7\epsilon^2}  \right)$, and the asynchronous algorithm attains a time complexity of $\tilde{\Omega}\left(\frac{L}{(1-\gamma)^7\epsilon^2} \right)$, where $D$ is the cardinality of the state-action space, $\gamma$ is the discount factor, and $L$ is a parameter related to the sampling strategy for asynchronous double Q-learning. These results improve the order-level dependence of the convergence rate on all major parameters $(\epsilon,1-\gamma, D, L)$ provided in \citet{xiong2020double}. The new analysis in this paper presents a more direct and succinct approach for characterizing the finite-time convergence rate of double Q-learning.

Under review as a conference paper at ICLR 2021
DOUBLE Q-LEARNING: NEW ANALYSIS AND SHARPER FINITE-TIME BOUND
Anonymous authors Paper under double-blind review
ABSTRACT
Double Q-learning (Hasselt, 2010) has gained significant success in practice due its effectiveness in overcoming the overestimation issue of Q-learning. How- ever, theoretical understanding of double Q-learning is rather limited and the only existing finite-time analysis was recently established in Xiong et al. (2020) under a polynomial learning rate. This paper analyzes the more challenging case with a rescaled linear/constant learning rate for which the previous method does not appear to be applicable. We develop new analytical tools that achieve an order- level better finite-time convergence rate than the previously established result. Specifically, we show that synchronous double Q-learning attains an 6-accurate global optimum with a time complexity of Q
D and the asynchronous [1-1)²e
algorithm attains time complexity of á (1-1) where D is the cardinality of the state-action space, y is the discount factor, and L is a parameter related to the sampling strategy for asynchronous double Q-learning. These results im- prove the order-level dependence of the convergence rate on all major parameters (e, 1 7, D, L) provided in Xiong et al. (2020). The new analysis in this pa- per presents a more direct and succinct approach for characterizing the finite-time convergence rate of double Q-learning.
INTRODUCTION
Double Q-learning proposed Hasselt (2010) a widely used model-free reinforcement learn- ing (RL) algorithm in practice for searching for an optimal policy (Zhang et al., 201 8a;b; Hessel et al., 2018). Compared to the vanilla Q-learning proposed in Watkins & Dayan (1992). double Q-learning uses two Q-estimators with their roles randomly selected at each iteration, respectively for estimating the maximum Q-function value and updating the Q-function. In this way, the over- estimation of the vation-vvlle function in vanilla Q-learning can be effectively mitigated, especially when the reward is random or prone to errors (Hasselt, 2010; Hasselt et al., 2016; Xiong et al., 2020). Moreover, double Q-learning has been shown to have the desired performance in both finite state-action setting (Hasselt, 2010) and infinite setting (Hasselt et al., 2016) where it successfully improved the performance of deep Q-network (DQN), and thus inspired many variants (Zhang al., 2017: Abed-alguni & Ottom, 2018) subsequently.
In parallel to its empirical success in practice, the theoretical convergence properties of double Q- learning has also been explored. Its asymptotic convergence was first established in Hasselt (2010). The asymptotic mean- eeaa-s error for double Q-learning was studied Weng et al. (2020c) under the assumption that the algorithm converges to unique optimal policy. Furthermore, in Xiong et al. (2020), the finite-time convergence rate has been established for double Q-learning with a polyno- mial learning rate that double Q-lcarning attains an e-accurate optimal Q-function at a time complexity approaching to but never reaching Q { the cost of asymptotically large exponent on - However, polynomial learning rate typically does not offer the best possible convergence rate, having been shown for RL algorithms that so-called rescaled linear learning rate (with a form of a, = ) and a constant learning rate achieve a better convergence rate (Bhandari et al., 2018; Wainwright, 201 9a;b; Chen al., 2020; Qu & Wierman, 2020). Therefore, a natural question arises follows:
1/t" , E (0, 1). Under such choice for the learning rate, they showed

---

Under review as a conference paper at ICLR 2021
Can a rescaled linear learning rate or a constant learning rate improve the convergence rate of double Q- Q-learming order-wisely? If yes, does it also improve the dependence of the convergence rate other important parameters of the Markov decision process (MDP) such the discount factor and the cardinality of the state and action spaces?
The answer to the above question does not follow immediately from Xiong al. (2020), because the finite-time analysis framework in Xiong et al. (2020) does not handle such learning rates to yield desirable result. This paper develops a novel analysis approach and provides affirmative answers to the above question.
1.1 OUR CONTRIBUTIONS
This paper establishes sharper finite-time bounds for double Q-learning with a rescaled lin- ear/constant learning rate, which are orderwisely better than the existing bounds in Xiong et al. (2020). We devise a different analysis approach from that in Xiong et al. (2020), which is more capable of handling variants of double Q-learning.
For synchronous double Q-learning, where all state-action pairs are visited at each iteration, we apply a rescaled linear learning rate a; 3+(1-7)+ and show that the algorithm can attain
an e-accurate global optimum with time complexity of (n=)fz) where y is the discount factor and D = |S||A|| is the cardinality of the finite state-action space. As comparison, for the e dominated regime (with relatively small 7), our result attains an e-accurate optimal Q- function with a time complexity 22 ( whereas the result in Xiong et al. (2020) (see Table 1) 1 w - 0) is an
does not exactly reach 2 ((22) and its approaching such an order additional cost of an asymptotically large exponent on r For - y dominated regime, our result improves on that in Xiong et al. (2020) (which has been optimized in the dependence on
1 - y in Table 1) by O (1n==))
For asynchronous double Q-learning, where only one state-action pair is visited at each iter- ation, we obtain a time complexity of 5 ((-))r=) where L is a parameter related to the sampling strategy in Assumption 1. As illustrated in Table I, our result improves upon that in Xiong et al. (2020) order-wisely in terms of its dependence on e and - y as well as on L by at least O (I.').
Our analysis takes a different approach from that in Xiong et al. (2020) in order to handle the rescaled linear/constant learning rate. More specifically, to deal with a pair of nested stochastic approximation (SA) recursions, we directly establish the dependence bound of the error dynamics (of the outer SA) between the Q-estimator and the global optimum on the error propagation (of the inner SA) between the two Q-estimators. Then we develop bound on the inner SA, integrate it into that on the outer SA as a noise term, and establish the final convergence bound. This a very different yet more direct approach than that in Xiong al. (2020), the latter of which captures the blockwise convergence by constructing two complicated block -hielyy decreasing bounds for the two SAs. The sharpness of the bound also requires careful selection of the rescaled learning rates and proper usage of their properties.
1.2 RELATED WORK
Double Q-learning was proposed and proved to converge asymptot- ically in Hasselt (2010). In Weng et al. (2020c), the authors explored the properties of mean-square errors for double Q-learning both in the tabular case and with linear function approximation, under the assumption that unique optimal policy exists and the algorithm evant work to this paper is Xiong et al. (2020), which established the first finite-time convergence rate for tabular double Q-learning with polynomial learning rate. This paper provides sharper finite-time convergence bounds for double Q-learning, which requires different analysis approach.
Theory on double Q-learning:
converge. The most rel-
Tabular Q-learning and convergence under various learning rates: Proposed in Watkins & Dayan (1992) under finite state-action space, Q-learning has aroused great interest in its theoretical study. Its asymptotic convergence has been established in Tsitsiklis (1994); Jaakkola et al. (1994);
2

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison of time complexity for (a)synchronous double Q-learning. The choices w - 1, 7: and w respectively optimize the dependence of time complexity on c, 1 9, and L in Xiong et (2020). We denote V max(a, b), min (a.bb b).
SyneDQ Xiong et al. (2020)
Stepsize F.WE E 1)
Time complexity
W
w 6/7
Ω
V
In 1 1-7
(1-7)²
2.5
This work
3
(#))
3+11->1
(1-7)
AsyneDQ Xiong al. (2020)
Stepsize www E 1)
Time complexity
W =
W
6/7
w 2/3
Ω
(
Ω
V
[n 1-m
L 1)
(1-))²
(1-7)883
This work
(11)))
(+))
(1-78²e
1
Borkar & Meyn (2000); Melo (2001); Lee & He (2019) by requiring the learning rates to satisfy Li=0 0; = 0o and Er of < oc. Another line of research focuses on the finite-time analysis of Q-learning under different choices of the learning rates. Szepesvári (1998) captured the first con- vergence rate of Q-learning using a linear learning rate (i.c., a = }. Under similar learning rates, Even-Dar & Mansour (2003) provided finite-time results for both synchronous and asynchronous Q-learning with a convergence rate being exponentially slow as a function of - Another pop- ular choice is the polynomial learning rate which has been studied for synchronous Q-learning in Wainwright (2019b) and for both synchronoussasynchrooouu Q-learning in Even-Dar & Mansour (2003). With this learning rate, however, the convergence rate still has gap with the lower bound of O (Azar et al., 2013). To handle this, more sophisticated rescaled linear learning rate was introduced for synchronous Q-learning (Wainwright, 2019b; Chen et al., 2020) and asynchronous Q-learning (Qu & Wierman, 2020), and thus yields better convergence rate. The finite-time bounds for Q-learning were also given with constant stepsizes (Beck & Srikant, 2012: Chen et al., 2020; Li al., 2020). In this paper, we focus on the rescaled linear/constant learning rate and obtain sharper finite-time bounds for double Q-learning.
Q-learning with function approximation: When the state-action space considerably large or even infinite, the Q-function is usually approximated by a class of parameterized functions. In such case, Q-learning has been shown are typically needed to establish the convergence of Q-learning with linear function approxima- tion (Bertsekas & Tsitsiklis, 1996; Melo et al., 2008; Zou al., 2019; Chen al., 2019; Du al., 2019; Yang & Wang, 2019; Jia et al., 2019; Weng et al., 2020a;b) neural network approxima- tion (Cai al., 2019; Xu & Gu, 2019). The convergence analysis of double Q-learning with function approximation raises new technical challenges and can be an interesting topic for future study.
converge in general (Baird, 1995). Strong assumptions
PRELIMINARIES ON DOUBLE Q-LEARNING
We consider a Markov decision process (MDP) over a finite state space S and finite action space A with the total cardinality given by D == [|) The transition kernel of the MDP is given by P. S:SSA x A
+ [0, 1] denoted as PP a). We denote the random reward function at time t
<(-ss) captures the conditional probability distribution over the action space given state s E S. For policy m, we define Q-function Q" E || as
as R. S x A S + [0, Rmaz], with [ (s, a, s')] = Re' A policy
Q=(ssa):=B ==
Σ
r Ra(s,, az s1) st) =8
(1)
where 7 E (0, 1) is the discount factor, at (-108)), and 5/ P(()se.
3

---

Under review as a conference paper at ICLR 2021
Both vanilla Q-learning (Watkins & Dayan, 1992) and double Q-learning (Hasselt, 2010) aim find the optimal Q-function Q" which the unique fixed point of the Bellman operator T (Bertsekas & Tsitsiklis, 1996) given by
m at)
TQ(s, 0) (P-laa))))
(2)
d'EA
Note that the Bellman operator T is 7-contractive which satisfies - TQ'I S 5 1 Q'Il under the supremum norm || max,,a (Q(ssa)),
The idea of double Q-learning is to keep two Q-tables (i.e., Q-function estimators) Q and Q", and randomly choose one Q-table to update at each iteration based on the Bellman operator com- puted from the other Q-table. We next describe synchronous and asynchronous double Q-learning algorithms in more detail.
Synchronous double Q-learning: Let (3th21 be sequence of ii.d. Bernoulli random variables satisfying P(3: 0) P(3, = 1) 0.5. At each time 6, 3, = O indicates that Q" is updated, and otherwise Qa is updated. The update at time 2 can be written in a compact form as,
(Q -1-- ax,3) (s, + 3, (Ra 6') + +
(3)
( = (1- (3)) Q (s,a) + az(1 B.) (Ri(s, a, +
for all (s,a) E S A, where s' is sampled independently for each (s, a) by 8' ~ P(-|s, a). a" arg max (s',, a), b' arg max and o is the learning rate. Note that the rewards for both updates of Q and Q are the same copy of R,,
Asynchronous double Q-learning: Different from synchronous double Q-learning, at each itera- tion the asynchronous version samples only one state-action pair update the chosen Q-estimator. That is, at time i, only the chosen Q-estimator and its value at the sampled state-action pair (8t, Qx) will be updated. We model this by introducing an indicator function (r a) 1 ((s).a))((s.a) Then the update at time t 2 1 of asynchronous double Q-learning can be written compactly as
( -1- (s) oo ( = -1- (1- ar) (1)))1))(()))))))))))))))) (f)))(((()))) (s, as,(s a) B:) (Ie + 2f
ar) (Re Q0
for all (s, E x A, where Re is evaluated as a,)s.
In the above update rules (3) and (4), each iteration only one of the two Q-tables is randomly chosen to be updated. This chosen Q-table generates greedy optimal action, and the other Q- table is used for estimating the corresponding Bellman operator (or evaluating the greedy action) for updating the chosen table. Specifically, if QA is chosen to be updated, we use Q4 to obtain the optimal action a" and then estimate the corresponding Bellman operator using QB to update Q4. As shown in Hasselt (2010), B[Q"(s' a²"] }}] is likely smaller than E max. (Q (s',)),, where the expectation taken over the randomness of the reward for the same (s, a, s') tuple. Such a effectively reduce the overestimation.
two-estimator framework adopted by double Q-learning
Without loss of generality, we assume that QAA and QB are initialized with the same value (usually both all-zero tables in practice). For both synchronous and asynchronous double Q-learning, it has been shown in Xiong al. (2020) that either Q-estimator is uniformly bounded by 'I-y the learning process. Specifically, for either i E {A, B), we have |[Q]] < Rmax and ||Q: Q' s 2Bmax 1-7
Rimax throughout
1-7
Vmax for all 2 This boundedness property will be useful in our finite-time analysis.
3 FINITE-TIME CONVERGENCE ANALYSIS
In this section, we start with modeling the error dynamics to be nested SAs, following by a conver- gence result for general SA that will be applicable for both SAs. Then provide the finite-time results for both synchronous and asynchronous double Q-learning. Finally, we sketch the proof of the main theorem for the synchronous algorithm to help understand the technical proofs.
4

---

Under review as a conference paper at ICLR 2021
3.1 CHARACTERIZATION OF THE ERROR DYNAMICS
In this subsection, we characterize the (a)synchronous double Q-learning algorithms pair of nested SA recursions, where the outer SA recursion captures the error dynamics between the Q- estimator and the global optimum Q* and the inner SA captures the error propagation between the two Q-estimators which enters into the outer SA as a noise term, Such characterization enjoys useful properties that will facilitate the finite-time analysis.
Outer SA: Denote the iteration error by Fr = Q - Q* and define the empirical Bellman operator (,Q(s, a) = R,(8, aa) + 7max a'). Then we can have for all 2 1 (see Appendix C),
Tr+1 (s, a) = (1
+ ā, (s. (G, (s, a) ",)(s'a")), (5)
where 5 == F:Q' - = Q . Ge(re) = F, - = f. (rr - and the equivalent learning rate (, a)
for synchronous version
(,,33eT(s, for asynchronous version Note that it is by
design that we use the same sampled reward R2 in both T,Q" and T.Q, in the definition of Gr(r).
These newly introduced variables have several important properties. First of all. the noise term (erJe sequence i.i.d. random variables satisfying Es, BTT - Q- = TQ Q' =
0 E R. Furthermore, define the span seminorm of Q* as ||Q Il span (aa (s,
min (xa))SXA (s.a). Then it can be shown that (see Appendix C)
|e&ll S 2maax + 7 11 Ilspan == K.
(6)
Moreover, it is easy to show that (rx) S 7 ||reell. which follows from the contractive property of the empirical Bellman operator given the same state. We shall say that G. is quasi-contractive in the sense that the 7-contraction inequality only holds with respect to the origin 0.
Inner SA: We further characterize the dynamics of v =2 Q SA recursion (see Ap- pendix C);
V4+1(s, = (s, a))u ( + ár(s, a) (Hi a) + m)(s,))),
for synchronous version for all 2 where ār(s, a) = as) for asynchronous version
at.
has been shown in
1+7 ||v]]] and {pehe1 is Xiong al. (2020) that Hr is quasi-contractive satisfying I1H, < 2 martingale difference sequence with respect to the filtration F, defined by Fi = {0, Ω} where Ω denotes the underlying probability space and for t 2 2,
a (18k), (Ra-1), Bk k S (),
for synchronous version,
F
l (sk: ak, R4-1, 14
t), for asynchronous version,
where we note that for synchronous sampling {sk} and [Rs-1} are the collections of sampled next states and the sampled rewards for each (s, aa-rrir, respectively; while for asynchronous sampling, the pairs {Sk, 0k, 8k+ h222 are consecutive sample transitions from one observed trajectory.
In the sequel, we will provide the finite-time convergence guarantee for (a)synchronous double Q- learning using the SA recursions described by (5) and (7).
3.2 FINITE- TIME BOUND FOR A GENERAL SA
In this subsection, we develop a convergence result for a general SA that will be applicable for both inner and outer SAs described in Section 3.1.
Consider the following general SA algorithm with the unique fixed point 0 O:
0 = - 0, + o (9,( + E + 774)
for all 2 1, where 0, E R" and we abuse the notation of a general learning rate a, E [0, 1). Then bound 0g in the following proposition, the proof of which is provided in Appendix D.
5

---

Under review as a conference paper at ICLR 2021
Proposition 1. Consider an SA given in (9). Suppose G. is guasi-contractio with constant pa- rameter " that is, [[ $ y |00a] where y E (0,1). Then for any learning rate ar E [0, 1). the iterates { satisfy
||0,1| - (1---00 ())))))))))))))))))))))))))))) ||6111 704-1 (1]l (12-11l))
Σ
(1 (- f (1IWWl) + (|-illl + [Will,
(10)
1=k+1
where the sequence {We} is given by W (1-a=) a, + a with W = 0.
We note that an SA with similar form to that in (9) has been analyzed in Wainwright (2019h), which additionally requires a monotonicity assumption. In contrast, our analysis does not require this assumption. Moreover, distinct from Wainwright (2019b), we treat the noise terms and Vt separately rather than bounding them together. This is because for double Q-learning, the noise term it has its dynamics which is significantly more complex than the i.i.d. noise Es. Bounding them as one noise term will yield more conservative results.
Note that the SA recursion (7) is special case of (9) by setting 44 0. Therefore, Proposition is readily applicable to both (5) and (7).
3.3 FINITE- TIME ANALYSIS OF SYNCHRONOUS DOUBLE Q-LEARNING
We apply the above bound for SA synchronous double Q-learnngg and bound the error ||r]]| |0 1- The first result is stated in the following theorem.
Theorem 1. Fix E (0. 1). Consider synchronous double Q-learning in (3) with a rescaled linear
learning rate a; 3+(1- Vt 2 0. Then the learning error Tt Q² Q" satisfies
3 3|1r
3/3KŌ 1 36 max D +
B B|/r+ S
Vt +
(11)
(1 7)t
(1-7)3/2
(1 (1-2) Vt
where : = 6vIn2D + +3/ D 2v + Vn. and is defined in (6) which is the uniform bound of [xcl
Theorem provides the finite-time error bound for synchronous double Q-learning. To understand Theorem the first term on the RHS (right hand side) of (11) shows that the initial error decays sub- sub-linearly with respect to the number of iterations. The second term arises due to the fluctuation of the noise term E,, which involves the problem specific quantity K. The last item arises due the fluctuation of the noise term μr in the u,-recursion (7), i.e. the difference between two Q-estimators.
Corollary 1. The time complexity (i.e., the total number of iterations) to achieve an e-accurate optimal Q-function (i.e., E |rrl| S e) is given by T(e, D) Ω
D
(1-7)(=3
Proof. The proof follows directly from Theorem by noting that the middle term on the RHS of (11) scales as
since k. 22max + ||Q" span
2R
V Vuax-
spaan
We next compare Corollary with the time complexity of synchronous double Q-learning provided in Xiong et al. (2020), which given by
1 +
D
T= St
(12)
(1-7)TE2
1-7
(1 - 7)
For the e dominated regime (with relatively small 7), the result in (12) clearly cannot achieve the order of 1 and In D as our result does. Further, its approaching to such an order (1) + 0 in Table 1) is also an additional cost of asymptotically large exponent -ー For 1 1- dominated regime, the dependence on 7 can be optimized by taking w = in (12), compared to which our result achieves an improvement by a factor of O ((n (m==)²) (see Table 1).
where w E 1). 1).

---

Under review as a conference paper at ICLR 2021
3.4 FINITE-TIME ANALYSIS OF ASYNCHRONOUS DOUBLE Q-LEARNING
In this subsection, we provide the finite-time result for asynchronous double Q-learning- Differently from the synchronous version, each iteration asynchronous double Q-learning only update one state-action pair of a randomly chosen Q-estimator. Thus the sampling strategy is important for the convergence analysis, for which we first make the following assumption.
Assumption 1. The Markov chain induced by the stationary behavior policy n is uniformly ergodic.
This is standard assumption under which Markov chain is most widely studied (Paulin et al., 2015). It was also assumed in (Qu & Wierman, 2020; Li et al., 2020) for the asynchronous samples in Q- learning. We further introduce the following standard notations (see for example Qu & Wierman (2020); Li al. (2020)) that will be useful in the analysis.
First, we denote jx as the stationary distribution of the behavior policy over the state-action space S and denote Mmin == ma) Mr (s, a). is easy that the smaller M'in is, the more iterations we need to visit all state-action pairs. Formally, we capture this probabilistic coverage by defining the following covering number:
L = min {t min (sL.0))ESAA
(13)
2
where B, denotes the event that all state-action pairs have been visited at least once f iterations.
In addition, the ergodicity assumption indicates that the distribution of samples will approach to the stationary distribution μ4 in a so-called mixing rate. We define the corresponding mixing time as
mix
min tt
max div (P' S 4 (x1.0))ESxA
(14)
where pt (-1(8,, a1)) is the distribution of (st, ar) given the initial pair (s1, and drv(p, v) the variation distance between two distributions
Next, we provide the first result for asynchronous double Q-learning in the following theorem whose proof is seen in Appendix H.
10,1),8 E (0, E (0, + and suppose that Assumption holds. Consider asynchronous double Q-learning with a constant learning rate aç = a = In Dr min { (1--)) e with some constant ej. Then asynchronous double Q-learning learns an e-accurate optimum, i.e., 1| Q-11 S e, with probability at least 1 6 given the time com- plexity of
Theorem 2. Fix E
T T
( Mumin
bmix
In
7)
Pmin (1
7)
c(1
7)2
where tmms defined in (14).
The complexity in Theorem 2 is given in terms of the mixing time. To facilitate comparisons, provide the following result in terms the covering number.
Theorem 3. Under the same conditions of Theorem 2, consider constant learning rate os
fr min {(1 72, with some constant c2. Then asynchronous double Q-learning can
learn an e-accurate optimum, i.e., 110 - 1111 < with probability at least 5 given the time complexity of
L
1
T = Ω
In
2 (111-) 7)
c(1 71-
where L is defined in (13).
We next compare Theorem 3 with the result obtained in Xiong et al. (2020). In Xiong et al. (2020), the authors provided the time complexity for asynchronous double Q-learning
(=
((
77
DL
$ +
La
1
T T= Ω
In
In (1
(15)
(1
Te
2
7

---

Under review as a conference paper at ICLR 2021
where (2.1). 1). It can be observed that result improves that in (15) with respect to the order of all key parameters e, D, 1 - y, L (see Table 1). Specifically, the dependence on in (15) can be optimized by choosing
I. upon which Theorem 3 improves by factor of at least L
3.5 PROOF SKETCH OF THEOREM
In order to provide the convergence bound for double Q-learning under the rescaled linear learning rate, we develop different analysis approach from that in Xiong et al. (2020), the latter of which does not handle the rescaled linear learning rate. More specifically, in order to analyze a pair of nested SA recursions, we directly bound both the error dynamics of the outer SA between the Q- estimator and the global optimum and the error propagation between the two Q-estimators captured by the inner SA. Then we integrate the bound on the inner SA into that on the outer SA as a noise term, and establish the final convergence bound. This is very different yet more direct approach than the techniques in Xiong al. (2020) which constructs two complicated block boic-l decreasing bounds for the two SAs to characterize a block-wiss convergence.
Our finite-time analysis for synchronous double Q-learning (i.e., Theorem 1) includes four steps.
Step I: Bounding outer SA dynamics E ||r]] by inner SA dynamics E || Here, r; == Q2 Q* captures the error dynamics between the Q-estimator and the global optimum, and 1/4 := Q of captures the error propagation between the two Q-estimators. We apply Proposition I to the error dynamics (5) rt. take the expectation, and apply the learning rate inequality (24) to obtain
E |rall S a4-1 ||rll + 04-1
EE [ + E ||xl]) E ||Wlll
(16)
k=1
where W2+1 = - a.) + ã,,τ, with initialization W = 0.
Step II: Bounding E [|eel- We first construct a F--martingale sequence (Winsiseer with W4+1 Wt+1 and Wi 0. Next, we bound the squared difference sequence (W..1 w2) by 4V2 max a// /a;" N-2 for 1 < i < t, where N is defined in (26). Then apply the Azuma-Hoeffding inequality (see Lemma 5) [W.) Wisss1 and further use Lemma 6 to obtain the bound on EE [WWill in Proposition 2 which is given by
E || S nāvan.
(17)
where Ö = 6v/n 2D + 3/7 and & is defined (6).
Step III: Bounding inner SA dynamics E ||a]|- Similarly to Step we apply Proposition to the ue-recursion (7), take the expectation, and apply the learning rate inequality (24) to obtain
E |ell S 1 |p]
+
Σ
E || + E Mell,
(18)
2
2==2
where M,+1 (1 o;) Me + 0g444, with initialization M1 = O. Using a similar idea to Step II, we
obtain the bound on || MM in Proposition 3. Finally, we substitute the bound of E [|M& || back in
(18) and use the fact || || = 0 to obtain
6Vmax
E ||p
S 1 1-7 Var-i. with D - 22 + VT.
(19)
Step IV: Deriving finite-time bound. Substituting (17) and (19) into (16) yields (11).
4 CONCLUSION
In this paper, we derived sharper finite-time bounds for double Q-learning with both synchronous sampling and Makovian asynchronous sampling. To achieve this, we developed different approach to bound two nested stochastic approximation recursions. An important yet challenging future topic is the convergence guarantee for double Q-learning with function approximation. In addition to the lack of the contraction property the Bellman operator in the function approximation setting, is likely that neither of the two Q-estimators converges, they do not converge to the same point even they both converge. Characterizing the conditions under which double Q-learning with function approximation converges is still open problem.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Bilal H Abed-alguni and Mohammad Ashraf Ottom. Double delayed Q-learning. International Journal of Artificial Intelligence, 16(2):11-59 2018.
Alckh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a gener- ative model is minimax optimal. In Conference on Learning Theory(COLT), pp. 67-83, 2020.
Mohammad Gheshlaghi Azar. Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3): 325-349, 2013.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Carolyn L Beck and Srikant. Error bounds for constant step-size Q-learning. Systems Control Letters, 61(12):1203-122 1208, 2012.
Dimitri P. Bertsekas and John N Tsitsiklis. Neuro-Dynamic Programming, volume 5. Athena Sci- entific, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory (COLT), 2018.
Vivek S Borkar and Sean P Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-differenc learning con- verges to global optima. In Advances in Neural Information Processing Systems (NeurIPS), pp- 11312-11322, 2019.
Zaiwei Chen, Sheng Zhang, Thinh T. Doan, Siva Theja Maguluri, and John-Paul Clarke. Finite- time analysis of Q-learning with linear function approximation. arXiv preprint arXiv: (rxXiv::955.11 14455, 2019.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint 2wXiv:2002.00874. 2020.
Gal Dalal, Balazs Szorenyi, and Gugan Thoppe. tale of two-timescale reinforcement learning with the tightest finite-time bound. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3701-3708, 2020.
Thinh T Doan. Finite-time analysis and restarting scheme for linear two-time-scale stochastic ap- proximation. arXiv preprint 11X.v:1912.10588 2019.
Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with UCB exploration is 2019..
sample efficient for mafiite-horiiznn MDP. arXiv preprint
Simon S Du, Yuping Luo, Ruosong Wang, and Hanrui Zhang. Provably efficient Q-learning with function approximation via distribution shift error checking oracle. In Advances in Neural Infor- mation Processing Systems (NeurIPS), pp. 8058 8068,, 2019.
Eyal Even-Dar and Yishay Mansour. Learning rates for Q-learning. Journal of Machine Learning Research, 5(Dec):1-22 2003.
Jianqing Fan, Zhaoran Wang. Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep Q- learning. arXiv preprint 1901.0010 2019.
Hado V Hasselt. Double Q-learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2613-2621, 2010.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proc. AAAI Conference Artificial Intelligence (AAAI), 2016.

---

Under review as a conference paper at ICLR 2021
Jiafan He, Dongruo Zhou, and Quanquan Gu. Minimax optimal reinforcement learning for dis- counted MDPs. arXiv preprint arXiv:2010.00587, 2020.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proc. AAAI Conference on Artificial Intelligence (AAAI), 2018.
Tommi Jaakkola, Michael I Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic programming algorithms. In Advances Neural Information Processing Systems (NeurIPS), pp. 703-710, 1994.
Zeyu Jia, Lin F. Yang, and Mengdi Wang. Feature-bass based q-learning for two-player stochastic games.
arXiv preprint arXiv: 00400000043 2019.
Chi Jin, Zeyuan Allen Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably effi- cient? In Advances in Neural Information Processing Systems (NeurIPS), pp. 4863-4873, 2018.
Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. arXiv preprint arXiv:2008. 12776, 2020.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timesse too-timescale stochastic approximation with markovian noise. arXiv preprint arXiv:2002.01268, 2020.
Donghwan Lee and Niao He. unified switching system perspective and ODE analysis of Q- learning algorithms. arXiv preprint arXiv:1912.022770 2019.
Donghwan Lee and Niao He. Periodic Q-learning, arXiv preprini arXiv:2002.09795, 2020.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous Q-laariin: Sharper analysis and variance reduction. arXiv preprint arXiv:2006.00 0004,,,06.03041,, 2020.
Francisco S Melo. Convergence of Q-learning A simple proof. Institute of Systems and Robotics, Tech. Rep, pp. 1-4, 2001.
Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning, pp. 664-671, 2008
Daniel Paulin et al. Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20, 2015.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learning. arXiv preprint arXiv:2002.00260, 2020.
Devavrat Shah and Qiaomin Xie. Q-learning with nearest neighbors. In Advances in Neural Infor- mation Processing Systems (NeurIPS), pp. 0.P31111-1211 2018.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with generative model. arXiv preprint arXiv: 4122, 2018a.
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 770-787. SIAM, 2018b.
Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization for episodic reinforcement learning in metric spaces. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1-44, 2019.
Csaba Szepesvári. The asymptotic convergence-rate of Q-learnin. Advances in Neural Informa- tion Processing Systems (NeurIPS), pp. 1064-1070, 1998.
John N Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16 13):155-202. 1994.
10

---

Under review as a conference paper at ICLR 2021
Martin J. Wainwright. High-Dimensional Statisties: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019a. doi: 10.1017/
Martin Wainwright. Stochastic approximation with cone-contractive operators: Sharp too bounds for Q-learning. arXiv preprini arXiv: (.xxvv:905.002000 2019b.
Mengdi Wang. Primal-dual æ learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint 17Xiv:1710.06100, 2017.
Christopher J.C.H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):279-292 1992.
Bowen Weng, Huaqing Xiong, Yingbin Liang, and Wei Zhang. Analysis of Q-learning with adapta- tion and momentum restart for gradient descent. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (LJCAI-20), pp. 3051-3057, 2020a.
Bowen Weng, Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang. Momentum Q-learning with sanite-sample convergence guarantee. arXiv preprint arXiv:2007.15418, 2020b.
Wentao Weng, Harsh Gupta, Niao He, Lei Ying, and Srikant R. Provably-efficient double Q- learning. arXiv preprint arXiv:arX1::207.5550: 2020c.
Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang. Finite-time analysis for double Q- learning. arXiv preprint UrXiv:2009.142577 2020.
Pan Xu and Quanquan Gu. A finite-time analysis of Q-learming with neural network function ap- proximation. arXiv preprint arXiv: 19/2.0451, 2019.
Tengyu Xu, Shaofeng Zou, and Yingbin Liang. Two time-scale off-policy learning: Non-
asymptotic analysis over markovian samples. arXiv preprint arXiv:1909.11007, 2019.
Kunhe Yang, Lin F. Yang. and Simon S. Du. Q-learning with logarithmic regret. arXiv preprint arXiv:arXiv:2006.098 09118, 2020.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features.
In International Conference on Machine Learning (ICML). pp. 6995-7004, 2019.
Qingchen Zhang, Man Lin, Laurence T Yang, Zhikui Chen, Samee U Khan, and Peng Li. dou- ble deep Q-learning model for energy-efficient edge scheduling, IEEE Transactions on Services Computing, 12(5):739-749, 2018a.
Yi Zhang, Ping Sun, Yuhan Yin, Lin Lin, and Xuesong Wang. Human-like autonomous vehicle speed control by deep reinforcement learning with double Q-learning. In Proc. IEEE Intelligent Vehicles Symposium (IV), pp. 1251-1256, 2018b.
Zongzhang Zhang, Zhiyuan Pan, and Mykel J Kochenderfer. Weighted double Q-learning, In International Joint Conferences on Artificial Intelligence (ICAI-177, pp- 3455-3461, 2017.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems (NeurIPS), pp- 8665-8675, 2019.


Reviews:
[{"review_id": "uRxp05p8fmx", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the convergence rate of double Q learning under the tabular setting. Both the synchronous and asynchronous double Q learning algorithms are studied and analyzed. The technical novelty of this paper seems limited -- possibly a direct combination of [Wainwright 2019a] and [Xiong et al 2020]. Moreover, the scope of this work seems also limited -- it only consider the tabular version of double Q-learning, with either a generative model (synchronous) or i.i.d. sampling (asynchronous) sampling models, which is never used in practice. This seems to makes this work only appealing to theorists. However, in terms of the theory, the results for double Q learning is pessimist -- the rate is much worse than standard Q learning. However, practical implementations of double Q learning has demonstrated its advantage in terms of correcting the over-estimation bias. Without numerical results or additional theory, such a gap makes one ponder whether the rates in this paper are tight. \n\n\nDetailed comments: \n\n1. This paper seems a theory paper, with the focus on understanding the convergence rate of double Q learning under the tabular case. This paper provides a unified analysis for both the synchronous and asynchronous settings using stochastic approximation (Proposition 1). However, seen from the proof, this proposition is a modification of Theorem 1 in [Wainwright 2019a]. Based on this stochastic approximation result, showing the convergence rate for double Q learning by analyzing the evolution of outer and inner stochastic approximations follows from [Xiong et al 2020]. Thus, the technical novelty of this paper is limited.\n\n2. The synchronous setting seems too restrictive because one needs to update the Q value of every state and action at each iteration. In other words, this setting essentially assumes a version of the generative model. \nA more interesting setting is the asynchronous setting, where one updates each state-action at each iteration. However, this paper makes the assumption that the samples are i.i.d. and each state-action appears with probability at least 1/L. This is very restrictive and essentially reduces the sampling model to the generative model, as one can first estimate the model and solve a planning problem. This approach is also known as minimax optimal. A more practical assumption is to sample a trajectory according to a behavioural policy, as is done in [Li et al. 2020] (Sample Complexity of Asynchronous Q-Learning:\nSharper Analysis and Variance Reduction) for asynchronous Q Learning. \n\n3. Compared with the results for standard Q Learning, e.g., [Li et al. 2020], the rates obtained here are inferior. This seems somewhat disappointing because there seems no advantage of using double Q Learning -- the algorithm is more complicated and the rate is worse. \n\n4. It would be interesting to see whether (1) variance reduction and (2) constant stepsize can be used to sharpen the rates.  \n\n5. I appreciate the efforts of the authors in comparing with the related work details. It would be nice to also compare with papers on standard Q-learning and other methods in the tabular settings.\n\n6. In the abstract, why is the run-time complexity given by the \"big Omega\" notation, which means that the time-complexity is larger than the quantity provided in terms of the order. It seems that the complexity should be given in \"big O\" notation. \n\n\n\n\nMissing references:\n\n**Tabular Q-learning**:\n\nIs Q-Learning Provably Efficient?\n\nQ-learning with Logarithmic Regret\n\nQ-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP\n\nPeriodic Q-Learning\n\n**Q-Learning with function approximation**: \n\nSample-Optimal Parametric Q-Learning Using Linearly Additive Features\n\nFeature-based q-learning for two-player stochastic games\n\nAdaptive Discretization for Episodic Reinforcement Learning in Metric Spaces\n\nQ-learning with Nearest Neighbors\n\nAn Analysis of Reinforcement Learning with Function Approximation\n\nA Theoretical Analysis of Deep Q-Learning\n\nFinite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning\n\n\n**Tabular RL**:\n\nVariance reduced value iteration and faster\nalgorithms for solving Markov decision processes \n\nPrimal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems\n\nModel-Based Reinforcement Learning with a Generative Model is Minimax Optimal\n\nEfficiently Solving MDPs with Stochastic Mirror Descent\n\nNear-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model\n\nVariance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes\n\nMinimax Optimal Reinforcement Learning for Discounted MDPs", "extra_scores": {}, "extra_text": {}}, {"review_id": "klltXDz10r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper refines the existing finite-sample bound of double Q-learning. This paper considers the rescaled linear schedule of the learning rate and claims that the sample complexity bounds are improved in the sense the dependence on all main parameters (epsilon, 1-gamma, L, D) have been improved.\n\n\nOriginality: The paper follows the work in Xiong et.al 2020, but has made some non-trivial improvements. The nested SA representation of double Q-learning is interesting and the proving techniques seem new. \n\nQuality: The technical quality of this paper looks reasonably good to me although I have only roughly checked the proofs. The high level idea of the proof makes sense to me. I haven't found any flaws in the proof sketches.\n\nClarity: Overall the paper is well written. \n\nSignificance: I am not sure whether the significance level of this submission meets the standard of ICLR or not. The main reason is that the bounds in this paper are on the expectation of L1 norm of the iteration error. The bounds in the Xiong et.a. (2020) are high probability bounds. Is it fair to make comparisons between these two? The L1 bound is  weaker than the mean square bounds and I am not fully convinced how meaningful such results are. In addition, the implications of the proposed theory on algorithm design have not been fully verified on numerical examples.\n\nPros:\n1. The linear learning rate schedule is considered.\n2. The nested SA representation is interesting and the proof technique looks new.\n\n\nCons:\n1. The bounds on the iteration errors are in the L1 sense and it is unclear how meaningful these bounds are. Is the comparison with Xiong et.al (2020) really fair? \n2. Does the theory in this paper lead to any new insight for design and tuning of double Q-learning? Any numerical justifications for these new insights?\n \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WXSn9CNt85t", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a new theoretical analysis of double Q-learning in the tabular case. The analysis improves over previous result of Xiong et al. which assumes polynomial learning rate. This paper considers rescaled linear learning rate and the sample complexity has better dependency on 1/eps. The improvement comes from a better characterization of the error dynamics. \n\nOverall, this paper is well-written. The authors provide a careful comparison with previous results, and also provide a technical overview to highlight the new ideas in the analysis. The authors also provide a proof sketch in Section 3.5. \n\nMy main concern is whether the results are interesting enough to the ICLR community. Certainly, understanding the theoretical guarantee double Q-learning is an important topic, and this paper provides a nice improvement over the previous analysis. However, I am not sure if the improvement is significant enough compared to the previous result. Moreover, the bounds provided in this paper is still far from being practical (in the synchronous setting, all state-action pairs are visited in each iteration, and in the asynchronous setting the sample complexity is at least (|S||A|)^6. Given this, my commendation would merely be a weak acceptance. \n\n***Post Rebuttal***\nI appreciate the authors's improved analysis. After reading the new version it is unclear to me whether the results are interesting enough to the ICLR community, and thus I would like to keep my original score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "6qsuNXl48P2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a sharper analysis for the finite time convergence rate of the double Q learning algorithm. The authors provides bounds for the synchronous and asynchronous settings and uses a more refined learning rate of $a/(b+t)$. It is shown that with such step size rule, a sharper convergence rate than (Xiong et al., 2020) can be obtained.\n\nThe advantages of this paper are that (i) the authors analyzed a popular algorithm with reasonable assumptions; (ii) particularly, the analysis which is achieved by studying a nested stochastic approximation scheme with the Azuma-Hoeffding inequality is quite easy to follow. The reviewer believes that the analysis may generate new insights for the future work in related domains. \n\nThere are some outstanding concerns/comments as follows:\n\n- Significance of contribution\n\nAs the authors mentioned, the double Q learning algorithm has been analyzed in the prior works such as (Xiong et al., 2020). While the obtained rates by the authors are sharper, in the current presentation, the reviewer finds the result relatively incremental. It may be useful to better highlight the difference between the analysis approach in this paper and (Xiong et al., 2020). \n\nMoreover, though the double Q learning algorithm is different from the standard Q learning, it also seems that the sharper analysis done in this paper has a worse dependence on $1-\\gamma$ compared to (Qu & Wierman, 2020). \n\n- Relation to Prior Works\n\nAs claimed by the authors, one of the major innovations in this work is to deploy a rescaled step size of the form $a/(b+ct)$. However, it should be noted using such rescaled step size is also common in the stochastic approximation analysis, e.g., \n\nBhandari et al., A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation, COLT, 2018.\n\nAlso, the idea of analyzing nested stochastic approximation can be found in a few recent works on analyzing 2 timescale stochastic approximation, e.g., \n\nT. Doan, Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation, arXiv/1912.10583.\n\nDalal et al., A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound, AAAI 2020.\n\nKaledin et al., Finite time analysis of linear two-timescale stochastic approximation with Markovian noise, COLT 2020.\n\nIt would put the paper in a better position if the authors could emphasize on how the analysis is related to the above mentioned works.\n\n- Async. Q learning\n\nIn (4), the authors mentioned that the state-action pair change over $t$ without a further discussion on how $a_t,s_t$ are generated. From the analysis in Section 3, it seems that the analysis can tackle the general cases satisfying assumption 1 (including the ergodicity assumption ones). It maybe beneficial to supplement the discussions in Section 2 with a few concrete examples.\n\nLastly, the current bound developed by the paper has a dependence of $L^3$ (cf. Assumption 1), where $L \\geq D$, which seems to be quite high when the state/action space is large. Particularly, it is also worse than the $L^2$ bound analyzed in (Qu and Wierman, 2020) - of course, the latter paper analyzed a different algorithm, but it would again put the paper in a better position if the authors could discuss the differences in these convergence rates. \n\n* Minor point: the reviewer wonders that in Table 1, the convergence bound for \"This Work\" is shown for both $\\omega = 1-\\eta \\rightarrow 1$ and $\\omega = 6/7$. From my understanding, the $\\omega$ exponent is always $1$ for this work. \n\nPost-rebuttal: I am satisfied with the authors' response and decided to keep my score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides an improved analysis of the finite time convergence rate of double Q-learning under more reasonable step size rules, comparing to previous work by Xiong et al., 2020.  Understanding the convergence behavior of double Q-learning is an obviously interesting theoretical topic and all reviewers appreciate the authors’ improved analysis. 

 Several reviewers questioned the sample complexity in terms of the dependence on L (thus |S||A|); In the latest revision, the authors claimed they now refined the dependence from O(L^6) to O(L). This major change is yet to be further reviewed since the authors did not leave any clue on why/how such an improvement was attained. 
Another outstanding concern relates to the theoretical comparison of the rates between double Q-learning and Q-learning, which remains clueless. It’s unclear whether the bound in this paper is sharp enough and whether/when double Q-learning is provably inferior than Q-learning. 

Therefore, I am not recommending acceptance at this time, though I encourage the authors to resubmit with a more conclusive theoretical analysis. 

Decision: Reject