A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning
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 sampl...
| Authors | Ege C. Kaya, Abolfazl Hashemi |
|---|---|
| Primary category | cs.LG |
| Published | 7 May 2026 |
| Last updated at source | 6 October 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.