# A Generalized Minimax Q-learning Algorithm for Two-Player Zero-Sum Stochastic Games

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2019.

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

- [Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approach](https://mlsanity.com/paper/2306.05700/) (2023)
- [Two-Step Q-Learning](https://mlsanity.com/paper/2407.02369/) (2024)
- [Smoothing Policy Iteration for Zero-sum Markov Games](https://mlsanity.com/paper/2212.01623/) (2022)
- [A Multi-Step Minimax Q-learning Algorithm for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2407.04240/) (2024)
- [Double Successive Over-Relaxation Q-Learning with an Extension to Deep Reinforcement Learning](https://mlsanity.com/paper/2409.06356/) (2024)
- [Deep SOR Minimax Q-learning for Two-player Zero-sum Game](https://mlsanity.com/paper/2511.16226/) (2025)
- [NDRL: Cotton Irrigation and Nitrogen Application with Nested Dual-Agent Reinforcement Learning](https://mlsanity.com/paper/2512.16408/) (2025)
- [Dynamical low-rank equilibrium computation for stochastic games between advanced persistent threats and moving target defense](https://mlsanity.com/paper/2610.06885/) (2026)

## Abstract (arXiv)

We consider the problem of two-player zero-sum games. This problem is formulated as a min-max Markov game in the literature. The solution of this game, which is the min-max payoff, starting from a given state is called the min-max value of the state. In this work, we compute the solution of the two-player zero-sum game utilizing the technique of successive relaxation that has been successfully applied in the literature to compute a faster value iteration algorithm in the context of Markov Decision Processes. We extend the concept of successive relaxation to the setting of two-player zero-sum games. We show that, under a special structure on the game, this technique facilitates faster computation of the min-max value of the states. We then derive a generalized minimax Q-learning algorithm that computes the optimal policy when the model information is not known. Finally, we prove the convergence of the proposed generalized minimax Q-learning algorithm utilizing stochastic approximation techniques, under an assumption on the boundedness of iterates. Through experiments, we demonstrate the effectiveness of our proposed algorithm.