{
  "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 $π$ 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 H^3/(μ_{\\min}\\varepsilon^2)+\\mathfrak h_\\star)$ transitions for $0<\\varepsilon\\le1$. 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(t_{\\rm 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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.38880",
  "author_total": 1,
  "authors": [
    {
      "name": "Yang Peng"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/7ac9b8h3dzmyg.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.38880",
  "fulltext_url": null,
  "id": "7ac9b8h3dzmyg",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.38880",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "openalex",
      "1702|Reinforcement Learning in Robotics"
    ]
  ],
  "openalex": "W7215042144",
  "pdf_url": "https://arxiv.org/pdf/2609.38880",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-09",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/7ac9b8h3dzmyg.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:28:46Z",
      "native_id": "2609.38880",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.38880"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:stat.ML",
      "subfield": "statistics"
    }
  ],
  "title": "Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data",
  "title_text": "Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data",
  "type": "preprint",
  "updated_at": "2026-10-30T12:28:46Z",
  "url": "https://research.draconitic.com/paper/7ac9b8h3dzmyg",
  "venue": "arXiv",
  "versions": []
}