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.] (020), 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.
2 V
In
244
(1-7))
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-y 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 scmel 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(()s,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 71Q -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 (s..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 R2 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 @ 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 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 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)
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 (1.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' |W&ll, 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 |Pll <
(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 CCen
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 wttpa///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 DoXXvv1905.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-lcarnnng for two-player stochastic games. arXiv preprint arXiv: 00e::/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": "vOr7_17GK4B", "reviewer": "Reviewer_Z175", "summary": "Thanks to the practical applicability of double Q-learning, this paper denoted to analyzing the finite-time convergence of double Q-learning algorithms with constant stepsizes. Building on existing analysis in Xiong etal'2020, the paper brings in some new analysis tools for nested stochastic approximation schemes and achieves faster non-asymptotic error bounds for double Q-learning. Some interesting observations are made on the practical usefulness of constant step in Q-learning. \n", "questions": "", "limitations": "", "rating": 5, "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": "Originality.\nThe paper builds heavily upon and compares against the work by Xiong etal'2020, but provides a faster finite-time convergence of nested SA schemes for which double Q-learning can be taken as an interesting example; and the topic is interesting, yet most of the algorithm and analysis follows from existing ones with several new techniques. However, the work Xiong etal'2020 establishes high-probability bound (1-\\delta) on the finite-time convergence error, while this paper focuses on the \n\nQuality.\nThe quality of this paper looks reasonabe and the bounds appear tighter than existing ones. \n\nClarity.\nThe paper is mostly clear, well-written, and easy to follow.\n\nSignificance.\nThe authors' effort in mproving finite-time error bounds of double Q-learning is appreciated. However, the paper is very similar to the work by Xiong et al'2020 in terms of both the content, algorithm, analysis, and results. The practical implication of the improved results is not fully demonstrated. Whether the results shed light on designing new Q-learning algorithms, or helps advise the efficient use of Q-learning algorithms? How general are the results?  Numerical simulations are also encouraged to validate the theoretical claims. \n\n-----------\nI have seen the rebuttal and read the other reviews, and updated the score. But I am still not convinced by the explanation of the \"typo\" and the merits of the paper relative to existing works. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Strengths.\n\nImproved high probability error bounds are derived. \nInteresting analysis involving some new tools. \n\nMajor comments/limitations.\n\n1. In general, function approximation is used, in particular nonlinear approximation? \n2. The paper missed comparison against a number of closely related works on two-timescale SA algorithms, Q-learning, and coupled Q-learning algorithms, especially the coupled Q-learning in [D. S. Carvalho, F. S. Melo, P. A. Santos'2020: A new convergent variant of Q-learning with linear function approximation].\n3. It is not clear why in (5) (same for the asychronous setting), the noise term {εt}t is a sequence of i.i.d. random variables satisfying Eεt = E[TbtQ∗] − Q∗ = T Q∗ − Q∗ =0 ∈ RD. Then how the Markovian correlation between s and s' is handled? \n4. When and why the SA in (9) has only one unique fixed point? Under what conditions? Do the considered two double Q-learning algorithms obey these conditions?\n5. What assumptions shall be made on the error \\epsilon_t and bias term v_t for the general SA scheme to cover the two types of double Q-learning? These are important to be claimed as a general result.\n6. No numerical simulations validate the claimed theoretical improvement vs the bound provided by Xiong etal'2020.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "tzlmEAeSdYC", "reviewer": "Reviewer_YcUb", "summary": "This work studies the Double Q Learning algorithm for reinforcement learning under tabular settings. The main technical contribution is a refined convergence to the optimal Q function with high probability under a specification of constant step-size. This improves upon previous results which use a polynomial learning rates. No experiments are given to contrast whether the performance gap translates to substantial gains in practice.", "questions": "", "limitations": "", "rating": 4, "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": "\nThe technical contribution of a novel convergence result for double Q learning is interesting, and clearly refines existing results on the performance of Double Q learning that require attenuating step-sizes. I agree that the results hinge upon some technical innovations illuminated on page 3, lines 68-75. However, I am not sure this alone is sufficient to warrant acceptance. That is because:\n\n1) what algorithmic ideas are fundamentally new here? It is well-known in stochastic approximation that constant step-sizes can result in faster improvement but to looser limiting neighborhoods of convergence. In that sense, none of the results here are particularly surprising or innovative here.\n\n2) The results here are restricted to tabular settings only, which limits their applicability/usefulness to preclude large-scale MDPs common in practice in technology today.\n\n3) There seem to be no experiments contrasting whether the improved learning rates are actually borne  out in practice. \n\nTherefore, this work should really be evaluated on the technical novelty of the proofs alone. While the characterization of the error dynamics in 3.1 which gives rise to the main results is well-executed, I feel the lack of actual algorithmic innovation or experimental validation is difficult to overlook.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "f7gzLM0ulyr", "reviewer": "Reviewer_k2nn", "summary": "The paper studied double Q-learning in RL and established finite time convergence analysis for both synchronous/asynchronous version of the algorithm. The complexity result improves the existing result in terms of the dependency on parameters such as $\\epsilon, 1-\\gamma, \\cdots$.", "questions": "", "limitations": "", "rating": 7, "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": "This papers studied Double Q-learning, which is one of the most widely used technique in RL. The authors established the non-asymptotic convergence result of both synchronous/asynchronous Double Q-learning for tabular discounted MDP. In particular, the paper proved $O(\\frac{1}{(1-\\gamma)^7\\epsilon^2})$ time complexity for both methods (ignoring other constants), improving upon the existing result that adopts a decaying step size. This is achieved by using more aggressive constants step size and a more refined analysis. It still remains unknown if Double Q-learning is provably faster than Q-learning, and this paper serves as an important step towards understanding Double Q-learning.\n\nWith the prevalence of Double Q-learning methods in various applications, it is of great importance to understand its theoretical guarantee. Overall this paper is solid and very well written. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See full review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Z7fm_eqrmp", "reviewer": "Reviewer_p1oe", "summary": "Vanilla Q learning often suffers from the over estimation problem i.e, it might choose bad actions initially which gets reinforced later on. Double Q learning maintains two Q functions $Q^A$ and $Q^B$ which are used to update each other. This helps in the case of random rewards. However, the complicated coupled dynamics of $Q^A$ and $Q^B$ makes the analysis much harder. Even though there are many satisfactory analyses for vanilla Q learning, double Q learning is lacking in this front.  This paper attempts to fill in this gap by giving a non-asymptotic convergence analysis of DQL, which is much better than the previous analyses in terms of every parameter. \n\nIn both the synchronous and asynchronous case (i.e all cases updated at once or updated from a stream of off-policy data respectively) they obtain a time complexity of $O(1/\\epsilon^2(1-\\gamma)^7)$ where $\\epsilon$ is the target error and $\\gamma$ is the discount factor. The proof technique mentioned in Section 3.3 considers the error propagation dynamics and analyzes the iterations using standard concentration inequalities.", "questions": "", "limitations": "", "rating": 6, "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": "I think this is an important problem with lots of recent interest. The paper is fairly well written and makes a good attempt at obtaining a finite time analysis of DQL. As mentioned in the paper, the results are worse than the guarantees obtained for the vanilla Q learning in terms of the discount factor $\\gamma$ which is the major drawback of the work.\n\nAll in all, I expect that the techniques established here would be useful in further investigation of DQL and eventually show that it outperforms vanilla Q learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

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

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

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

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