Online Inference in Distributional Temporal-Difference Learning

Reinforcement learning (RL) has evolved from simple value-based methods to sophisticated distributional approaches that aim to estimate the entire return distribution rather than just the mean. Early algorithms like TD(0) and SARSA focused on value functions, providing theoretical guarantees for convergence and asymptotic normality under i.i.d. assumptions. With the advent of distributional RL, methods such as C51, QR-DQN, and IQN have been developed to approximate the distribution of returns, capturing risk and tail behavior. These methods have shown empirical success in deep RL applications, but their statistical inference properties—such as confidence intervals and hypothesis testing—remain underdeveloped. Most existing work relies on offline data or multiple trajectories, limiting their applicability in online, single-trajectory settings. Recent advances have begun to explore the asymptotic behavior of distributional estimators, but comprehensive theoretical guarantees, especially involving bootstrap methods and nonsmooth functionals, are lacking. This paper addresses this gap by establishing the asymptotic normality and bootstrap consistency of online distributional TD estimators, extending the theoretical foundation of distributional RL.

The core challenge is to perform valid statistical inference for the return distribution and its functionals from a single Markov trajectory, which is a common scenario in online RL. Traditional approaches often assume i.i.d. samples or multiple independent trajectories, which are unrealistic in many real-world applications. Moreover, many important functionals—such as quantiles, tail risk measures, and expectiles—are non-smooth and do not satisfy the regularity conditions required for classical asymptotic theory. This complicates the derivation of confidence intervals and hypothesis tests. Additionally, existing methods lack rigorous validation of bootstrap procedures in the Markovian setting, especially for nonparametric estimators. Addressing these issues requires developing a unified theoretical framework that accounts for the dependence structure, handles non-smooth functionals, and validates bootstrap approximations in the online, single-trajectory context.

The paper's main innovations include: 1) developing a nonparametric distributional TD algorithm that estimates the full return distribution without parametric restrictions; 2) establishing a weak convergence result in Cramér space, showing that the scaled estimation error converges to a Gaussian process, leveraging the geometric ergodicity of the Markov chain; 3) designing an online multiplier bootstrap scheme that reuses the observed trajectory with independent bootstrap weights, and proving its conditional consistency; 4) formulating a local asymptotic theory for the estimated return CDF over neighborhoods of finitely many thresholds, enabling inference for non-smooth functionals like quantiles. These innovations collectively provide a rigorous statistical foundation for online distributional RL, bridging the gap between estimation and inference.

• �� Construct a nonparametric distributional TD recursion based on the Bellman operator, updating the estimated return distribution at each step using observed transitions.
• �� Apply Polyak–Ruppert averaging to the sequence of distribution estimates to stabilize convergence.
• �� Represent the estimation error as a zero-mean signed measure in Cramér space, and derive a recursive linear approximation that isolates the stochastic fluctuation component.
• �� Prove that the scaled error converges weakly to a Gaussian process in the Hilbert space, using martingale CLT and geometric ergodicity assumptions.
• �� Design an online bootstrap scheme where bootstrap weights are multiplied with the step sizes in the recursion, generating bootstrap replicates of the estimator.
• �� Establish the conditional weak convergence of the bootstrap estimator to the same Gaussian limit, validating bootstrap inference.
• �� For non-smooth functionals, develop a local CDF expansion within T^{-1/2} neighborhoods of thresholds, and prove their joint convergence to Gaussian processes.
• �� Use the functional delta method to transfer the Gaussian and bootstrap limits to the desired functionals, enabling confidence interval construction and hypothesis testing.

Simulations are conducted in finite-state Markov chains with rewards bounded in [0,1]. The experiments compare the empirical coverage probabilities of confidence intervals for the mean, variance, CVaR, and quantiles, under different trajectory lengths (T=1000, 5000). The step size parameters are set to αt = a(t + t0)^{-κ} with κ in (0.5, 0.75). Multiple independent runs validate the asymptotic Gaussian approximation and the bootstrap's conditional validity. The experiments also include non-smooth functionals like quantiles, verifying the local CDF expansion and the accuracy of the bootstrap-based inference. Results show that the confidence intervals achieve near-nominal coverage and that the bootstrap replicates accurately reflect the sampling distribution, even in small samples.

The key theoretical result is that the scaled estimation error converges weakly to a Gaussian process in the Hilbert space, with covariance determined by the stationary distribution and the martingale difference sequence. Empirically, the bootstrap method consistently approximates this distribution, with coverage probabilities close to 95% across various functionals. For nonsmooth functionals like quantiles, the local CDF expansion accurately captures the asymptotic distribution, enabling valid inference. The simulations demonstrate that the proposed approach outperforms naive methods that ignore dependence or non-smoothness, especially in finite samples. These findings confirm the theoretical guarantees and highlight the method's robustness in practical scenarios.

This framework is directly applicable to online policy evaluation in settings where data is collected sequentially, such as financial trading, autonomous vehicle safety assessment, and adaptive control systems. It allows practitioners to construct confidence intervals for risk measures and tail statistics in real time, facilitating risk-aware decision-making. The methods are compatible with deep RL architectures, provided the distributional estimates are obtained via neural network function approximators. Long-term, this approach can underpin the development of adaptive, risk-sensitive RL algorithms that quantify uncertainty and provide statistical guarantees, thereby enhancing safety, robustness, and interpretability in complex environments.

The current theory relies on assumptions of geometric ergodicity and finite state spaces, which may not hold in high-dimensional or continuous environments. Extending the results to deep RL settings involves additional challenges, such as function approximation errors and non-stationarity. The convergence rates and finite-sample performance require further empirical validation, especially in real-world applications with complex dynamics. The local asymptotic theory for nonsmooth functionals assumes density continuity and threshold uniqueness, which may not be valid for multimodal or degenerate distributions. Future work should aim to relax these assumptions, develop scalable algorithms, and validate the methods in high-dimensional, real-world scenarios.