# A Discrete-Time Switching System Analysis of Q-learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 17 Feb 2021.

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

- [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)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)

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

- [Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View](https://mlsanity.com/paper/2207.12217/) (2022)
- [Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approach](https://mlsanity.com/paper/2306.05700/) (2023)
- [Finite-Time Error Analysis of Soft Q-Learning: Switching System Approach](https://mlsanity.com/paper/2403.06366/) (2024)
- [Causality-informed Anomaly Detection in Partially Observable Sensor Networks: Moving beyond Correlations](https://mlsanity.com/paper/2507.09742/) (2025)
- [A Switching System Theory of Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2605.11021/) (2026)
- [Target Updates May Stabilize Linear Q-Learning: Periodic and Soft Dynamics](https://mlsanity.com/paper/2606.02645/) (2026)
- [Suppressing Overestimation in Q-Learning through Adversarial Behaviors](https://mlsanity.com/paper/2310.06286/) (2023)
- [A finite time analysis of distributed Q-learning](https://mlsanity.com/paper/2405.14078/) (2024)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [Sign-Separated Asymmetric Finite-Time Error Analysis of Q-Learning](https://mlsanity.com/paper/2605.16103/) (2026)
- [Control Theoretic Analysis of Temporal Difference Learning](https://mlsanity.com/paper/2112.14417/) (2021)
- [Continuous-Time Distributed Dynamic Programming for Networked Multi-Agent Markov Decision Processes](https://mlsanity.com/paper/2307.16706/) (2023)
- [Finite-Time Analysis of Simultaneous Double Q-learning](https://mlsanity.com/paper/2406.09946/) (2024)
- [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)
- [Geometrically Averaged Hard Target Updates for Linear Q-Learning](https://mlsanity.com/paper/2606.10835/) (2026)

## Abstract (arXiv)

This paper develops a novel control-theoretic framework to analyze the non-asymptotic convergence of Q-learning. We show that the dynamics of asynchronous Q-learning with a constant step-size can be naturally formulated as a discrete-time stochastic affine switching system. Moreover, the evolution of the Q-learning estimation error is over- and underestimated by trajectories of two simpler dynamical systems. Based on these two systems, we derive a new finite-time error bound of asynchronous Q-learning when a constant stepsize is used. Our analysis also sheds light on the overestimation phenomenon of Q-learning. We further illustrate and validate the analysis through numerical simulations.