Finite-Time Analysis for Double Q-learning

Abstract

Although Q-learning is one of the most successful algorithms for finding the best action-value function (and thus the optimal policy) in reinforcement learning, its implementation often suffers from large overestimation of Q-function values incurred by random sampling. The double Q-learning algorithm proposed in~\citet{hasselt2010double} overcomes such an overestimation issue by randomly switching the update between two Q-estimators, and has thus gained significant popularity in practice. However, the theoretical understanding of double Q-learning is rather limited. So far only the asymptotic convergence has been established, which does not characterize how fast the algorithm converges. In this paper, we provide the first non-asymptotic (i.e., finite-time) analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $\epsilon$-accurate neighborhood of the global optimum by taking $\tilde{\Omega }\left({\left(\frac{1}{(1-\gamma {)}^6{\epsilon }^2}\right)}^{\frac{1}{\omega }}+{\left(\frac{1}{1-\gamma }\right)}^{\frac{1}{1-\omega }}\right)$ iterations, where $\omega \in (0,1)$ is the decay parameter of the learning rate, and $\gamma$ is the discount factor. Our analysis develops novel techniques to derive finite-time bounds on the difference between two inter-connected stochastic processes, which is new to the literature of stochastic approximation.

Accepted to NeurIPS 2020. The camera-ready version will include additional updates

References in corpus (9)

• Rainbow: Combining Improvements in Deep Reinforcement Learning
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Momentum Q-learning with Finite-Sample Convergence Guarantee

Cited by in corpus (2)

• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants