# Finite-Time Analysis for Double Q-learning

arXiv: https://arxiv.org/abs/2009.14257 · HTML: https://mlsanity.com/paper/2009.14257/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2020.

## Built on by (most cited first, 12 of 12)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Action Candidate Driven Clipped Double Q-learning for Discrete and Continuous Action Tasks](https://mlsanity.com/paper/2203.11526/) (2022)
- [Sample Complexity Characterization for Linear Contextual MDPs](https://mlsanity.com/paper/2402.02700/) (2024)
- [On the Estimation Bias in Double Q-Learning](https://mlsanity.com/paper/2109.14419/) (2021)
- [Suppressing Overestimation in Q-Learning through Adversarial Behaviors](https://mlsanity.com/paper/2310.06286/) (2023)
- [Two-Step Q-Learning](https://mlsanity.com/paper/2407.02369/) (2024)
- [Finite-Time Analysis of Simultaneous Double Q-learning](https://mlsanity.com/paper/2406.09946/) (2024)

## Abstract (arXiv)

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~citethasselt2010double 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 ε-accurate neighborhood of the global optimum by taking tildeOmegaleft(left( frac1(1-γ)6ε2right)^frac1ω +left(frac11-γright)^frac11-ωright) iterations, where ω∈(0,1) is the decay parameter of the learning rate, and γ 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.