# Double Successive Over-Relaxation Q-Learning with an Extension to Deep Reinforcement Learning

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

## 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 11 of its 36 references that are in the map.
- First posted on arXiv 10 Sep 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, 11 of 11)

- [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)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Maxmin Q-learning: Controlling the Estimation Bias of Q-learning](https://mlsanity.com/paper/2002.06487/) (2020)
- [MushroomRL: Simplifying Reinforcement Learning Research](https://mlsanity.com/paper/2001.01102/) (2020)
- [The Mean-Squared Error of Double Q-Learning](https://mlsanity.com/paper/2007.05034/) (2020)
- [Self-correcting Q-Learning](https://mlsanity.com/paper/2012.01100/) (2020)
- [A Generalized Minimax Q-learning Algorithm for Two-Player Zero-Sum Stochastic Games](https://mlsanity.com/paper/1906.06659/) (2019)
- [Successive Over Relaxation Q-Learning](https://mlsanity.com/paper/1903.03812/) (2019)
- [Generalized Speedy Q-learning](https://mlsanity.com/paper/1911.00397/) (2019)

## Abstract (arXiv)

Q-learning is a widely used algorithm in reinforcement learning (RL), but its convergence can be slow, especially when the discount factor is close to one. Successive Over-Relaxation (SOR) Q-learning, which introduces a relaxation factor to speed up convergence, addresses this issue but has two major limitations: In the tabular setting, the relaxation parameter depends on transition probability, making it not entirely model-free, and it suffers from overestimation bias. To overcome these limitations, we propose a sample-based, model-free double SOR Q-learning algorithm. Theoretically and empirically, this algorithm is shown to be less biased than SOR Q-learning. Further, in the tabular setting, the convergence analysis under boundedness assumptions on iterates is discussed. The proposed algorithm is extended to large-scale problems using deep RL. Finally, the tabular version of the proposed algorithm is compared using roulette and grid world environments, while the deep RL version is tested on a maximization bias example and OpenAI Gym environments.