Abstract
Q-learning is known to suffer from overestimation bias: because the Bellman update maximizes noisy or imperfect action-value estimates, positive errors can be selected and propagated, causing learned values to exceed the true optimal values. This bias can slow learning, degrade policy quality, and make value estimates unreliable. Although the convergence of Q-learning has been studied extensively, convergence theory that explicitly reflects this overestimation mechanism remains limited. This paper studies the asymmetric convergence behavior of Q-learning induced by overestimation bias. We decompose the Q-learning error into its componentwise positive and negative parts and derive separate finite-time rates for the two components. The resulting certificates can assign a slower exponential envelope to the positive component than to the negative component. This rate separation provides indirect theoretical evidence for max-induced overestimation: positive errors can be amplified through the maximization step, whereas negative errors admit a sharper comparison with an optimal-policy system. The separation is a difference between upper bounds, so it need not hold for every realized Q-learning trajectory. Nevertheless, we construct examples in which the predicted asymmetry appears in the actual trajectory. The analysis gives deterministic and stochastic constant-step-size bounds and clarifies how overestimation enters the switching-system dynamics of Q-learning.
Explore similar work
Apr 21, 2026cs.LG
Q-learning is a fundamental algorithmic primitive in reinforcement learning. This paper develops a new framework for analyzing Q-learning from a switching linear system (SLS) viewpoint. In particular, we derive a stochastic SLS representation of the Q-learning error, and a finite-time error analysis through the joint spectral radius (JSR) of the corresponding SLS model, where the JSR is the exact worst-case exponential rate of the associated SLS. To the best of our knowledge, this is the first convergence rate analysis of standard Q-learning whose leading exponential rate is expressed through the JSR. The resulting rate is tied to the intrinsic worst-case exponential rate of the direct SLS representation and can be sharper than row-sum upper bounds when those bounds are conservative.
Donghwan Lee
May 10, 2026cs.LG
Q-learning is a fundamental algorithmic primitive in reinforcement learning. This paper develops a new framework for analyzing linear Q-learning from a switching linear system (SLS) viewpoint, where linear Q-learning denotes Q-learning with linear function approximation. We derive a stochastic SLS representation of the linear Q-learning error and obtain a finite-time error analysis for linear Q-learning through the joint spectral radius (JSR) of the associated SLS family; the JSR is the exact worst-case exponential rate of the corresponding SLSs. The JSR-based rate is tied to the intrinsic worst-case exponential rate of the SLS representation. Moreover, we provide a JSR-based certificate for convergence of linear Q-learning, which can be less conservative than one-step norm bounds.
Donghwan Lee, Han-Dong Lim
Jun 25, 2026cs.LG
This paper proposes a corrected heavy-ball Q-learning method for reinforcement learning (RL) and establishes convergence of its deterministic mean dynamics. It also identifies conditions under which the method is theoretically guaranteed to converge faster than standard Q-learning. The same construction is then extended to Q-learning with linear function approximation, where analogous convergence and acceleration statements are derived for the corresponding corrected fixed point. The sampled stochastic versions are treated through conditional-mean recursions and, in the stated linear-function-approximation setting, finite-time bounds. The analysis is based on a switched linear system (SLS) representation of Q-learning algorithms and on the joint spectral radius (JSR) of the associated switching families. This SLS viewpoint is not commonly used in standard analyses of Q-learning, and it provides a complementary framework and new insight into how heavy-ball momentum can accelerate Q-learning.
Donghwan Lee