Summary
Temporal-difference (TD) learning is a way machines predict future rewards based on past experience, but this prediction can be noisy and slow to learn. The paper studies how quickly and accurately TD learning finished running can get close to the best prediction using data generated by a Markov process, which models things that change based on current state. They find precise rates on how long learning takes depending on factors like how much future rewards are valued and how quickly states mix. Their results hold under various conditions and match the best possible bounds, meaning they show TD learning is as efficient as theoretically expected in these settings.
What this means in practice
- •For reinforcement learning engineers: Design learning algorithms with guaranteed error bounds for training models from correlated Markov data.
- •For algorithm designers: Use precise statistical error rates to improve convergence analysis of asynchronous learning in dependent data settings.
A theory result. No direct application yet.
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.