mlsanityData to 7 Oct 2026

A Discrete-Time Switching System Analysis of Q-learning

arXiv 2102.08583 ↗First posted 17 Feb 2021math.OC cs.AIcited by 16

Not on the map. Why?

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.

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

Builds on

4 of 20 references.

References · 4

  1. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  2. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  3. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  4. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 3; 2024: 4; 2025: 1; 2026: 6.

16 papers.

Sort:

  1. 2022Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic Viewcited by 4
  2. 2023Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approachcited by 3
  3. 2024Finite-Time Error Analysis of Soft Q-Learning: Switching System Approachcited by 2
  4. 2025Causality-informed Anomaly Detection in Partially Observable Sensor Networks: Moving beyond Correlationscited by 2
  5. 2026A Switching System Theory of Q-Learning with Linear Function Approximationcited by 2
  6. 2026Target Updates May Stabilize Linear Q-Learning: Periodic and Soft Dynamicscited by 2
  7. 2023Suppressing Overestimation in Q-Learning through Adversarial Behaviorscited by 1
  8. 2024A finite time analysis of distributed Q-learningcited by 1
  9. 2026Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iterationcited by 1
  10. 2021Control Theoretic Analysis of Temporal Difference Learningcited by 0
  11. 2023Continuous-Time Distributed Dynamic Programming for Networked Multi-Agent Markov Decision Processescited by 0
  12. 2024Finite-Time Analysis of Simultaneous Double Q-learningcited by 0
4 more
  1. 2024A Multi-Step Minimax Q-learning Algorithm for Two-Player Zero-Sum Markov Gamescited by 0
  2. 2026Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Gamescited by 0
  3. 2026Sign-Separated Asymmetric Finite-Time Error Analysis of Q-Learningcited by 0
  4. 2026Geometrically Averaged Hard Target Updates for Linear Q-Learningcited by 0