# A Multi-Step Minimax Q-learning Algorithm for Two-Player Zero-Sum Markov Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 12 of its 46 references that are in the map.
- First posted on arXiv 5 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [Q(λ) with Off-Policy Corrections](https://mlsanity.com/paper/1602.04951/) (2016)
- [Multi-step Reinforcement Learning: A Unifying Algorithm](https://mlsanity.com/paper/1703.01327/) (2017)
- [Revisiting Peng's Q(λ) for Modern Reinforcement Learning](https://mlsanity.com/paper/2103.00107/) (2021)
- [True Online Temporal-Difference Learning](https://mlsanity.com/paper/1512.04087/) (2015)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [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)
- [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)

## Abstract (arXiv)

An interesting iterative procedure is proposed to solve a two-player zero-sum Markov games. Under suitable assumption, the boundedness of the proposed iterates is obtained theoretically. Using results from stochastic approximation, the almost sure convergence of the proposed two-step minimax Q-learning is obtained theoretically. More specifically, the proposed algorithm converges to the game theoretic optimal value with probability one, when the model information is not known. Numerical simulation authenticate that the proposed algorithm is effective and easy to implement.