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

Q-learning (QL) 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) QL, 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 SORQL (MF-DSORQL) algorithm. Theoretically and empirically, this algorithm is shown to be less biased than SORQL. Furthermore, 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, both the tabular version of the proposed algorithm and its deep RL extension are tested on benchmark examples.