arXiv preprint ·
Understanding the Asymptotic Transience of Q-Learning via Distributional Expansion
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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/2}$, whereas the maximization transient is of order $n^{-1}$ and converges almost surely, after rescaling by $n$, 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Random feature policy iteration for inverse mean field games with complex geometry and high dimensions
Gradient Flows over Convex Bodies for Learning Optimal Regularizers
Strategically Robust Multi-Agent Control
Exact Decisions and Certified Values in $L_\infty$-Norm Computation from State-Space Representations
A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.