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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 11 references that are in the map.
- First posted on arXiv 20 Aug 2026.

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

- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Self-Concordant Analysis of Generalized Linear Bandits with Forgetting](https://mlsanity.com/paper/2011.00819/) (2020)
- [Efficient Learning in Non-Stationary Linear Markov Decision Processes](https://mlsanity.com/paper/2010.12870/) (2020)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Randomized Exploration for Non-Stationary Stochastic Linear Bandits](https://mlsanity.com/paper/1912.05695/) (2019)
- [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026)

## Abstract (arXiv)

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 δ≤1/2 and T/δ is sufficiently large, any deterministic anytime boundary valid uniformly over the stated conditionally sub-Gaussian model class must be at least of order R√log(T/δ) 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.