math.OCNov 11, 2026

Understanding the Asymptotic Transience of Q-Learning via Distributional Expansion

Authors: Shengbo Wang

Organizations: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Abstract

Q-learning has been empirically observed to exhibit substantial transient error. This transient remains uncaptured by the leading Gaussian limit because the central-limit normalization removes the smaller-scale displacement generated by the initial nonlinear evolution. On the other hand, worst-case finite-sample guarantees, while accounting for transient effects, can obscure the mechanisms responsible for the error on a particular problem instance. We develop a finer asymptotic analysis that gives an asymptotically exact characterization of this transient for a fixed instance. Specifically, for synchronous Q-learning in finite discounted Markov decision processes, we separate the last-iterate error into an optimal-policy temporal-difference (TD) component and a nonnegative displacement caused by maximization. The centered TD component has Gaussian fluctuations at scale n−1/2n^{-1/2}, whereas the maximization transient is of order n−1n^{-1} and converges almost surely, after rescaling by nn, to a random limit. This limit represents the propagated effect of maximization errors generated before the greedy policy stabilizes. We combine this characterization with an Edgeworth expansion of the TD component to identify the corrections to its Gaussian approximation, separating the effects of initialization, non-Gaussian TD fluctuations, and maximization. The results reveal how transient errors arise for individual Q-learning instances and how their effects persist below the central-limit scale.

Figures & tables

Explore similar work

CardsList
  1. Sign-Separated Asymmetric Finite-Time Error Analysis of Q-Learning

    May 15, 2026Donghwan LeeQ-LearningConvergence Analysis

  2. Hitting-Time Bounds for Asynchronous Q-Learning

    Oct 9, 2026Yang PengReinforcement LearningQ-Learning

  3. A Finite-Sample Analysis of Quantile Temporal-Difference Learning

    Aug 27, 2026Zijie Cheng, Xiang Li, Yang Peng +1Distributional RLStochastic Approximation