Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections

arXiv:2608.19643v1 Announce Type: new Abstract: Self-normalized concentration inequalities are standard tools in bandit and reinforcement-learning analyses. A widely used weighted extension claims an analogous time-uniform guarantee for discounted least-squares estimators in non-stationary problems. A simple scalar Gaussian counterexample with a fixed parameter shows that the claimed bounded radius is crossed with probability one. For fixed discount and regularization parameters, we further show that, when eltaleq1/2 and T/elta is sufficiently large, any deterministic anytime boundary valid uniformly over the stated conditionally sub-Gaussian model class must be at least of order Rsqrt{log(T/elta)} at some time by horizon T; for nondecreasing boundaries, this order is required at time T. We identify the proof error: different terminal times use different Gaussian mixing distributions, so the fixed-time mixtures do not form one supermartingale, and the stopping-time argument does not repair this failure. Finally, we show that the weighted inequality remains valid at each fixed deterministic time, give valid finite- and infinite-horizon corrections, and discuss consequences for downstream analyses.

Related

• Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning
• ReCo: Reweighting GRPO Against Distributional Concentration
• Non-asymptotic estimates of the minimal risk in statistical learning

Source: arXiv cs.LG | 2026-08-21