Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data

Abstract

We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy $b$ with an irreducible, possibly periodic state chain; a target policy $\pi$ covered by $b$ is evaluated with action importance ratios bounded by $\varrho$. Write $H=(1-\gamma {)}^{-1}$, with ${\mu }_{\min }$ the minimum stationary probability and ${\mathfrak{h}}_{\star }$ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most $\epsilon$ with high probability after $\tilde{O}(\varrho H^3/({\mu }_{\min }{\epsilon }^2)+{\mathfrak{h}}_{\star })$ transitions for $0<\epsilon \le 1$. The statistical term retains the cubic effective-horizon dependence of synchronous TD, while the initialization cost is additive in ${\mathfrak{h}}_{\star }$. Setting $b=\pi$ and $\varrho =1$ recovers the on-policy rate. For aperiodic behavior chains, ${\mathfrak{h}}_{\star }=\tilde{O}(t_{\mathrm{mix}}/{\mu }_{\min })$ recovers a mixing-time bound. The proof combines an anchored local Poisson equation in reverse time to control fluctuations without a mixing-time factor, a compensation argument for successive hitting costs, and an expected cumulative propagation mass bound for decreasing step sizes. Given the policy ratios and their bound, an empirical state-count rule attains the same rate without prior knowledge of model parameters. The framework covers nonnegative affine importance-weighted prediction updates, including successor features, transition-dependent discounting, and coupled finite-mode predictions. A perturbation estimate yields a time-uniform guarantee for online return-variance estimation. A three-state, two-action construction gives matching minimax lower bounds for both terms up to logarithmic factors on the considered parameter classes.