Q-learning's transient error gets an instance-level account: maximization residuals settle at an n-1/4 random limit
Synopsis
Convergence analyses of synchronous Q-learning usually keep only the Gaussian limit, and central-limit normalization removes the smaller-scale displacement produced by the initial nonlinear evolution. This analysis splits the last-iterate error into an optimal-policy temporal-difference component and a nonnegative displacement caused by maximization, proves the latter converges almost surely to a random limit at the n-1/4 scale, and uses an Edgeworth expansion to give corrections to the Gaussian approximation. In a two-state example, the first-order corrected density tracks the empirical distribution better than the central-limit Gaussian.
Interpretation
Part of synchronous Q-learning's error was hidden by the Gaussian limit: residuals from maximization before the greedy policy stabilizes propagate through later updates and form a nonnegative displacement. The leading account was the Gaussian limit from the central limit theorem, whose normalization removes the smaller-scale displacement of the initial nonlinear evolution; uniform worst-case finite-sample guarantees cover the transient but obscure the error mechanism on a particular instance. For finite discounted Markov decision processes with a unique optimal action at every state and rescaled-linear step sizes, the displacement converges almost surely and in Lp at the n-1/4 scale to a random limit determined by the finitely many maximization residuals generated before the greedy policy stabilizes and by their propagation.
Separating the maximization displacement from the Gaussian correction of the policy-correct recursion requires the two not to interfere in the limit. The centered policy-correct error is of order n-1/2 while the maximization transient is of order n-1/4; correlation between them would change the first-order distributional correction. The analysis shows the centered error and the maximization transient converge jointly to an independent pair, with the Gaussian part independent of the random limit; the maximization transient therefore enters the n-1/4-order expansion only through its mean, and the first correction combines initialization bias, non-Gaussian temporal-difference fluctuations and maximization.
Although it lives at the smaller n-1/4 scale, the maximization transient can be large, with magnitude inversely related to the optimality gap. This offers an asymptotic explanation consistent with observations that maximization bias can substantially affect Q-learning performance, since maximization errors accumulate in the initial phase when actions are hard to distinguish. In a one-state, two-action example with bounded rewards, the mean maximization transient is shown to have a lower bound proportional to the inverse optimality gap; in the two-state numerical visualization, the empirical histogram still visibly deviates from the central-limit Gaussian while the first-order corrected density is closer, with the correction mainly from a positive bias term.
Perspective
The conclusions concern synchronous Q-learning on finite discounted Markov decision processes, require a unique optimal action at every state and use rescaled-linear step sizes; the numerical example is a two-state instance, and the inverse-gap lower bound comes from a one-state, two-action example.
The n-1/4-scale limit of the maximization transient is random, and its distribution enters the first-order expansion only through its mean, with higher-order contributions left for later work. The analysis is limited to synchronous sampling; extension to asynchronous updates and general nonlinear stochastic approximation is listed as a direction requiring harder proofs and coefficient computations.