# Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approach

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 58 references that are in the map.
- First posted on arXiv 9 Jun 2023.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Memory-based control with recurrent neural networks](https://mlsanity.com/paper/1512.04455/) (2015)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [Periodic Q-Learning](https://mlsanity.com/paper/2002.09795/) (2020)
- [A Generalized Minimax Q-learning Algorithm for Two-Player Zero-Sum Stochastic Games](https://mlsanity.com/paper/1906.06659/) (2019)

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

- [Suppressing Overestimation in Q-Learning through Adversarial Behaviors](https://mlsanity.com/paper/2310.06286/) (2023)
- [A Multi-Step Minimax Q-learning Algorithm for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2407.04240/) (2024)
- [Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games](https://mlsanity.com/paper/2604.04394/) (2026)

## Abstract (arXiv)

The objective of this paper is to investigate the finite-time analysis of a Q-learning algorithm applied to two-player zero-sum Markov games. Specifically, we establish a finite-time analysis of both the minimax Q-learning algorithm and the corresponding value iteration method. To enhance the analysis of both value iteration and Q-learning, we employ the switching system model of minimax Q-learning and the associated value iteration. This approach provides further insights into minimax Q-learning and facilitates a more straightforward and insightful convergence analysis. We anticipate that the introduction of these additional insights has the potential to uncover novel connections and foster collaboration between concepts in the fields of control theory and reinforcement learning communities.