🤖 machine learning

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

This paper bridges the gap between existing finite-iteration theory and practical implementations by establishing non-asymptotic convergence guarantees for asynchronous, single-state categorical temporal-difference learning under both i.i.d. and Markovian sampling regimes.

Original authors: Ege C. Kaya, Abolfazl Hashemi

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ege C. Kaya, Abolfazl Hashemi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to navigate a maze. The robot doesn't just want to know the average distance to the exit; it wants to understand the full story of the journey. Maybe sometimes it gets stuck in a dead end (a long, bad outcome), and sometimes it finds a secret shortcut (a great outcome). In the world of Artificial Intelligence, this is called Distributional Reinforcement Learning. Instead of guessing a single number, the robot learns a whole "probability map" of all possible futures.

This paper is about making sure the robot learns this map quickly and reliably, even when it's learning on the fly, one step at a time, without a perfect map of the world.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: The "One-Step" vs. The "Big Picture"

Most previous theories about how these robots learn assumed they could look at the entire maze at once and update every single spot simultaneously. It's like a teacher standing in front of a classroom and correcting every student's homework at the exact same time.

But in the real world, robots learn asynchronously. They take one step, see what happens, update their knowledge for just that spot, and then move on. It's like a student correcting their own homework one question at a time as they go.

The authors noticed a gap: We had great math proving the robot would eventually learn if it could update everything at once, but we didn't have a guarantee for how fast it would learn when updating just one spot at a time, especially when the robot is wandering through the maze in a random, unpredictable path (like a real-life trajectory).

2. The Solution: Two New "Lenses"

The paper focuses on two specific ways robots represent these probability maps:

CTD (Scalar Categorical): Think of this as a standard ruler. The robot divides possible outcomes into buckets (like "short," "medium," "long") and counts how likely each bucket is.
MTD (Multivariate Signed-Categorical): Think of this as a sophisticated 3D scanner. It handles more complex, multi-dimensional outcomes and allows for "negative" weights in its math to handle tricky situations.

The authors' big breakthrough was realizing that if you look at these two methods through a specific mathematical "lens" (called an isometric embedding), they both turn into the same simple, predictable process. It's like realizing that a bicycle and a motorcycle, though different, both follow the same basic rules of physics when you look at them from the right angle.

3. The "Contraction" Magic

The core of their proof relies on a concept called contraction. Imagine you are trying to fold a large, messy blanket into a neat square.

Every time the robot updates its knowledge, it "folds" the messy possibilities closer to the correct answer.
The authors proved that no matter how the robot wanders (whether it picks random spots or follows a specific path), this "folding" process always happens. The distance to the correct answer shrinks with every step.

Because they proved this "folding" happens reliably, they could calculate exactly how many steps the robot needs to take to get within a certain distance of the perfect answer.

4. The Three Scenarios Tested

The paper tested this theory in three different "worlds":

The Random Simulator (i.i.d.): The robot gets to peek at random spots in the maze, like pulling cards from a shuffled deck.
The Real Walk (Markovian): The robot walks through the maze step-by-step. Where it goes next depends entirely on where it is now. This is the most realistic scenario.
The Fixed-Time Run (Fixed-Horizon): The robot has to finish the maze in exactly $H$ steps. There is no discount for waiting; it just needs to survive the fixed time.

For all three scenarios, the authors provided a "countdown timer." They gave formulas that tell you: "If you want the robot to be 99% accurate, it needs to take roughly X steps."

5. The "Noise" Difference

One interesting finding is how the two methods handle "noise" (mistakes or randomness):

CTD (The Ruler): Because it uses simple buckets, the mistakes are always bounded. The robot can never be too wrong in a single step. It's like a ruler that can only be off by a millimeter.
MTD (The 3D Scanner): Because it's more complex, the mistakes can grow slightly larger depending on how far the robot has already learned. It's like a 3D scanner where the error might grow if the object is very large, but the authors proved the math still holds up and the robot eventually converges.

6. The "Two Parts of the Error"

Finally, the paper separates the robot's total mistake into two parts:

The Learning Speed: How fast the robot is updating its notes (the math the paper solves).
The Map Quality: How good the "buckets" or "scanners" are at representing the real world. If the robot's buckets are too wide, it will never be perfectly accurate, no matter how long it learns. The paper shows that once you pick your buckets, the learning speed is guaranteed, and the remaining error is just the limit of your bucket size.

Summary

In short, this paper bridges the gap between "idealized theory" and "real-world practice." It proves that the popular methods robots use to learn about the future (Categorical Temporal-Difference learning) are not just lucky guesses. They are mathematically guaranteed to converge to the right answer, and the authors tell us exactly how fast that convergence happens, whether the robot is learning in a simulator or wandering through a chaotic real-world environment.

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

Problem Statement
Recent advances in distributional reinforcement learning (RL) have established strong asymptotic guarantees for categorical policy evaluation methods, specifically scalar categorical temporal-difference (CTD) learning in the Cramér metric and multivariate signed-categorical temporal-difference (MTD) learning in the maximum mean discrepancy (MMD) metric. However, existing non-asymptotic (finite-iteration) analyses largely focus on synchronous full-state updates, generative models, or idealized surrogates. In practical online RL settings, standard categorical TD learning operates asynchronously: it performs single-state updates at each iteration driven by a Markovian trajectory. This creates a theoretical gap between the established asymptotic theory and the finite-iteration behavior of the exact recursions used in practice. This paper addresses this gap by providing finite-iteration guarantees for asynchronous CTD and MTD under both discounted and undiscounted fixed-horizon regimes.

