Faster Non-asymptotic Convergence for Double Q-learning

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 -accurate global optimum with a time complexity of Ω ln D (1-γ) 7 2 , and the asynchronous algorithm achieves a time complexity of Ω L (1-γ) 7 2 , where D is the cardinality of the state-action space, γ 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 ( , 1 -γ, D, L). This paper presents a substantial step toward the full understanding of the fast convergence of double-Q learning.