# Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 26 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (2021)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Statistical Inference for Policy Evaluation with Temporal Difference Learning](https://mlsanity.com/paper/2410.16106/) (2024)
- [Statistical inference for Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2505.19102/) (2025)
- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference](https://mlsanity.com/paper/2312.10894/) (2023)
- [Statistical Guarantees for High-Dimensional Stochastic Gradient Descent](https://mlsanity.com/paper/2510.12013/) (2025)
- [Revisiting the Constant Stepsize Stochastic Approximation with Decision-Dependent Markovian Noise](https://mlsanity.com/paper/2604.13378/) (2026)
- [High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2508.05570/) (2025)

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

- [Online Inference in Distributional Temporal-Difference Learning](https://mlsanity.com/paper/2608.14408/) (2026)

## Abstract (arXiv)

Constant-stepsize temporal-difference (TD) learning is attractive for policy evaluation, but inference from a single Markov trajectory must account for serial dependence and a stepsize-dependent stationary target. For fixed-stepsize linear TD, we establish a functional central limit theorem whose covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error. We then derive a joint functional limit for parallel Richardson--Romberg (RR) recursions driven by the same trajectory. A Brownian-bridge self-normalizer yields asymptotically pivotal confidence regions for prespecified state-value contrasts without estimating the long-run covariance or selecting a bandwidth or batch length. For such a contrast, the procedure admits a one-pass implementation whose memory does not grow with the trajectory length. At a fixed stepsize, the inferential center is the RR stationary target. We also study horizon-indexed designs in which the stepsize remains constant within each run and decreases across longer horizons. Under an explicit RR-dependent rate window, the residual RR target shift, multiplicative remainder, and initialization effect are negligible at the root-n scale, yielding inference for the projected Bellman solution. Experiments on FrozenLake and Garnet illustrate stationary-target coverage, RR target correction, and the finite-sample behavior of the horizon-indexed design.