Methodology
The authors bridge the gap between practical asynchronous updates and finite-iteration stochastic approximation (SA) theory through a unified framework based on statewise isometric embeddings and block-supremum geometry.

Isometric Embeddings and Contraction:
- For CTD, the authors utilize the Cramér metric and a cumulative-mass isometric embedding ( $I_C$ ). This transforms the projected Bellman operator into a contraction in a block-supremum norm ( $\|\cdot\|_{2,\infty}$ ) with modulus $\sqrt{\gamma}$ (discounted) or a weighted contraction (fixed-horizon).
- For MTD, they employ the MMD metric with a characteristic kernel and a Gram-matrix embedding ( $I_M$ ). This similarly converts the projected Bellman map into a contraction in the block-supremum MMD geometry, with modulus $\gamma^{c/2}$ (discounted) or a weighted contraction (fixed-horizon).
Asynchronous Stochastic Approximation (SA) Formulation:
- The standard single-state update rule is recast as an asynchronous SA recursion: $U_{k+1} = U_k + \alpha_k P_{S_k}(\hat{T}(U_k; S_k, \xi_k) - U_k(S_k))$ .
- The analysis relies on abstract finite-iteration frameworks for contractive recursions under i.i.d. and Markovian sampling (building on Chen et al., Robbins-Monro, and Borkar).
- Perturbation Geometry: A critical distinction is made between the noise structures of the two methods. CTD operates in a bounded-noise regime due to the bounded support of categorical distributions and the Cramér geometry. In contrast, MTD operates in an affine perturbation regime because the signed-categorical projection is affine rather than uniformly bounded, leading to perturbation bounds that scale with the norm of the current iterate.
Regimes Analyzed:
- Discounted Policy Evaluation: Analyzed under both i.i.d. sampling (replay/generative model) and Markovian trajectory sampling (standard online RL). The Markovian case incorporates geometric mixing time bounds.
- Undiscounted Fixed-Horizon Evaluation: Analyzed for episodic tasks with a fixed horizon $H$ . Since there is no discount factor $\gamma < 1$ to drive contraction, the authors introduce a weighted block metric ( $\lambda^h$ ) across the horizon stack. This recovers a contraction property where horizon $h$ bootstraps from $h-1$ . The analysis is performed at episode boundaries to handle phase-dependent drift within an episode.

Key Contributions

Finite-Iteration Guarantees for Asynchronous CTD and MTD: The paper establishes explicit non-asymptotic convergence rates for the standard asynchronous recursions of both CTD and MTD. This is the first such theory for these specific methods under single-state, trajectory-driven updates.
Unified Framework for Discounted and Fixed-Horizon Settings: The authors provide a coherent theoretical treatment that covers both discounted problems (with i.i.d. and Markovian sampling) and undiscounted fixed-horizon problems (under i.i.d. episodic sampling).
Deterministic Representation Error Decomposition: The paper records a decomposition that separates the total error into an algorithmic term (controlled by the finite-iteration bounds) and a deterministic projection bias term (dependent on the categorical support family). This allows the SA analysis and discretization bias to be analyzed independently.
Explicit Constants and Step Size Regimes: The analysis provides explicit constants for three step-size regimes:
- Constant step size: Geometric convergence to an $O(\alpha)$ neighborhood.
- Linearly diminishing step size: Leading residual decay of $O(1/k)$ (squared error), implying $O(\epsilon^{-2})$ sample complexity for mean error $\epsilon$ .
- Polynomially diminishing step size: Decay of $O(1/k^z)$ , trading convergence rate for milder admissibility conditions.

Results

Discounted Regime: For both CTD and MTD, under i.i.d. sampling, the squared error converges at a rate of $O(1/k)$ with linearly diminishing step sizes. Under Markovian sampling, the rate is $\tilde{O}(1/k)$ , incurring a logarithmic overhead due to the mixing time of the underlying Markov chain.
Fixed-Horizon Regime: For undiscounted episodic tasks, the error at episode boundaries converges at rates analogous to the discounted case. Specifically, $O(1/m)$ convergence for squared error after $m$ episodes (equivalent to $O(\epsilon^{-2})$ transitions).
Noise Regimes: The results confirm that CTD benefits from uniform bounded noise, while MTD requires handling affine noise bounds, which introduces additional constants related to the iterate norm in the convergence guarantees.

Significance and Claims
The paper claims to bridge a significant theoretical gap between the asymptotic understanding of distributional RL and the practical, asynchronous, single-state updates used in implementations. By demonstrating that standard categorical recursions constitute asynchronous SA schemes with contractive structures in suitable embeddings, the authors enable rigorous finite-iteration control.

The authors modestly note the scope of their work:

The theory is limited to tabular, finite-state policy evaluation and does not address control or policy improvement.
The guarantees are expectation bounds rather than high-probability bounds.
The results apply to the exact asynchronous recursions used in practice, distinguishing them from prior work that analyzed synchronous or model-based surrogates.

The work establishes that once CTD and MTD are formulated with the appropriate statewise embeddings, their update rules possess the necessary structural properties (contraction, Lipschitz continuity, and controlled perturbation) to be analyzed using modern non-asymptotic SA tools, providing the first finite-iteration theory for these widely used distributional methods in realistic online settings.