Faster Non-asymptotic Convergence for Double Q-learning

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 -accurate global optimum with a time complexity of ( 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.

Tasks

Reproductions