Search papers, labs, and topics across Lattice.
This paper critiques the widely used time-uniform self-normalized concentration inequalities in the context of discounted least-squares estimators for non-stationary problems, revealing a critical flaw through a scalar Gaussian counterexample. The authors demonstrate that the claimed bounded radius is violated with probability one, and they establish necessary conditions for valid boundaries that scale with \( R\sqrt{\log(T/\delta)} \). Ultimately, they provide corrections to the inequalities and discuss their implications for future analyses in bandit and reinforcement learning contexts.
A simple Gaussian counterexample reveals that existing concentration inequalities for discounted least-squares estimators are fundamentally flawed, necessitating significant corrections.
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 $\delta\leq1/2$ and $T/\delta$ is sufficiently large, any deterministic anytime boundary valid uniformly over the stated conditionally sub-Gaussian model class must be at least of order $R\sqrt{\log(T/\delta)}$ 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.
