UIUC researchers crack TD learning inference, no tuning needed

Temporal-difference (TD) learning is a core reinforcement learning algorithm for estimating the value of a policy from sampled trajectories, but quantifying uncertainty in those estimates has historically required messy adjustments. In a new paper on arXiv, researchers Min Zeng, Yichen Zhang, and Xiaofeng Shao from the University of Illinois at Urbana-Champaign introduce a self-normalized inference framework for constant-stepsize TD learning under Markovian sampling. The key innovation is a functional central limit theorem that accounts for both the random TD matrix and the stationary iterate error, followed by a joint functional limit for parallel Richardson-Romberg (RR) recursions. A Brownian-bridge self-normalizer then yields asymptotically pivotal confidence regions for state-value contrasts—without estimating long-run covariance or selecting bandwidths/batch lengths.

The method is designed for practical use: for any prespecified contrast, it runs in a single pass over the data, and memory usage does not grow with trajectory length. The inferential center is the RR stationary target at a fixed stepsize, and the authors also analyze horizon-indexed designs where stepsize decreases across longer runs, showing the residual target shift becomes negligible at the root-n scale. Experiments on FrozenLake and Garnet benchmarks confirm that the confidence regions hit nominal coverage while correcting for RR target bias, with finite-sample performance matching theory. This effectively removes a significant tuning headache for reinforcement learning practitioners who want reliable statistical guarantees from a single Markov chain.