# Finite-Time Analysis of Simultaneous Double Q-learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 14 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 9 of 9)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [Finite-Time Analysis for Double Q-learning](https://mlsanity.com/paper/2009.14257/) (2020)
- [The Mean-Squared Error of Double Q-Learning](https://mlsanity.com/paper/2007.05034/) (2020)
- [Final Iteration Convergence Bound of Q-Learning: Switching System Approach](https://mlsanity.com/paper/2205.05455/) (2022)
- [Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View](https://mlsanity.com/paper/2207.12217/) (2022)

## Abstract (arXiv)

Q-learning is one of the most fundamental reinforcement learning (RL) algorithms. Despite its widespread success in various applications, it is prone to overestimation bias in the Q-learning update. To address this issue, double Q-learning employs two independent Q-estimators which are randomly selected and updated during the learning process. This paper proposes a modified double Q-learning, called simultaneous double Q-learning (SDQ), with its finite-time analysis. SDQ eliminates the need for random selection between the two Q-estimators, and this modification allows us to analyze double Q-learning through the lens of a novel switching system framework facilitating efficient finite-time analysis. Empirical studies demonstrate that SDQ converges faster than double Q-learning while retaining the ability to mitigate the maximization bias. Finally, we derive a finite-time expected error bound for SDQ.