Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data

Abstract

We study the last iterate of standard tabular temporal-difference (TD) learning from a single trajectory of a finite Markov reward process. For discount factor $γ$, write $H=(1-γ)^{-1}$, and let $μ_{\min}$ and $t_{\operatorname{mix}}$ denote the minimum stationary probability and total-variation mixing time. We prove that last-iterate TD achieves sup-norm error at most $\varepsilon$ with high probability using$\widetilde O\left( \frac{H^3}{μ_{\min}\varepsilon^2} +\frac{t_{\operatorname{mix}}}{μ_{\min}} \right)$ transitions, for $0<\varepsilon\leq1$. This rate holds both for a constant step size selected for the target accuracy and for a decreasing schedule independent of the target accuracy and terminal time. The latter gives a simultaneous guarantee over all times beyond an explicit transient threshold. The statistical term retains the cubic effective-horizon dependence of synchronous TD, and the additive mixing transient has no extra horizon factor. The result allows non-reversible chains, arbitrary initial state distributions, and bounded rewards that may depend on the next state. The proof uses an anchored local Poisson equation in reverse time to control stochastic fluctuations without a mixing-time factor, and a hitting-time compensation identity to bound initialization error. The latter also yields a finer transient in terms of the worst expected reverse hitting time. A bound on the expected cumulative propagation mass extends this argument to decreasing step sizes. A three-state construction with known deterministic rewards gives matching minimax lower bounds for the statistical and mixing terms, up to logarithms, over specified model classes in a slow-mixing parameter regime.