mlsanityData to 14 Oct 2026

Deep SOR Minimax Q-learning for Two-player Zero-sum Game

arXiv 2511.16226 ↗First posted 20 Nov 2025cs.LGcited by 0

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

In this work, we consider the problem of a two-player zero-sum game. In the literature, the successive over-relaxation Q-learning algorithm has been developed and implemented, and it is seen to result in a lower contraction factor for the associated Q-Bellman operator resulting in a faster value iteration-based procedure. However, this has been presented only for the tabular case and not for the setting with function approximation that typically caters to real-world high-dimensional state-action spaces. Furthermore, such settings in the case of two-player zero-sum games have not been considered. We thus propose a deep successive over-relaxation minimax Q-learning algorithm that incorporates deep neural networks as function approximators and is suitable for high-dimensional spaces. We prove the finite-time convergence of the proposed algorithm. Through numerical experiments, we show the effectiveness of the proposed method over the existing Q-learning algorithm. Our ablation studies demonstrate the effect of different values of the crucial successive over-relaxation parameter.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 7 of its 25 references that are in the map. First posted on arXiv 20 Nov 2025.

Builds on

7 of 25 references.

References · 7

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2024Deep Reinforcement Learning for Robotics: A Survey of Real-World Successescited by 176
  3. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  4. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  5. 2018Q-learning with Nearest Neighborscited by 37
  6. 2019A Generalized Minimax Q-learning Algorithm for Two-Player Zero-Sum Stochastic Gamescited by 8
  7. 2019Successive Over Relaxation Q-Learningcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024A Multi-Step Minimax Q-learning Algorithm for Two-Player Zero-Sum Markov Games
  2. 2024Double Successive Over-Relaxation Q-Learning with an Extension to Deep Reinforcement Learning
  3. 2021Reinforcement Learning In Two Player Zero Sum Simultaneous Action Games
  4. 2024FM3Q: Factorized Multi-Agent MiniMax Q-Learning for Two-Team Zero-Sum Markov Game
  5. 2024MinMaxMin Q-learning
  6. 2025Deep Double Q-learning
  7. 2024Zero-Sum Positional Differential Games as a Framework for Robust Reinforcement Learning: Deep Q-Learning Approach
  8. 2024Iterated Q-Network: Beyond One-Step Bellman Updates in Deep Reinforcement Learning