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

Ege C. Kaya, Abolfazl Hashemi · 2026

Read A Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning by Ege C. Kaya, Abolfazl Hashemi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06866.txt.

Introduction

Ege C. Kaya and Abolfazl Hashemi give a sharp mathematical theory for a family of reinforcement learning methods. The methods learn a full distribution of future returns, not just an average, and they update in an asynchronous, categorical way. Earlier work lacked precise guarantees for how many steps they need to become accurate.

Kaya and Hashemi prove high-probability bounds for both random sampling and sampling along a continuing Markov path. They cover single-value and multi-value versions, plus discounted and fixed-length settings. Matching lower bounds show their leading rates cannot be improved, making the analysis the first complete rate picture for the multivariate version.

Catalog record

CREATOREge C. Kaya, Abolfazl Hashemi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE166 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06866

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning Ege C. Kaya, Abolfazl Hashemi Abstract Recent non-asymptotic analyses have substantially advanced the theory of distributional policy evaluation, but they largely concern synchronous full-state updates under a generative model, model-based estimators, accelerated variants, or different approximation architectures. Standard categorical temporal-difference learning is typically used in a different regime. It asynchronously performs a single-state update at each iteration and, in online settings, is driven by a Markovian trajectory. This leaves an important gap between existing finite-iteration theory and the categorical recursions most closely aligned with practical distributional temporal-difference implementations. We bridge this gap for two categorical policy-evaluation methods: scalar categorical temporal-difference learning in the Cramér geometry and multivariate signed-categorical temporal-difference learning in the maximum mean discrepancy geometry. After suitable isometric embeddings, both algorithms take the form of asynchronous single-state stochastic-approximation recursions that contract in a statewise supremum norm. This permits finite-iteration guarantees in discounted problems under both i.i.d. and Markovian state sampling, and in undiscounted fixed-horizon problems under i.i.d. episodic sampling. 1 Introduction Categorical representations are among the central approximation families in distributional reinforcement learning (RL) [ 4 , 39 , 15 , 14 , 51 , 30 , 40 , 5 ] . In the scalar case they underlie the categorical methods initiated by C51 [ 4 ] , while in the multivariate case they support signed-measure constructions for vector-valued returns [ 49 ] . These methods replace infinite-dimensional return-distribution objects with finite-dimensional ones while preserving the geometry that governs projected distributional policy evaluation [ 21 , 23 , 24 , 43 , 32 ] . For these categorical methods, the asymptotic picture is by now well understood [ 20 , 17 , 47 , 22 , 6 , 28 , 39 , 5 ] . The scalar categorical temporal-difference (CTD) method admits a projected Bellman contraction in the Cramér metric together with asymptotic guarantees [ 39 , 5 ] . The multivariate signed-categorical temporal-difference (MTD) method admits the analogous maximum mean discrepancy (MMD)-based contraction and theory [ 49 ] . What remains less well understood is the finite-iteration behavior of these TD methods. This matters because standard TD learning is not a synchronous full-state procedure [ 46 , 45 , 48 , 10 ] . In practice, each update modifies only the sampled state, and in online RL, the sampled states are generated by a Markovian trajectory. Finite-iteration guarantees for asynchronous, trajectory-driven updates are therefore the natural benchmark for understanding how quickly CTD and MTD approach their projected fixed point in regimes relevant to practice. Several recent results address neighboring finite-iteration questions [ 37 , 7 , 44 , 34 , 16 , 36 , 8 , 52 , 41 , 35 ] . These works establish that non-asymptotic distributional analysis is feasible, but do not provide a finite-iteration theory for the standard asynchronous categorical recursion driven by one-state updates. The present paper is organized in two halves. The first treats discounted policy evaluation under i.i.d. and Markovian sampling, with a framework guided by 12 , 13 , 11 , 38 , 29 , 9 , 26 . The second treats a tractable instance of an undiscounted policy evaluation, in the finite, fixed-horizon episodic regime. Across both halves, the main theme remains the same: After suitable statewise isometric embeddings, CTD and MTD constitute an asynchronous stochastic approximation (SA) recursion in a block-supremum geometry. Practical interpretation of the sampling regimes. Each sampling model considered in this work has a practical RL interpretation. The discounted i.i.d. regime points to a replay-based or generative-model benchmark, where updates are formed from approximately independent samples drawn from a buffer or simulator, also akin to the synchronous analyses often used to study TD-style methods theoretically. The discounted Markovian regime is the standard online setting for TD learning, in which samples are generated sequentially along a single behavior trajectory. In the finite-horizon undiscounted case, the episodic regime is the standard reset-based formulation of finite-horizon RL, where interaction proceeds for a fixed horizon H and then restarts from an initial distribution. Our main claim is that, once CTD and MTD are written in the right statewise embedding, these update rules become asynchronous SA recursions with contractive structure enabling finite-iteration control. Contributions. 1. We establish finite-iteration guarantees for asynchronous CTD and MTD under discounted i.i.d. and Markovian sampling. 2. We establish finite-iteration guarantees for undiscounted fixed-horizon CTD and MTD under i.i.d. episodic sampling. 3. We record a deterministic representation-error decomposition that turns the projected fixed-point bounds into total-error bounds with an explicit projection bias term. 2 Related work Two lines of work are most directly relevant. On the finite-iteration side, 12 , 13 , 11 develop non-asymptotic SA tools for contractive recursions under i.i.d. and Markovian sampling, building on the broader TD and SA literature [ 7 , 37 , 38 , 29 , 9 , 26 ] . On the distributional side, 39 , 5 establish the scalar categorical projection and Cramér contraction theory underlying CTD, while 49 provide the multivariate signed-categorical MMD framework for MTD. For the undiscounted half, our setup follows the fixed-horizon viewpoint of 18 . Our contribution is to bring these threads together for the tabular asynchronous categorical recursions that are used in practice, rather than for synchronous or idealized surrogates. Recent non-asymptotic distributional analyses study several neighboring regimes. 36 and 8 analyze CTD with generative-model access, where updates are synchronous or accelerated. 52 and 41 study model-based or direct-estimation procedures with stronger sampling access. 50 focuses on offline policy evaluation, 35 studies linear function approximation, and 25 considers a KL-based categorical analysis with a different divergence and asymptotic emphasis. By contrast, we analyze the exact asynchronous recursions of CTD and MTD. 3 Discounted categorical policy evaluation We consider a discounted Markov decision process [ 45 ] (\mathcal{S},\mathcal{A},P,R,\gamma) with finite state space \mathcal{S} , finite action space \mathcal{A} , reward function R(s,a) , transition kernel P(\cdot\mid s,a) , and discount factor \gamma\in(0,1) . We assume that R:\mathcal{S}\times\mathcal{A}\to[0,1] in the scalar case, and R:\mathcal{S}\times\mathcal{A}\to[0,1]^{q},q\geq 2 in the multivariate case. A policy \pi is fixed throughout. The induced state trajectory is either i.i.d. with law \rho or a Markov chain with stationary distribution \mu_{\mathcal{S}} . In the Markovian case we assume irreducibility and aperiodicity. The finiteness of \mathcal{S} implies that the Markov chain resulting from the MDP with fixed policy \pi mixes geometrically [ 27 ] , i.e., that there exist constants C_{\mathrm{mix}}\geq 1 and \sigma_{\mathrm{mix}}\in(0,1) such that \sup_{x\in\mathcal{S}}\left\lVert\Pr(S_{k}\in\cdot\mid S_{0}=x)-\mu_{\mathcal{S}}(\cdot)\right\rVert_{\mathrm{TV}}\leq C_{\mathrm{mix}}\sigma_{\mathrm{mix}}^{k}\qquad\text{for all }k\geq 0. (1) For \delta>0 , we define the associated mixing time t_{\delta}:=\min\Bigl\{k\geq 0:\sup_{x\in\mathcal{S}}\left\lVert\Pr(S_{k}\in\cdot\mid S_{0}=x)-\mu_{\mathcal{S}}(\cdot)\right\rVert_{\mathrm{TV}}\leq\delta\Bigr\}. (2) For both CTD and MTD, we work with a block-supremum contraction metric \ell_{\infty} , which admits a statewise isometric embedding I to a product space with contraction norm \left\lVert\cdot\right\rVert_{2,\infty} , and a statewise projection \Pi^{\Theta} onto the space of \Theta -supported, state-indexed representations \mathcal{F}^{\mathcal{S}}_{\Theta} . We can then compose the distributional Bellman operator T^{\pi} to obtain the embedded, projected operator \mathcal{O}:=I\circ\Pi^{\Theta}T^{\pi}\circ I^{-1}. (3) This operator then admits a one-step sampled Bellman target \widehat{T}(U_{k};s,(R_{k},S_{k+1})) computed from a current estimate U_{k} and a random sample (R_{k},S_{k+1}) , satisfying \mathbb{E}\left[\widehat{T}(U_{k};S_{k},(R_{k},S_{k+1}))\mid U_{k},S_{k}=s\right]=(\mathcal{O}U_{k})(s), (4) and a recursion that takes the form U_{k+1}=U_{k}+\alpha_{k}P_{S_{k}}(\widehat{T}(U_{k};S_{k},(R_{k},S_{k+1}))-U_{k}(S_{k})), (5) where for each s\in\mathcal{S} , P_{s} denotes the coordinate projector

Read the complete text