A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

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 Õ(ρ_min⁻¹(1−γ)⁻²ε⁻²) in the i.i.d. and Õ(μ_min⁻¹(1−γ)⁻²ε⁻²+μ_min⁻¹t_mix) in the Markovian setting, without using variance reduction or data dropping. For MTD, the MMD sample complexity has leading terms Õ(ρ_min⁻¹(1−γ)^−1−cε⁻²) and Õ(μ_min⁻¹(1−γ)^−1−cε⁻²+μ_min⁻¹t_mix), where c∈(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−γ)⁻¹ 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.

Online Inference in Distributional Temporal-Difference Learning
Yang Peng, Liangyu Zhang
arXiv16 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Quantitative constructive representation of the KdV flow in H³ via L²-energy-preserving centered-difference Chernoff approximations and Picard iteration
Comlan Edmond Koudjinan
arXiv22 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Distributional Difference-in-Differences: Aggregation Before or After Quantile Inversion?
Ulrich Hounyo
arXiv1 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces
Jingyi Jin, Martha White, Hao Wang
arXiv4 Nov 2026PreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv
Temporal-Difference Calibration of Black-Box Simulators
Min Zeng, Xin Wen, Xi Chen +2
arXiv26 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{kaya2026sharp,
  title = {{A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning}},
  author = {Ege C. Kaya and Abolfazl Hashemi},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2605.06866},
  eprint = {2605.06866},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.06866},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning
AU  - Ege C. Kaya
AU  - Abolfazl Hashemi
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2605.06866
UR  - https://arxiv.org/abs/2605.06866
AB  - 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 Õ(ρ_min^−1(1−γ)^−2ε^−2) in the i.i.d. and Õ(μ_min^−1(1−γ)^−2ε^−2+μ_min^−1t_mix) in the Markovian setting, without using variance reduction or data dropping. For MTD, the MMD sample complexity has leading terms Õ(ρ_min^−1(1−γ)^−1−cε^−2) and Õ(μ_min^−1(1−γ)^−1−cε^−2+μ_min^−1t_mix), where c∈(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.
ER  -

Abstract

Related

Cite