Heavy-Ball Q-Learning with Residual Weighting Correction

Donghwan Lee · 2026

Read Heavy-Ball Q-Learning with Residual Weighting Correction by Donghwan Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27112.txt.

Introduction

Lee proposes a corrected heavy-ball version of Q-learning, the classic method that teaches agents action values from rewards. Heavy-ball momentum, borrowed from optimisation, adds a push from the previous update to speed learning. Plain versions can misbehave, so a residual weighting correction reshapes the recursion. The correction makes the averaged update maps share a common eigenvector, a shared stable direction. Convergence of the corrected method is established in this theory paper from 2026.

Conditions are also derived where the corrected method provably converges faster than standard Q-learning. Analysis views the algorithms as switched linear systems, whose behaviour is governed by a joint spectral radius. That lens is uncommon in Q-learning theory and yields fresh insight into momentum effects. The same construction extends to linear function approximation, where values are estimated by weighted feature sums. Matching convergence and acceleration statements hold there too.

Catalog record

CREATORDonghwan Lee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27112

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Heavy-Ball Q-Learning with Residual Weighting Correction Donghwan Lee Abstract This paper proposes a corrected heavy-ball Q-learning method for reinforcement learning (RL) and establishes its convergence. 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. 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. Keywords. Q-value iteration, heavy-ball momentum, Bellman residual, joint spectral radius, switched linear systems, constant-preserving diagonal weighting 1 Introduction Q-learning [ 1 ] is one of the most fundamental and widely used methods in reinforcement learning (RL) [ 2 ] . In the tabular discounted setting, it learns the optimal Q-function through Bellman optimality updates without requiring an explicit transition model, and it also underlies modern deep variants such as deep Q-learning [ 18 ] . The usual convergence argument relies on the contraction property of the Bellman optimality operator, but this contraction can be weak when the discount factor is close to one. Therefore, many methods have tried to improve the speed of Q-learning or closely related value-iteration recursions. Examples include speedy Q-learning [ 3 ] , momentum-based Q-learning [ 13 ] , proportional-integral-derivative (PID)-type value iteration [ 4 ] , first-order accelerated value iteration [ 5 ] , and rank-one correction or deflation methods [ 8 , 11 ] . However, theoretical guarantees that a modified recursion is faster than standard Q-learning remain comparatively limited, especially for control problems in which the active greedy policy can change along the trajectory. This paper proposes a corrected heavy-ball Q-learning method obtained by modifying the simplest heavy-ball Q-learning recursion. The correction is designed so that the associated mean mappings share a common eigenvector. Along this common eigenvector, we derive conditions under which the corrected heavy-ball recursion has a smaller certified rate than the standard Q-learning recursion. The common eigenvector makes the analysis tractable and is the reason such a theoretical acceleration guarantee can be obtained. In the directions orthogonal to this common eigenvector, the present argument does not give the same acceleration guarantee. The contribution is therefore a precise certificate in one analytically identifiable direction, rather than a full-direction acceleration theorem, and this gives a useful perspective on the geometry of the heavy-ball Q-learning. For this analysis, we model the heavy-ball Q-learning mean dynamics as a switched linear system (SLS) [ 25 , 26 , 27 ] . The greedy action in the Bellman maximum determines the active mode of the SLS, and the resulting matrix family is analyzed through the joint spectral radius (JSR) [ 28 , 20 ] . This switching-system viewpoint provides a new route for studying the proposed heavy-ball Q-learning recursion and gives additional intuition about when acceleration can be certified. We also extend the method to linear function approximation and obtain analogous conclusions. The main analysis is written for deterministic mean dynamics, which keeps the role of the common eigenvector clear. The same update can be implemented as a model-free stochastic RL recursion. We also give a short discussion of the independent and identically distributed (i.i.d.) observation version. A Markovian observation version can be developed with standard stochastic approximation tools, as in [ 22 ] , but that extension is not developed here. 2 Related work Momentum-based modifications of value iteration have been studied from several perspectives. The proportional-integral-derivative (PID) accelerated value iteration framework in [ 4 ] interprets value iteration as a feedback-control system and introduces proportional-derivative (PD), proportional-integral (PI), and related PID variants. In fixed-policy settings, the PD/heavy-ball term changes the eigenvalues of the value-iteration error dynamics through a second-order companion polynomial associated with each eigenvalue of the transition matrix. Momentum value computation and accelerated value iteration were also studied in [ 5 ] , which connects value iteration with first-order optimization methods and analyzes momentum-type value-iteration updates for policy evaluation. Momentum-based accelerated Q-learning has also been studied in stochastic approximation settings [ 13 , 14 ] . Other acceleration mechanisms for dynamic programming iterations are related but technically different. Adaptive relaxation and lookahead methods for value iteration were studied in [ 6 , 7 ] ; Anderson acceleration applies a general fixed-point acceleration scheme to dynamic programming iterations [ 15 ] ; momentum value iteration in [ 16 ] averages successive Q -functions rather than using the heavy-ball Q-value iteration update analyzed here; and anchored/Halpern-type value iteration gives another provably accelerated Bellman-error mechanism for both Bellman consistency and optimality operators [ 17 ] . Speedy Q-learning is also relevant because it uses two successive Q-estimates to obtain faster finite-sample bounds in a model-free setting [ 3 ] . These works support the broader idea that past iterates or modified Bellman updates can accelerate Bellman-type recursions. In contrast, this paper proposes a modified heavy-ball Q-learning recursion that yields a theoretically verifiable acceleration certificate. To the best of our knowledge, the algorithm studied here has not appeared previously, and the convergence and acceleration analysis developed below is new. Unlike much of the existing momentum-based value-iteration and Q-learning literature, which focuses mainly on policy evaluation or stochastic approximation bounds, this paper treats the control setting for a simple constant-stepsize heavy-ball Q-learning recursion. The proof technique is also different: we represent the recursion as a switched linear system and compare the resulting switching families through the joint spectral radius rather than relying on fixed-policy spectral or contraction arguments. The slow constant direction of discounted dynamic programming iterations has a long history. Rank-one correction and extrapolation methods exploit the dominant stochastic matrix direction to improve value-iteration behavior [ 8 ] . Recent rank-one or deflation-based methods also use dominant-direction information, including rank-one modified value iteration and deflated dynamics value iteration [ 9 , 10 ] . More recent deflation-based approaches remove or quotient out the component along the common eigenvector in order to expose faster transverse dynamics; see, for example, the switching-geometry analysis of deflated Q-value iteration (Q-VI) [ 11 ] . The present paper is related in that every standard Q-VI switching matrix treats the constant-vector direction in the same way. This shared direction fixes the ambient-space benchmark rate, even though the remaining policy-dependent directions may decay faster. The mechanism studied here is different: heavy-ball momentum does not deflate or remove this direction, but turns it into a second-order linear time-invariant dynamics. The JSR is a standard measure of worst-case exponential growth for products of matrices under arbitrary switching; see, for example, [ 20 ] . Value-iteration updates naturally lead to SLS representations because the greedy action can change with the iterate. The SLS analysis used here is close to the direct switching representation of Q-learning [ 22 ] . The projected-error viewpoint is also related to recent JSR analyses of Q-VI geometry, including [ 23 , 11 ] . 3 Preliminaries 3.1 Notation The set of real numbers is denoted by \mathbb{R} ; \mathbb{R}^{m} is the m -dimensional Euclidean space; and

Read the complete text