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

Abstract:We study finite-iteration behavior of the exact asynchronous recursions used by categorical distributional temporal-difference methods. The analysis covers scalar categorical TD in the Cramér geometry and multivariate signed-categorical TD in the maximum mean discrepancy geometry. Existing statewise isometric embeddings turn both methods into single-state stochastic-approximation recursions that contract in a block-supremum norm, but the categorical operators are contractive only on invariant representation domains. We establish the required restricted-domain theory and obtain discounted bounds under i.i.d. sampling and under a Markovian trajectory. A Poisson-equation decomposition handles trajectory dependence without an explicit mixing-time window. For undiscounted fixed-horizon policy evaluation, we establish analogous finite-iteration guarantees for horizon-stacked categorical methods under episodic sampling. Together, these results provide a unified non-asymptotic analysis of asynchronous categorical distributional TD across scalar, multivariate, discounted, and fixed-horizon settings.

Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2605.06866 [cs.LG]

(or arXiv:2605.06866v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2605.06866 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.