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

arXiv:2609.38880v2 Announce Type: replace 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 $\varepsilon$ with high probability after $\widetilde O(\varrho H^3/(\mu_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions for $0