异步分类分布时序差分学习的锐利有限迭代理论

View PDF HTML (experimental)

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(\rho_{\min}^{-1}(1-\gamma)^{-2}\varepsilon^{-2})$ in the i.i.d. and $\tilde O(\mu_{\min}^{-1}(1-\gamma)^{-2}\varepsilon^{-2}+\mu_{\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(\rho_{\min}^{-1}(1-\gamma)^{-1-c}\varepsilon^{-2})$ and $\tilde O(\mu_{\min}^{-1}(1-\gamma)^{-1-c}\varepsilon^{-2}+\mu_{\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-\gamma)^{-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.

Submission history

From: Ege Can Kaya [view email]
[v1] Thu, 7 May 2026 19:07:00 UTC (48 KB)
[v2] Tue, 18 Aug 2026 00:30:40 UTC (98 KB)
[v3] Tue, 6 Oct 2026 02:54:14 UTC (2,994 KB)