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

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 π covered by b is evaluated with action importance ratios bounded by varrho. Write H=(1-γ)-1, with μ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 varepsilon with high probability after widetilde O(varrho H3/(μminvarepsilon2)+mathfrak h_star) transitions for 0<varepsilon≤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=π and varrho=1 recovers the on-policy rate. For aperiodic behavior chains, mathfrak h_star=widetilde O(trm mix/μ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.