# Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2025.

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

- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer](https://mlsanity.com/paper/2601.01502/) (2026)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?](https://mlsanity.com/paper/2603.25657/) (2026)
- [Gaussian Approximation for Asynchronous Q-learning](https://mlsanity.com/paper/2604.07323/) (2026)
- [Online Inference in Distributional Temporal-Difference Learning](https://mlsanity.com/paper/2608.14408/) (2026)
- [Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains](https://mlsanity.com/paper/2601.08184/) (2026)
- [Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization](https://mlsanity.com/paper/2604.04218/) (2026)
- [On Gaussian approximation for entropy-regularized Q-learning with function approximation](https://mlsanity.com/paper/2605.17678/) (2026)
- [Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation](https://mlsanity.com/paper/2605.19629/) (2026)

## Abstract (arXiv)

We establish novel and general high-dimensional concentration inequalities and Berry-Esseen bounds for vector-valued martingales induced by Markov chains. We apply these results to analyze the performance of the Temporal Difference (TD) learning algorithm with linear function approximations, a widely used method for policy evaluation in Reinforcement Learning (RL), obtaining a sharp high-probability consistency guarantee that matches the asymptotic variance up to logarithmic factors. Furthermore, we establish an O(T^-frac14log T) distributional convergence rate for the Gaussian approximation of the TD estimator, measured in convex distance. Our martingale bounds are of broad applicability, and our analysis of TD learning provides new insights into statistical inference for RL algorithms, bridging gaps between classical stochastic approximation theory and modern RL applications.