Sign-Separated Finite-Time Error Analysis of Q-Learning
This work offers a theoretical understanding of Q-learning's error dynamics, particularly the asymmetry causing overestimation, which is relevant for reinforcement learning researchers.
The paper provides a finite-time error analysis for constant step-size Q-learning by decomposing the error into sign-separated components, showing that negative errors converge faster than positive errors and linking this asymmetry to overestimation. Finite-time bounds are derived for both deterministic and stochastic settings.
This paper develops a sign-separated finite-time error analysis for constant step-size Q-learning. Starting from the switching-system representation, the error is decomposed into its componentwise negative and positive parts. The negative part is dominated by a lower comparison linear time-invariant (LTI) system associated with a fixed optimal policy, whereas the positive part is controlled by a linear switching system. The resulting bounds show that the negative-side LTI certificate is no slower than the positive-side switching certificate and may produce a faster exponential envelope. The analysis identifies a max-induced asymmetry in Q-learning error dynamics. This asymmetry is connected to overestimation: positive action-wise errors can be selected and propagated by the Bellman maximum, whereas negative errors admit an optimal-policy lower comparison. Finite-time bounds are provided for both deterministic and stochastic constant-step-size recursions.