Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning
This provides statistical inference tools for reinforcement learning algorithms, bridging classical stochastic approximation theory with modern RL applications.
The paper developed concentration inequalities and Berry-Esseen bounds for Markov chain-induced martingales, applying them to Temporal Difference (TD) learning to achieve a high-probability consistency guarantee matching asymptotic variance up to logarithmic factors and an O(T^{-1/4} log T) distributional convergence rate for Gaussian approximation.
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^{-\frac{1}{4}}\log 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.