Metraipolis › archive › dc_196dd97d9318

Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data — arXiv:2609.38880

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.38880
License (as archived)
CC0-1.0
Archived
2026-10-07T13:47:23.268Z
SHA-256 of the archived text
6f9b6b48ea3660c2b7008b1328ddd8b721a8212543c0fee7b6e2c96a18c1d738
Stable URL of this page
https://metraipolis.com/documento/dc_196dd97d9318

How to cite

Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data — arXiv:2609.38880 — arXiv (en), https://arxiv.org/abs/2609.38880 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_196dd97d9318 (Metraipolis archive dc_196dd97d9318, sha256 6f9b6b48ea3660c2b7008b1328ddd8b721a8212543c0fee7b6e2c96a18c1d738)
BibTeX
@misc{dc196dd97d9318,
  title = {Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data — arXiv:2609.38880},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.38880},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_196dd97d9318; sha256 6f9b6b48ea3660c2b7008b1328ddd8b721a8212543c0fee7b6e2c96a18c1d738},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38880. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\gamma$, write $H=(1-\gamma)^{-1}$, and let $\mu_{\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}{\mu_{\min}\varepsilon^2} +\frac{t_{\operatorname{mix}}}{\mu_{\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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LG).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.38880 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:18:10.600Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).