{
  "abstract": "We study finite-iteration behavior of asynchronous categorical distributional temporal-difference methods, covering scalar categorical TD (CTD) in the Cramér geometry and multivariate signed-categorical TD (MTD) in the maximum mean discrepancy (MMD) geometry. We establish high-probability guarantees under i.i.d. sampling and under a continuing Markovian trajectory. For CTD, the Cramér sample complexity to the true return law has leading term $\\tilde O(ρ_{\\min}^{-1}(1-γ)^{-2}\\varepsilon^{-2})$ in the i.i.d. and $\\tilde O(μ_{\\min}^{-1}(1-γ)^{-2}\\varepsilon^{-2}+μ_{\\min}^{-1}t_{\\mathrm{mix}})$ in the Markovian setting, without using variance reduction or data dropping. For MTD, the MMD sample complexity has leading terms $\\tilde O(ρ_{\\min}^{-1}(1-γ)^{-1-c}\\varepsilon^{-2})$ and $\\tilde O(μ_{\\min}^{-1}(1-γ)^{-1-c}\\varepsilon^{-2}+μ_{\\min}^{-1}t_{\\mathrm{mix}})$, where $c\\in(0,2)$ is the homogeneity exponent of the MMD kernel, and they reduce to the CTD rates when $c=1$. These are, to our knowledge, the first finite-iteration rates for MTD. For undiscounted fixed-horizon policy evaluation, the same analysis applies to fixed-horizon versions of CTD and MTD under i.i.d. and episodic sampling, and the rates match the discounted ones with the effective horizon $(1-γ)^{-1}$ replaced by the horizon $H$ in the leading term. Matching minimax lower bounds show that the leading terms, and the implied $1$-Wasserstein rates, are optimal under i.i.d., Markovian, and episodic sampling. Together, these results provide a unified non-asymptotic analysis of asynchronous categorical distributional TD across scalar, multivariate, discounted, and fixed-horizon settings, with rates that are minimax optimal in their leading terms.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2605.06866",
  "author_total": 2,
  "authors": [
    {
      "name": "Ege C. Kaya"
    },
    {
      "name": "Abolfazl Hashemi"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/2g97g1kdg2nd5.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2605.06866",
  "fulltext_url": null,
  "id": "2g97g1kdg2nd5",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2605.06866",
  "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",
      "math.OC"
    ],
    [
      "openalex",
      "1702|Reinforcement Learning in Robotics"
    ]
  ],
  "openalex": "W7160841635",
  "pdf_url": "https://arxiv.org/pdf/2605.06866",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-06",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/2g97g1kdg2nd5.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:26Z",
      "native_id": "2605.06866",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2605.06866"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning",
  "title_text": "A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:26Z",
  "url": "https://research.draconitic.com/paper/2g97g1kdg2nd5",
  "venue": "arXiv",
  "versions": []
}