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

arXiv: https://arxiv.org/abs/2609.38880 · HTML: https://mlsanity.com/paper/2609.38880/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 17 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise](https://mlsanity.com/paper/2605.20999/) (2026)
- [A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning](https://mlsanity.com/paper/2605.06866/) (2026)
- [A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging](https://mlsanity.com/paper/2606.24981/) (2026)

## Built on by (most cited first, 1 of 1)

- [Hitting-Time Bounds for Asynchronous Q-Learning](https://mlsanity.com/paper/2610.13901/) (2026)

## Abstract (arXiv)

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.