A Discrete-time Switching System Analysis Of Q-learning

Abstract

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.

Stats

• citations12
• S2 citations—
• github stars0
• HF likes0
• heat score8.35
• arxiv keylee2021a

Related papers

• Finite-time Analysis Of Asynchronous Q-learning Under Diminishing Step-size From Control-theoretic View (2022)3.58
• From Set Convergence To Pointwise Convergence: Finite-time Guarantees For Average-reward Q-learning With Adaptive Stepsizes (2025)0.00
• Finite-time Error Analysis Of Soft Q-learning: Switching System Approach (2024)0.00
• Finite-time Analysis Of Minimax Q-learning For Two-player Zero-sum Markov Games: Switching System Approach (2023)0.00
• Finite-time Analysis For Double Q-learning (2020)0.00
• Constant Stepsize Q-learning: Distributional Convergence, Bias And Extrapolation (2024)0.00
• Deep Q-learning: Theoretical Insights From An Asymptotic Analysis (2020)10.35
• Finite-time Analysis Of Simultaneous Double Q-learning (2024)0.00