Faster Non-asymptotic Convergence for Double Q-learning
Authors: Lin Zhao
Huaqing Xiong
Yingbin Liang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement learning theory
Markov decision process
stochastic approximation

Abstract: Double Q-learning (Hasselt, 2010) has gained significant success in practice due to its effectiveness in overcoming the overestimation issue of Q-learning. However, the theoretical understanding of double Q-learning is rather limited. The only existing finite-time analysis was recently established in (Xiong et al. 2020), where the polynomial learning rate adopted in the analysis typically yields a slower convergence rate. This paper tackles the more challenging case of a constant learning rate, and develops new analytical tools that improve the existing convergence rate by orders of magnitude. Specifically, we show that synchronous double Q-learning attains an $\epsilon$-accurate global optimum with a time complexity of $\tilde{\Omega}\left(\frac{\ln D}{(1-\gamma)^7\epsilon^2} \right)$, and the asynchronous algorithm achieves 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 existing convergence rate by the order of magnitude in terms of its dependence on all major parameters $(\epsilon,1-\gamma, D, L)$.  This paper presents a substantial step toward the full understanding of the fast convergence of double-Q learning.

Faster Non-asymptotic Convergence for Double Q-learning
Lin Zhao
Huaqing Xiong The Ohio State University xiong. 3098osu. edu
Yingbin Liang The Ohio State University liang. 8890osu. edu
National University of Singapore elezhl 1unui.iuuu... edu.sg
Abstract
Double Q-learning (Hasselt 2010) has gained significant success in practice due its effectiveness in overcoming the overestimation issue of Q-learning. However, the theoretical understanding of double Q-learning is rather limited. The only existing finite-time analysis was recently established (Xiong et al.] 2020), where the polynomial learning rate adopted in the analysis typically yields slower vergence rate. This paper tackles the more challenging case of a constant learning rate, and develops new analytical tools that improve the existing convergence rate by orders of magnitude. Specifically, we show that synchronous double Q-learning
attains an e-accurate global optimum with time complexity of ÿ
(1-7)' and
the asynchronous algorithm achieves a time complexity of 3 (1-)) where D is the cardinality of the state-action space, 7 is the discount factor, and is parameter related to the sampling strategy for asynchronous double Q-learning. These results improve the existing convergence rate by the order of magnitude in terms of its dependence on all major parameters (c, - Y, D, L). This paper presents a substantial step toward the full understanding of the fast convergence of double-Q Q learning.
Introduction
Double Q-learning, proposed in Hasselt (010), is a widely used model-free freee reinforcement learning (RL) algorithm in practice for learning optimal policy (Zhang et al.) 2018a b Hessel et al. 2018). Compared to the vanilla Q-learning proposed in Watkins and Dayan (1992). double Q-learning uses two Q-estimators with their roles randomly selected each iteration, respectively for estimating the maximal Q-function value and updating the Q-function. In this way, the overestimation of the Q-function in the vanilla Q-learning can be effectively mitigated, especially when the reward is random or prone to errors (Hasselt) 20100] Hasselt et al., 2016 Xiong et al.] 2020). Moreover, double Q-lcarning has been shown have the desired performance both finite state-action space setting (Hasselt, 2010) and infinite setting (Hasselt et al.) 2016) where it successfully improved the performance of deep Q-network (DQN), and thus inspired more variants (Zhang et 2017 Abed-alguni and Ottom 2018) subsequently.
In parallel 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-square error for double Q-learning was studied in Weng et al. (2020b) under the assumption that the algorithm converges to a unique optimal policy. More recently, in Xiong al.) (2020), the finite-time convergence rate has been established for double Q-learning with polynomial learning rate = 1/t", w E (0, 1). Under such choice of the learning rate, Xiong et al. (2020) showed that double Q-learning attains an e-accurate optimal Q-function time complexity approaching to but never reaching Q (222) at the cost of asymptotically large exponent of 1-7.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Comparison of time complexity for synchronous and asynchronous double Q-learning.
SyneDQ
Stepsize 1 (w E
Time complexity
Xiong et al. 2020
W
6/7
(3.
244
(1-7))
2 V
In
This work
<(1->)
Q (1
(1-7)
AsyncDQ
Stepsize
Time complexity
W. E (3.1)
6/7
W 2/3
Xiong al. (2020)
Ω
Ω
In 1
á
(n 13 1.
(1-)
2.5
(1- (1-7)-0
This work
(
Ω
L
(1-7)
(1 (1-2)
The choices + 1. 7, and w optimize the dependence of time complexity on e, 1 7 and Xiong al. (2020). respectively. In addition, we denote a V max
6
However, polynomial learning rate typically does not offer the best possible convergence rate, as having been shown for RL algorithms that a constant learning rale achieves better convergence bounds (Beck and Srikant 2012 Bhandari al. 2018 et 2020 Therefore, natural question arises as follows:
Can a constant learning rate improve the convergence rate of double Q-learning by orders of magnitude? ? If yes, does it also improve the dependence of the convergence rate on other important parameters of the Markov decision process (MDP) such as the discount factor and the cardinality of the state-action space?
In this paper, develop novel analysis techniques and provide affirmative answers the above questions.
1.1 Our contributions
This paper establishes sharper finite-time bounds for double Q-learning with constant learning rates, which improve the existing bounds by orders of magnitude. Our result hence encourages to apply the constant stepsize in practice to attain better convergence performance.
For synchronous double Q-learning, where all state-action pairs are visited at each iteration, we show that with constant learning rates a, = a E (0, 1), the algorithm converges to an e-accurate global
D optimum with a time complexity of Ω (1-7)²<> ). where is the discount factor and D |S||AA] is
the cardinality of the finite state-action space. As comparison, for the e-dominated regime (with relatively small 7), we show that double Q-learning attains an c-accurate optimal Q-function with time complexity of S2( (( whereas the result in Xiong et al. (020) (see Table 1 does not exactly reach 2( ( and its approaching to such an order (1 ;= - 0) is at an additional cost of an asymptotically large exponent on r- For the (1 d)-miiinte regime, our result improves on that in Xiong et al. (2020) (which has been optimized in the dependence 1 1-7 in Table by (m==)²)
For asynchronous double Q-learning, where only one state-action pair is visited each iteration via a single sample trajectory, we show that the algorithm attains an e-accurate global optimum with
a time complexity of (m~)ra>) where L denotes the covering time (see 15)). and depends on
the sampling strategy. As illustrated in Table 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 (L*).
Technically, our finite-time analysis approach here is very different yet more direct than the techniques in Xiong et al. (2020). Our goal is still bound the convergence error via a pair of nested stochastic approximation (SA) recursions, where the outer SA captures the learning error dynamics between

---

one Qeestimator and the global optimum and the inner SA captures the error propagation between the two Qeestimators, Rather than constructing two block-wisely decreasing bounds for the nested SAs as in Xiong et al. (2020), which appears challenging if not infeasible under the constant learning rate, we devise new analysis techniques to directly bound both the inner and outer error dynamics either per iteration (for synchronous sampling) or per frame of constant iterations (for asynchronous sampling), We then treat the output of the inner SA as an noise term in the outer SA, and combine the two bounds to establish the finite-time error bound of the learning error.
1.2 Related work
Due to large number of studies in Q-learning, we only review the most relevant ones on the double Q-learning and the vanilla Q-learning under tabular/function approximation settings.
Theory on double Q-learning: Double Q-learning was proposed and proved to converge asymptoti- cally in Hasselt (010)). In |Wen et al. (2020b), 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 a unique optimal policy exists and the algorithm can converge. The most relevant work to this paper is Xiong al. (2020). which established the first finite- convergence rate for tabular double Q Q-learning with a polynomial learning rate. This paper provides sharper finite-tima convergence bounds for double Q-learning under a constant learning rate, which requires a different analysis approach.
Tabular Q-learning and convergence under various learning rates: Proposed in Watkins and Dayan (1 (192) 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);
Borkar and Meyn 2000 Melo (200T); Lee and He| (2020) by requiring the learning rates to satisty
2t=0 022 oc and t=o of oo. Another line of research focuses on the finite-time analysis of Q- learning under different choices of the learning rates. /zzeesvári ( 1998) captured the first convergence rate of Q-learning using linear learning rate (i.e., 02 = D) Under similar learning rates, Even- Dar and Mansour (203) provided finite-time results for both synchronous and asynchronous Q-learning with convergence rate heing exponentially slow function of T-y. Another popular choice is the
polynomial learning rate which has been studied for synchronous Q-learning in Wainwright (2019b)
Q-learning in Even-Dar and Mansour (2003). With this learning rate, however, the convergence rate still has gap with the lower bound (Azar et al. 2013). To handle this, more sophisticated rescaled linear learning rate was introduced for synchronous O-learning (Wainwright) [ Chen et al., (220)) and asynchronous Q-learning (Qu and Wierman 2020), and thus yields a better convergence rate. The finite-time bounds for Q-learning were also given for constant learning rate (Beck and Srikant, 2012]] Chen et al.) 2020 Li et al., 2020). In this paper, we focus on the constant learning rate and obtain sharper finite-time bounds for double Q-learning.
and for both synchronoussasyyccrroooo
Q-lcarning with function approximation: When the state-action space is considerably large or even infinite, the Q-function usually approximated by a class of parameterized functions. In such a case, Q-learning has been shown not to converge in general (Baird 1995). Strong assumptions are typically needed to establish the convergence of Q-learning with linear function approximation (Bertsekas)
and Tsitsiklis 1996, Melo et al. 2008 Zou et al. 2019 Chen et al. 2021b: Du et al., 2019 Yang and Wang 2019]Jia et al. 2019
Weng et al. [020a]] (021) or neural network approximation (Cai et al. 2019 Xu and Gu 2020). A two smmel variation of Q-learning with linear function
approximation was proposed in (Carvalho et al. 2020) which provably converges with probability 1. The convergence analysis of double Q-learning with function approximation raises new technical challenges and is an interesting topic for our future study.
2 Preliminaries on Double Q-learning
We consider a Markov decision process (MDP) over a finite state space S and a finite action space
A with the total cardinality given by D == [|) The transition kernel of the MDP is given by
+ [0, 1] denoted as PP)lss,). We assume a random reward function, denoted by F: : S x A
R, S x Ax S - [o, 1). and its expectation is denoted by [[ a, s')] Re Note that the
analysis of this paper easily applies to reward functions of different ranges by scaling. A policy
:= r(-ss) captures the conditional probability distribution over the action space given state E S.
3

---

For policy π, we define the Q-function (i.e., the state action value function) Q" E R|S|K|A| as
8
("(s,a)=
Roi
( ((s-()))...))
with (1) = (s, a). and y E (0, is the discount factor.
Both the vanilla Q-learning (Watkins and Dayan 1992) and double Q-learning (Hasselt
2010) aim to [Brttsekas)
find the optimal Q-function Q" which is the unique fixed point of the Bellman operator and Tsitsiklis 1996 given by
REL + +
TQ(s, a) = Eg Bxrp((ls,a)
(1)
d'EA
Note that the Bellman operator T is c-ontracctvve which satisfies the supremum norm ||Q]| := max,.a [Q(s.)) a)).
l S 11Q -Q'l under
Double Q-learning: The idea of double Q-learning is to keep two Q-tables (i.e., Q-function estima- tors) QA and Q", and randomly choose one Q-table to update at each iteration based the Bellman operator computed from the other Q-table. Let { Jez1 be a sequence of i.i.d. Bernoulli random variables satisfying P(33 = 0) = P(; = 1) = 0.5. At each time i, 8, = O indicates that QB is updated, and otherwise QA is updated. The update at time t can be written as,
QA =(1 âr a) (s) + ar(s, a) (Rs + (2 ( = (1- - (
(2)
as- Q (s) + as) - 3r) (6
for all a) E SxA, a" = arg , A a), and b" arg max, E. 2B B (s', ,a). The difference
between the (a)synchronous sampling is captured by the learning rate
āc(s,a) == ax
for synchronous version for asynchronous version
(TT(s. a),
where Te(s, a) = 1 (ss.a) is an indicator function. It can be seen that different from syn- chronous double Q-learning which updates all (s, aa-ppirs at each iteration, the asynchronous al- gorithm samples only one state-action pair to update chosen Q-estimator. Partieularly, in the synchronous version, is sampled independently between iterations following s' ~ P(|ss, a) for all (s, a), whereas in the asynchronous version, s' are consecutive sample transitions from one observed trajectory (i.e., Markovian sampling). Finally, we note that in (2) the rewards RG for both updates of Q4, and QB are the same copy of Rg Rs(s, a, 8').
As indicated by the update rules (2.. at each iteration only one the two Q-tables is randomly chosen to be updated. This chosen Q-table generates a greedy optimal action, and the other Q-table is used for estimating the corresponding Bellman operator (or evaluating the greedy action) to update the chosen table. Specifically, if Q is chosen to be updated, we use Q^ obtain the optimal action a and then estimate the corresponding Bellman operator using Q" to update Q As shown in Hasselt (2010), (s' a²) }] is likely smaller than E max, (Q'(s', (s). where the expectation is taken over the randomness of the reward for the same (s, a, s') tuple. Such a two-estimator framework adopted by double Q-learning can effectively reduce the overestimation.
Without loss of generality, we assume that QA4 and @B are initialized with the same value (usually both are all-zero tables in practice). For (a)synchronous double Q-learning, it can be easily shown that either Q-estimator uniformly bounded by Viaa := r throughout the learning process (see, for example Xiong al. )2020)) Specifically, for either i E (A, have ||Q:|] S Vinx and ||Q: @*1l < V max for all / 1, which will be useful in the finite-time analysis in the sequel.
3 Synchronous Double Q-learning
In this section, we start with modeling the error dynamics to be nested SAs, which will be useful to understand the nature of double Q-learning algorithms. Then we provide the finite-time results for synchronous double Q-leaming, followed by proof sketch to understand analysis insights.

---

3.1 Characterization of the Error Dynamics
In the following, we represent the (a)synchronous double Q-learning algorithms as a pair of nested SA recursions, where the outer SA recursion captures the eтror 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 noise term. Such a characterization enjoys various useful properties and prompts structured way of finite-time analysis for both sampling cases.
Outer SA: Denote the iteration error by re(s, a) = (s,, (* a) and define the empirical Bellman operator T.Q(s, a) == u, 5') 7mwx.eal(( a²). Then we can have for all / 2 1 (see Appendix A),
(4) where e, T,Q - Q" 12 = Q (i() T-1A- = Tr T,Q", and for synchronous version the equivalent learning rate 0 a) = (s, for asynchronous version" Note that by
rs+1 a)
(a(s.))(((..))((()) +E m)(s'aa)) +
aB,
design that we use the same sampled reward Rg in both T,Q² and T,Q2 in the definition of Gr(r)..
These newly introduced variables have several important properties. First of all, the noise term { is a sequence of i.i.d. random variables satisfying Es, = [[ Q- TQ Q" = 0 E RD. In particular, for the asynchronous case, we have 7/ & = (x( ae) which Markovian noise (process) for f. 2 1, where Tt, St RD_ Furthermore, it can be shown that (see Appendix A)
|| S Vmax
(5)
Moreover, is easy to show that (rx) > ||rell|. which follows from the contractive property of the empirical Bellman operator given the same next state. We shall say that G. is quasi-contractive in the sense that the 7-contraction inequality holds only with respect to the origin Ti =
Inner SA: We further characterize the dynamics of Pt Q - Q as an SA recursion (see Ap- pendix A):
(s+1(s,a)= -1 ()) + á., a) (Hi (v. (s, a) + (((s,a))
(6)
where (s, a) is defined in (2). H, EE (HI,)F), 14 H: He. and H, is defined in (18) in Appendix A. It can be shown that He is quasi-contractive satisfying [He((e))l < 1+z (Hchez is a martingale difference sequence with respect to the filtration F, defined by F1 = [0.2) where Q denotes the underlying probability space and for t 2.
2 ||]]] and
a ([Sk), (R o (sk, ak R4
St,,
for synchronous version, for asynchronous version.
F,
We note that for synchronous sampling, {sL} and R are respectively the collections of sam- pled next states and the sampled rewards for each (s, a) pair; and for asynchronous sampling, (5k, 0k2 8k+ h22 k22 are consecutive sample transitions from one observed trajectory.
Now our goal is to provide the finite-time bound for the nested SA recursions 44) and (6). Note that 3e (present in the outer SA) captures the random switching behavior of double O-learning, and plays an important role in connecting the error dynamics of inner and outer SAs. The error dynamics of the inner SA, which has unique contractive operator, affects the overall convergence via its coupling to the error dynamics of the outer SA.
In the sequel, we present our main result of the finite-time error bounds and consequently the time complexity of synchronous double Q-learning. We also make thorough comparison with existing results to highlight our significant improvement.
3.2 Finite-time Analysis
For the synchronous double Q-learning, at each iteration, one of the two Q-tables is chosen and all its state-action pairs are sampled and updated. In Theorem [ we present a finite-time error bound on the learning error ||rell Q Q'I]: based on which we further derive the time complexity in Corollary [] We then provide a proof sketch of Theorem Section 3.4 Its complete proof is deferred to Appendix B.
5

---

Theorem 1. Consider the synchronous double Q-learning in (2) with constant learning rate
a, E (0, 1) and y E (0,1). 1). Then there exist some universal constant >> such that with
probability at least 1 - 6, the learning error = Q Q' satisfies
2D
|| S he ||rll
(1 7)8 aln 5
(8)
for all 1. 2 1, where h = 1--1-
The following insights of the convergence of double-Q learning can be drawn from (8) The first term on the RHS of (8) shows that the initial error decays linearly with respect to the number of iterations (in logarithmic scale). The second term is constant enror which can be controlled by the size of the learning rate. By decreasing the learning rate a, this error vanishes at an order of Ó(va). This bound can be used to guide the choice of stepsizes according to the desired learning accuracy levels. Note that there is trade-off between the initial error decay rate and the constant learning error: smaller stepsize a yields smaller learning error, but leads to a larger h that is closer to 1 and thus slower decaying of the initial error.
With the above result, we are ready to derive the following time-complexity result, which characterizes the number of iterations required to achieve statistically meaningful finite-time error bound using synchronous double-Q learning. Recall that with the reward RG E 0, 1]. the Q-function falls within the range [0, 1. Therefore, is reasonable to consider E (0, 1-
Corollary 1. For any E (0, T-gb the time complexity for synchromous double Q-learning to achieve an e-accurate optimal Q-function (i.e., ||r/|| S E) with probability at least - Ó is given by
In 2
", = (1 71
Proof. We first show that if S
((1-)) and 2 [1-ya In (1-333 then ||r+ || & e. To proceed,
4 In
using Theorem I the first term the right hand side (RHS) of ( can be bounded
<(1 - 7) |n
hed ||
2
where (i) follows from the inequality + x S exp(x) and (ii) follows from the bound |||||| - --
Applying the upper bound of a to the second term on the RHS of (8, we obtain (1-7)s / In 20 I 2
which combining with ( proves the initial claim.
Then, further applying the bound on a in the lower bound T, we obtain the desired time complexity Sc In In
bound T
and Q denotes the omission of logarithmic factors in the corollary. n 2(1->) -|-
Comparison with existing results: compare our result with the time complexity synchronous double Q-learning provided in Xiong et al. (2020), which is given by
T = Ω (a-1)ee In (1 (1-
D
+ 1-7
(1-7 In
1
(10)
7)
where w (g.1). 1). We consider the following two major regimes. (a) For the c-dominated regime
(with relatively small 7), clearly the result in 10 does not achieve the order of Ω (In D/e²) whereas
our result does. Further, its approaching to such an order (w + 1 in Table ! is also at an additional
cost of an asymptotically large exponent on - (see the last term of (10)). (b) For the (1 7)-
dominated regime, the dependence on - can be optimized by taking w
10 compared
to which our result achieves an improvement by factor of O (nn ) (see Table Ib.
Comparing to the lower bound obtained in Azar et al. 2013)) which is T' = 52( 7ي- log D)
after translating to finite-time complexity under synchronous sampling, we see that the orders of dependence on D and 5 are tight. The order of & tight up to a logarithm factor. The only major gap appears in the dependence on 1 1 Y.

---

Error scaling versus iteretion@isccoutt
scaling versus iteration/isscourt
0.0.40
y- 0.50
10
10
0.70
Log eroo
Log
101
2.2.001, 0.92 8. pin
play y 0.98
10
10
10
101
1.0
10
Log
Figure I: Convergence rate under constant step- size (after 10s iterations)
Figure 2: Convergence comparison using differ- ent stepsizes
3.3 Numerical Experiment
To illustrate our theoretical results, we apply the synchronous double Q-learning to an MDP adapted from (Wainwright 2019b) by modifying the deterministic rewards there to be uniformly distributed over {R - 0.5, Rea + 0.5]. where Rsaa E {0, } is the expected reward at (s, a). We set the initial conditions as QA QB 1.0 with appropriate dimensions. Figure I iillustrates the convergence rate of synchronous double Q- Q-learning under constant stepsize with different discount values. Since the decay of the initial error usually dominates the learning process, it is not easy to observe the slower convergence rate T 22( when only using constant stepsize. To better illustrate the latter, we first apply the rescaled linear stepsizes (a; -ナ( at the beginning to reduce the initial errors. Then from = 103, we switch to a constant stepsize of a = 0.001. The plotted curves are averaged over 1000 independent runs. It can be observed that the ratio in the middle region under constant stepsize is about -0.5, which is consistent with our analysis of T 52( ( log 2) Ω( } (see Corollary
T. Besides, the non-diminishing learning errors are also captured by our Theorem
We also compare the convergence against polynomial stepsize (o, = çाकक) using the same MDP as the last example with the same initialization of the Q functions. The results are shown in Fig. 2 which are averaged over 10 independent runs. Under the same discount factor, constant stepsize generally yields faster convergence than a polynomial stepsize due to the linear decay rate (see Theorem D Convergence becomes slower when increasing the discount factor under both stepsizes, but polynomial stepsize is more susceptible to the change of discount factor than constant stepsize.
3.4 Proof Sketch of Theorem I
We first give a high-level idea about the difference between our approach and that in Xiong et al. (2020). Our central goal here is to bound the convergence error via pair of nested SA recursions, where the outer SA captures the learning error dynamics between one Q-estimator and the global optimum, and the inner SA captures the error propagation between the two Q-estimators. [iiong et al. (2020) constructed two block-wisely decreasing bounds for the nested SAs and characterized only block-wise convergence. Such an approach is rather complicated, and does not appear extend easily to the constant learning rate case. In contrast, we take a very different yet more direct approach here. We devise new analysis techniques directly bound both the inner and outer error dynamics per iteration. We then treat the output of the inner SA as a noise term in the outer SA, and combine the two bounds to establish the finite-time error bound of the learning error.
Specifically, our proof of Theorem I consists of five steps.
Step I: Deriving a template finite-time bound applicable to both SAs. We focus on a general SA with quasi-contractio operator, which captures the interconnection structure between the outer and inner SAs of double Q-learning via few noise and error terms. We provide a finite-time bound for such an SA by unfolding the SA recursively and carefully combining those noise terms into several smaller recursions. Such bound involves the coupling of the outer and inner SA error terms, and is critical for further deriving sharper finite-time bound for the synchronous Double-Q learning. We present this bound in Proposition in Appendix C.
7

---

Step II: Bounding outer SA dynamics E ||r || by inner SA dynamics E |plll We apply Proposi-
tion 1 to the error dynamics of r; in (4). and take the expectation obtain
B1rt1ll |l S he |1 + 7
h [Ell + E (xl) W
(11)
where h = 1 1 and W++1 (1-6,)W, e, with initialization Wi = 0.
The bound in (1T) captures the coupling between the nested SAs of double Q-learning, where is of the inner SA enters the outer SA error, we need to handle both |||/|| and Well.
tracking error term into the bound on of the outer SA. To further bound
Step III: Bounding E Will To bound E' |[all, we first construct an F--martingale sequence
W. = 11
a 2)
r-f W; for sist
where can be shown that W. W₁ and Wi = O. Following this way, for each > 1, we construct W as the martingale surrogate of W.. Equipped with such a property, and further applying the Azuma-Hoeffding inequality (see Lemma 3) and a Gaussian function integration technique (see Lemma 4), we show that
E W| S 2ñVnaxVa,
where 5 = 2v + VT and Vmnx is defined in 5 The complete results are presented in Propo- sition
Step IV: Bounding inner SA dynamics E ||p|]|- The inner SA captures the difference between two Q-estimators. and an error existing specifically in double Q-learning. Bounding E ||x,|| is of the key steps to handle the coupling between two nested SAs.
Note that the Vi -eccuuusionn (6) also satisfies the SA condition in Proposition 1. Then have
E well S 90 Σ W + M|
(12)
where 7 : 2- and M++1 = (1 0z ). M, adpe with initialization M1 = O. To bound E || ||, we construct the martingale surrogate Mr, for each 2 Specifically,, we construct the Fe-martingale sequence (Mi)si as M; (1 a+ M, with M++1 M++1 and E [ 0. Then by further characterizing the boundedness of the martingale, applying the Azuma-Hoeffding inequality, and the Gaussian function integration technique in Lemma 4, we obtain Proposition 3 that
|| Mc+1l < 2DVmaa V2a.
Finally, we substitute the bound of E M& into 12 to have
6 20
E |P <
(13)
The above bound indicates that the inner SA error is uniformly bounded by constant which can be controlled by the learning rate. Thus, the learning rate will play important role to guarantee the overall convergence by ensuring such an error to asymptotically vanish when entering into the outer SA error in (11).
Step V: Deriving overall finite-time complexity. The last step is "instantiate" the bounds of E| and E||e, in [TI. from which we have for any t 2 1,
6Dv2a (1 - (1-7)3-
E [|re |l S ||n||
(14)
The above expectation bound is equivalent to the high probability bound on [rr]]] by replacing In 2D with e In for some universal constant e > (see for example Wainwright (019b)). We then
readily have that (8) holds with probability at least 1 - 5.

---

4 Asynchronous Double Q-learning
In this section, we first develop the finite-time analysis for asynchronous double Q-learning, and then provide proof sketch for the main theorem.
4.1 Finite-time Analysis
Differently from the synchronous algorithm, at each iteration asynchronous double Q-learning updates only one state-action pair for randomly chosen Q-estimator. The sampled state-action pairs come from a single trajectory of the underlying MDP. Thus the statistical properties of the MDP plays an important role in the finite-time analysis.
We next make the following standard assumption, which is widely used in the studies of asynchronous Q-learning (Paulin 2015) Qu and Wierman 2020 Li et al. 2020).
Assumption 1. The Markov chain induced by the stationary behavior policy is uniformly ergodic.
We further introduce the following notations that will be used in the analysis. We denote by jar the stationary distribution of the behavior policy over the state-action space S x A and denote Mmin == min (s.)s. Hr (s, a). Intuitively, suggests that the smaller Mmnin is, the more iterations it takes to visit all state-action pairs in single trajectory. Alternatively, we define the so-called covering number in the following, which the number of iterations required to cover all state-action pairs at least once with the probability of at least one-half:
L min {
1
min (s1.A))ESxA
(81,
(15)
2
where B, denotes the event that all state-action pairs have been visited at least once in / iterations. In addition, the ergodicity assumption indicates that the distribution of samples will approach the stationary distribution fa at the so-called mixing rate, defined as
mix = min {
11 t:: max drv (P'()((1, 4
(16)
(EI.
where P'(-(ss,, a1)) is the distribution of (st, a;) given the initial pair (s1, a1), and drv (H,v) is the variation distance between two distributions μl,
Next, we provide the finite-time convergence result for asynchronous double Q-learning in the following theorem. We provide a proof sketch in Section 4.2 and give the full proof in Appendix F. Theorem Letry E (0, 8 e (0, f). E (0, [ي,] and suppose Assumption 7 holds. Consider asyn- chronous double Q-learning with a constant learning rate 04 = br min {11 (1- - 1 tais with some universal constant C1 > 0. Then asynchronous double Q-learning learns an e-accurate optimum, i.e., ||Q2 -Q' S 6, with probability at least 1 - 78 given the number T of iterations satisfies
T= (1 (1- +
Umix
In
Mmii (1 -
c(1 (1-7)2
where fmix is defined in T6).
The above time complexity result is given in terms of the mixing time. To facilitate the comparison with the existing results, we further characterize in terms of the covering number, which can be obtained from standard arguments for Q-learning (see (Li et al. 2020)).
Corollary 2. Under the same conditions of Theorem 2 consider constant learning rate a =
In PIT min {(1 (1-7)66 7 with some constant C2 > O. Then asynchronous double Q-learning can
learn an c-accurate optimum, i.e., 110
Q'Il S c, with probability at least 75 if the number T
of iterations satisfies
L
1
T = ñ
In
2 77
(11 7
where L is defined in 15

---

Comparison with existing results: We compare our result with the time complexity of asynchronous double Q-learning in Xiong et al. (2020), which is given by
L ((
DL
1 1 1-7 (1
1 In
T T=Ω (1- In
(1- +
(17)
7)
where w E (1/3, 1). Our result in Corollary 2 improves this characterization by orders of magnitude
in terms of the dependence of the time complexity on all key parameters c, D, D, 7; L (see Table I In particular, the dependence on the covering number L in (17) is optimized by choosing w = 2/3, under which Corollary 2 improves (17) by a factor of at least (LP). Comparing our results the lower bound obtained in Azar et al. (2013). the order of is tight up to a logarithm factor.
4.2 Proof Idea of Theorem 2
Differently from the proof of Theorem [ that does per iteration analysis, the central idea to analyze the asynchronous case is to capture the learning error terms of the key noise and error terms over all the preceding iterations (see equation (36) in Appendix F). A novel development lies in the new method for analyzing the noise and error terms that involve the Bernoulli switching parameters specifically in double Q-learning. For example, construct augmented Markov chain to the underlying MDP to derive a concentration inequality on the visitation probability of an (s, - in a Q-table when subject both Markovian sampling and Bernoulli switching (see Lemma 5). Moreover, we develop a conditional concentration analysis when bounding certain learning error term in the presence of Bernoulli switching (see Appendix G). These new techniques play critical role in improving the complexity bound in terms of its dependence on the sampling related parameters such as in (15) or mix 16 We refer the readers Appendix F for the complete proof.
5 Discussion and Conclusion
In this paper, we derived finite-time bounds for double Q-lernnig using constant learning rates under both synchronous sampling and Makovian asynchronous sampling, which order-wisely improves the dependence on all the important factors compared to the existing results. To achieve this, we developed systematic approach and a series of novel techniques to bound two nested stochastic approximation recursions.
Although the presented characterization does not achieve the same convergence rate the best available results of the vanilla learning (which are ( D ) for synchronous Q-learning and
②( (1-122))) for asynchronous Q-learning far, in terms of sample complexity. See Li et al. 2021 Chen
2020); Chen al. (2021a) etc.. and comparison tables therein), our analysis serves as an important step toward a fully understanding of the fast convergence of double-Q learning. The current analysis in this paper treats deterministic and random rewards in the same. However, since double Q-learning essentially reduces the estimation bias caused by the randomness or errors in rewards, further improvement on the order of the dependence on the discount factor might be achieved by explicitly taking into consideration how the variance of the random reward affects the convergence rate. This requires new and refined analysis. Moreover, better convergence rate might also be achieved by introducing other techniques into the algorithm, such as mini-batches. Experimentally, there is no conclusive comparison between Q-learning and Double Q-learning in the literature. For example, recent experimental study (Weng et al. 2020b) under similar setting to this paper shows that when using the same step size. Q-learning has a faster rate of convergence initially but suffers from a higher mean-squared error. On the other hand, when double Q-learning uses twice the step size of Q-learning, their simulation shows that double Q-learning achieves faster initial convergence rate, at the cost of possibly worse mean mean-squared error than Q-learning. This topic is still up to the future investigation to have a solid conclusion.
Another important yet challenging topic is the convergence guarantee for double Q-learning with function approximation. In addition to the lack of the contraction property of the Bellman operator in the function approximation setting. it is likely that neither of the two Q-estimators converges, or they do not converge to the same point even if they both converge. Characterizing the conditions under which double Q-learning with function approximation converges is still an open problem.
10

---

Acknowledgements
The work of L. Zhao was supported in part by the Singapore Ministry of Education Academic Research Fund Tier 1 under the grant R-263-000-E60-133 The work of H. Xiong and Y. Liang was supported in part by the U.S. National Science Foundation under the grant CCF-1761506.
References
Abed-alguni, B. and Ottom, M. A. (2018). Double delayed Q-learning. International Journal of Artificial Intelligence, 16(2):41-59
Azar, M. G., Munos, R., and Kappen, H. (2013). Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91(3):325-349.
Baird, L. (1995). Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier.
Beck, C. I.. Srikant, (2012). Error bounds for constant step-size Q-learning. Systems Control Letters, 61(12):103--120.
Bertsekas, D. P. and Tsitsiklis, J. N. (1996). Heuro-Dynanin Programmingg volume 5. Athena Scientific.
Bhandari, Russo, D., and Singal, R. (2018). finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory (COLT).
Borkar, and Meyn, S. (2000). The ODE method convergence stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469
Cai, Q.. Yang, Z., Lee, J. D., and Wang, Z. (2019). Neural temporal-difference learning converges to global optima. In Advances Neural Information Processing Systems (NeurIPS), pages 13312-1322.
Carvalho, D., Melo, S., and Santos. (2020). A new convergent variant of Q-learning with linear function approximation. Advances Neural Information Processing Systems (NeurIPS).
Chen, Z. Maguluri, S. T., Shakkottai, S., and Shanmugam, (2020). Finite-sampl analysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002.008574
Chen, Z., Maguluri, T., Shakkottai. S., and Shanmugam. K. (2021a). A Lyapunov theory for finite-sample guar- antees of asynchronous Q-Icarning and TD-learning variants. arXiv preprint https://orxivoorgaabae wttps///222220000 102.01 567..
Chen, Z., Zhang, S., Doan, T. T., Clarke, J.PP. and Maguluri, S. T. (2021b). Finite- saatle analysis of nonlinear stochastic approximation with applications in reinforvement learning. arXiv preprint DoXXv:1905.11425555
Du, S., Luo, Y., Wang, R., and Zhang, (2019), Provably efficient Q-learning with function approximation via distribution shift error checking oracle. In Advances in Neural Information Processing Systems (NeurIPS), pages 8058 8068.
Even-Dar, E. and Mansour, Y. (2003). Learning rates for Q-learning. Journal of Machine Learning Research, 5(Dec):1-25,
Hasselt, H. V. (2010). Double Q-learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 2613 2621.
Hasselt, H. v., Guez, A., and Silver, D. (2016). Deep reinforcement learning with double q-learning. In Proc. AAAI Conference on Artificial Intelligence (AAAI).
Hessel, M., Modayil, J.. Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., and Silver. D. (2018). Rainbow: Combining improvements in deep reinforcement learning. In Proc. AAAI Conference on Artificial Intelligence (AAAI).
Jaakkola, T., Jordan, M. L., and Singh, S. P. (1994). Convergence of stochastic iterative dynamic programming algorithms. In Advances in Neural Information Processing Systems (NeurIPS), pages 703-710
Jia, Z., Yang, L. F., and Wang, M. (2019). Feature-based Q-lcarning for two-player stochastic games. arXiv preprint arXiv: 0eee:/900000....
Lee. D. and He, N. (2020). A unitied switching system perspective and convergence analysis of Q-learning algorithms. In Advances in Neural Information Processing Systems.
11

---

Li. G., Cai, C., Chen, Y. Gu, Y., Wei. Y., and Chi, Y. (2021). Is Q-learning minimax optimal? tight sample complexity analysis. arXiv preprini arXiv:2007.1411.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. In Advances in Neural Information Processing Systems (NeurIPS).
Melo, F. S. (2001). Convergence of Q-learning: A simple proof. Institute of Systems and Robotics, Tech. Rep, pages 1-4.
Melo, F. S., Meyn, S. P., and Ribeiro, M. I. (2008). An analysis of reinforeement learning with function approximation. Proceedingy of the 25th international conference Machine learning, pages 671.
Paulin, D. (2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20.
Qu, G. and Wierman, A. (2020). Finite-time analysis of asynchronous stochastic approximation and Q-learning. arXiv preprint arXiv:2002.00200
Szepesvári, C. (1998). The asymptotic convergence-rate of Q-learning. In Advances in Neural Information Processing Systems (NeurlPS), pages 1064-1070.
Tsitsiklis, N. (1994). Asynchronous stochastic approximation and Q-learing, Machine Learning, 1853);185- 202.
Wainwright, M. J. (2019a). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
Wainwright, M. J. (2019b). Stochastic approximation with cone-contractive operators: Sharp Lo bounds for Q-learning. arXiv preprint 1956:2990.
Wainwright, M. J. (2019c). Varianco-reduced Q-learnin is minimax optimal. arXiv preprint 190.44777
Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine Learning, 8(3-4)2279-25 292.
Weng, B., Xiong, H., Liang, Y., and Zhang, W. (2020a). Analysis of Q-learning with adaptation and momentum restart for gradient descent. In Proc. 29th International Joint Conference on Artificial Intelligence (ICCAI-20), pages 3051-3057
Weng. B., Xiong, H.. Zhao, L.. Liang, Y., and Zhang, W. (2021). Finite-time theory of momentum Q-learning. In 37th Conference on Uncertainty in Artificial Intelligence, (UAI 2021).
Weng, W., Gupta, H., He. N., Ying, L., and R., S. (2020b). The mean-squauee mean-squared error of double Q-leariing. In Advances in Neural Information Processing Systems (NeurIPS).
Xiong, H., Zhao, L., Liang. Y., and Zhang, W. (2020). Finite-time analysis for double Q-learning. In Advances in Neural Information Processing Systems (NeurIPS).
Xu, P. and Gu. Q (2020). A finite-time analysis of Q-learnin with neural network function approximation. In Proc. of the 37th International Conference Machine Learning (PMLR), volume 119, pages 10555-10565
Yang, L. and Wang, M. (2019). Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning (ICML), pages -0044
Zhang, Q. Lin, M., Yang. L. T., Chen, Z., Khan. S. U., and Li, P. (2018a). A double deep Q-learning model for energy-efficiere edge scheduling. IEEE Transactions on Services Computing, 12(5):739-749.
Zhang, Y., Sun, P., Yin, Y., Lin, I.., and Wang, X. (2018b). Human-like autonomous vehicle speed control by deep reinforcement learning with double Q-leariing In Proc. IEEE Intelligent Vehicles Symposium (IV). pages 1251-1256.
Zhang, Z., Pan, Z., and Kochenderfer, M. J. (2017). Weighted double Q-learning. In International Joint Conferences on Artificial Intelligence (ICAI-17), pages 3455-3461.
Zou, S.. Xu, T., and Liang. Y. (2019). Finite-sample analysis for SARSA with linear function approximation. In Advances Neural Information Processing Systems (NeurIPS), pages 8665-8675
12


Reviews:
[{"review_id": "wTnGJynwonO", "reviewer": "Reviewer_vEGk", "summary": "This paper is about the analysis of both synchronous and asynchronous double Q-learning. This paper first does a quite introduction on double Q-learning, then focuses on the time complexity result for both synchronous and asynchronous double Q-learning. The time complexity result mentioned in their paper depends on the accuracy, discount factor, the number of state-action space, and covering number, and it is much better than the previous result you mention in your paper. In this paper, the authors also develop some new methods to deal with the convergence problem of double Q-learning, which makes us easier to solve the more challenging case of a constant learning rate. Since our interpretation of convergence result and time complexity of double Q-learning is still limited, I think the way you provide in the paper may give some new insight on this issue.", "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": "Highlights:\n1. To analyze double Q-learning, the authors divide the dynamic of double Q-learning into two different stochastic approximation recursions, the outer one and the inner one. It is a natural but wise idea to treat the noise term induced by the inner stochastic approximation and other noise terms separately. The recursion formulae for both stochastic approximation recursions are very important and will be useful for the following works. \n2. It is a good idea to find the similarity between the two recursions and design a template for both of them. That reveals the interrelationship between the two different stochastic approximation recursions. That also helps to make this paper more organized and easier to understand. \n3. It is a wise idea that the authors use martingale and Azuma-Hoeffding inequality to deal with the noise term in the analysis of double Q-learning. It may have a wider application in dealing with the noise term. I am curious about how you come up with the idea of analyzing noise using martingale and Azuma-Hoeffding inequality.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Suggestions:\n1. You mention the filtration F and the expectation H in the analysis of synchronous double Q-learning in your paper and Appendix A. I think in your paper, F and H are not formally defined. So I hope you can give a more detailed definition of F and H and explain what these notations mean in your paper. \n2. I cannot catch the main idea you use when you are proving the convergence result in asynchronous double Q-learning. I think you use a quite different way in asynchronous double Q-learning compared with synchronous double Q-learning. In synchronous double Q-learning, you analyze the error per iteration. However, in asynchronous double Q-learning, you combine the error in each iteration together and treat them as a whole. What is the idea behind your paper that makes you treat synchronous and asynchronous double Q-learning differently? Could you explain more about the method you use to analyze asynchronous double Q-learning in your paper? Does that mean the dynamic of synchronous double Q-learning is quite different from that of asynchronous double Q-learning? \n3. I find that the contraction property is very important in your analysis of double Q-learning. However, it is still a problem whether the function approximation method and the feedforward neural network have contraction property or under what condition it can have this property. I wonder what will happen if the contraction property is no longer satisfied in your paper. That might be helpful for the analysis of double Q-learning with function approximation. \n4. I think your result may be a significant improvement in reinforcement learning. However, It is not clear how far these improvements go towards attaining the performance we see in practice, and this should be something that is explicitly addressed by the authors.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "nOIH9U37aY1", "reviewer": "Reviewer_cHVh", "summary": "The paper provides new error bounds for double Q-learning using constant stepsize, which improves over existing result based on polynomial stepsize.  My only concern is that there are limited insights from this paper about double Q-learning. See detailed comments below. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Strength: \n- (Originality) The finite-time bounds under constant stepsize for double Q-learning are new and improve over existing paper by Xiong et al., 2020 which uses the polynomial stepsize.  The result follows by analyzing the error dynamics of Q_A-Q^* and Q_A-Q_B based on their stochastic approximation recursions.\n\n- (Clarity) The  paper for the most part is clearly written and easy to follow. Comparisons to related work are carefully discussed.\n\n- (Quality) Technical contribution is good although not particularly strong. The authors justified the difference in the analysis from Xiong et al, 2020,  but to a large extent, the analysis is more or less adapted from the existing Q-learning analysis in (Wainwright, 2019) and  (Li et al, 2020) for synchronous  ​and asynchronous settings. \n\nWeakness: \n- (Significance)  The main contribution of the paper is to show that using constant learning rate instead of polynomial rate yields better convergence of double Q-learning.  This of course is not too surprising given that similar results (e.g., Li et al, 2020) have already been established for Q-learning. I am not sure if this paper provides any more insights beyond this point. Given that the results only reflect the upper bounds (which may not necessarily  be tight), it certainly would be more convincing to provide some lower bound, or compare the exact behaviors, or at least validate the performance through numerical experiments. \n\n- (Significance) A perhaps more significant research question is  how does the non-asymptotic bounds of double Q-learning compare to Q-learning when both are using the constant stepsize.  The bound in this paper indicates that double Q-learning has a worse complexity than Q-learning with a factor of O((1-\\gamma)^{-2}) and requires a smaller stepsize than Q-learning.  But this deviates from what people normally observe in practice. It remains unclear whether the current bound is sharp or meaningful enough to shed light on the advantage of double Q-learning. \n\nMinor Suggestions:\n In the proof sketch, Proposition 1 is applied several times, but it is only presented in the appending. The definitions of H_t and mu_t in the SA recursion (6) is never defined in the main text. The authors mentioned their technical novelty of using augmented Markov chain and conditional concentration analysis. It is hard to understand what are these and why they are needed without going through all the proofs in the appendix. Some extra efforts are needed to make the main text more self-contained. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "_ZH2WfKUJUl", "reviewer": "Reviewer_fiWX", "summary": "This paper establishes tighter finite-time bounds for double Q-learning with constant learning rates in both synchronous\nand asynchronous Q-learning settings.\nA major difference between this paper and related work is that it only requires a constant learning rate to achieve fast convergence.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "**Originality**: I am not an expert in the theory area. To my knowledge, the proposed problem formulation and analysis are different from the related work discussed in this paper, which becomes more realistic.\n\n**Quality and Clarity**: The structure of this paper is well-organized. The discussion of preliminaries and related work is suitable.\n\n**Significance**: This paper aims to establish a better theoretical characterization of double Q-learning, which is a widely used technique in empirical research. I agree this paper studies a very important problem in reinforcement learning. To my knowledge, removing algorithmic assumptions on learning scheduling should have solid contributions to the related literature, since the constant learning rate setting is more realistic than related work and may serve some extent of insights for function approximation settings. I vote for *weak accept* since I have some concerns about the connections to practical scenarios (see questions).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am not an expert in reinforcement learning theory. My questions focus on how the given results can impact on practice. I am willing to increase my score if my concerns are addressed.\n\n(1) **(My major concern)** The main purpose of using double Q-learning is to reduce overestimation bias in value estimation. Does the analysis reveal any new insights on the reduction of overestimation? e.g., comparing to the analysis of vanilla Q-learning, I am curious about whether their error propagation behaviors are different. Does the reduction of overestimation can explicitly or implicitly provide any good properties for learning stability.\n\n(2) Line 341mentions that the current convergence analysis of double Q-learning has not achieved the same rate as that of vanilla Q-learning. How does their convergence performance compare in empirical evaluations with different learning rate scheduling mechanisms? I am curious about the literature, some discussions about related results are helpful. In addition, you can extend Table 1 to include prior results on vanilla Q-learning with different learning rate scheduling (maybe in Appendix). \n\n(3) In the asynchronous setting, whether the time complexity can translate to sample complexity? If so, why the proposed analysis does not rely on an exploration mechanism? To my knowledge, the fast convergence of tabular Q-learning relies on specific exploration strategies such as UCB exploration. Are there any assumptions on the chosen state-action pairs for updating?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "KfG5XBDZPYE", "reviewer": "Reviewer_NuYj", "summary": "This paper analyzes the convergence rate of double Q-learning under a constant learning rate. Previous results concerning the non-asymptotic convergence of double Q-learning mainly focus on polynomial learning rate, which yields a slower convergence rate. In this work, however, the authors discuss both synchronous Q-learning and asynchronous Q-learning under a constant learning rate. This paper proves that with learning rates $\\alpha \\in (0, 1)$, the double Q-learning algorithm converges to an $\\epsilon$-accurate global optimum with a time complexity of $\\tilde{\\Omega}(\\frac{\\ln D}{(1 - \\gamma)^7 \\epsilon^2})$ for the synchronous setting, and $\\tilde{\\Omega}(\\frac{L}{(1 - \\gamma)^7 \\epsilon^2})$ for the asynchronous setting.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\nThis work broadens our knowledge of the non-asymptotic convergence rate of Double Q-Learning. For the synchronous setting, this paper's result improves upon Xiong et al. (2020) by $\\mathcal{O}((\\ln \\frac{1}{1 - \\gamma})^7)$. For the asynchronous setting, this paper's result improves upon Xiong et al. (2020) by at least $\\mathcal{O}(L^5)$.\n\nThe main technical difficulty of using a constant learning rate lies in constructing two block-wisely decreasing bounds for the nested SAs. In this paper, the authors develop a novel analysis to directly bound both the inner and outer error dynamics and combine the two bounds to establish the finite-time error bound of the learning error.\n\nThis work extends the previous analysis of non-asymptotic convergence of double Q-learning. The article is well written and well structured.\n\nThere are, however, several points that can benefit the manuscript if tended to:\n\n(a) The paper introduces the constant learning rate scheme and the assorted theoretical analysis for double Q-learning. However, the sense of how well the proposed learning rate and analysis are reflected in real/practical scenarios is missing.\n\n(b) This paper provides rich theoretical analysis but very few intuitive examples. It would be great to include simple visual/numerical examples to give the audience more insights into the problem background and converging behaviors.\n\n(c) How tight is the convergence rate in practice?\n\n==================\n\nThanks for the detailed response! The authors have addressed all my concerns and I will keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations of their work in Section 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper offers an improved analysis of double Q-learning compared to some recent work, in particular giving better scaling in terms of the final error tolerance epsilon, the discount factor gamma, and some of the other quantities appearing in the bounds. However, there are concerns among the reviewers about the magnitude of the contribution, given that the techniques are not very novel, and that it is clear that the previous bounds compared against here are loose and can be substantially improved. Additionally, the reviewers agree that the paper does not seem to give much insight into the over-estimation problem, which is one of the main motivations for using double Q-learning, with the authors reply on this point not being very convincing. Nevertheless, on balance most reviewers lean towards acceptance, and I agree that improved bounds on the convergence time of double Q-learning are a clear contribution.

Decision: Accept (Poster)