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

arXiv: https://arxiv.org/abs/2605.06866 · HTML: https://mlsanity.com/paper/2605.06866/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 59 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 1 of 1)

- [Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spaces](https://mlsanity.com/paper/2403.05811/) (2024)

## Built on by (most cited first, 4 of 4)

- [Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning](https://mlsanity.com/paper/2605.11289/) (2026)
- [Online Inference in Distributional Temporal-Difference Learning](https://mlsanity.com/paper/2608.14408/) (2026)
- [A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps](https://mlsanity.com/paper/2608.15966/) (2026)
- [Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data](https://mlsanity.com/paper/2609.38880/) (2026)

## Abstract (arXiv)

We study finite-iteration behavior of asynchronous categorical distributional temporal-difference methods, covering scalar categorical TD (CTD) in the Cram'er 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'er sample complexity to the true return law has leading term tilde O(ρmin-1(1-γ)-2varepsilon-2) in the i.i.d. and tilde O(μmin-1(1-γ)-2varepsilon-2+μmin-1tmix) 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-cvarepsilon-2) and tilde O(μmin-1(1-γ)-1-cvarepsilon-2+μmin-1tmix), 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.