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

In the world of artificial intelligence, machines often learn by making a series of choices and observing the results, a process known as sequential decision-making. Imagine a traveler navigating a new city, trying to find the fastest route to a destination. With every step, the traveler gathers information about traffic and road conditions, using that knowledge to decide the next turn. To make good decisions, the traveler must constantly estimate the current state of the city based on past observations. However, in many real-world situations, the environment is not static; the traffic patterns change, roads are closed, and new construction appears. The traveler cannot rely solely on old data; they must weigh recent observations more heavily than those from long ago to stay accurate. This is the challenge of non-stationary learning: how to trust the past without being trapped by it.

Mathematicians and computer scientists have developed powerful tools to help these learning systems understand how much they can trust their own estimates. One such tool is a method called self-normalized concentration, which acts like a safety net. It calculates a margin of error that grows or shrinks depending on how much information the system has collected. If the system has seen a lot of data, the margin is tight; if it has seen little, the margin is wide. This ensures that the system's confidence intervals are always realistic. For years, researchers believed they had found a way to extend this safety net to handle changing environments using a technique called discounted least squares. This method assigns exponentially smaller weights to older data, effectively letting the system "forget" the distant past. A widely cited mathematical claim suggested that this approach provided a guaranteed, unchanging limit on the error, no matter how long the learning process continued.

A recent paper by Yi-Shan Wu challenges this long-held belief. The author demonstrates that the proposed safety net is flawed and that the claimed unchanging limit does not exist. Through a carefully constructed example involving a simple, one-dimensional scenario, the paper shows that the error in the system will inevitably exceed the proposed limit if the process runs long enough. It is not a matter of the system being unlucky; the mathematics proves that the boundary will be crossed with absolute certainty. The author identifies the root of the error in the original proof: the method used to combine different mathematical probabilities relied on a structure that breaks down when the rules of the game change over time. Specifically, the proof tried to stitch together different snapshots of the system's behavior as if they were part of a single, continuous story, but the mathematical ingredients used for each snapshot were actually different. Because of this mismatch, the logic that was supposed to guarantee safety for all time fails to hold up.

The paper does not leave the field without a solution. While the original claim of a fixed, unchanging limit is false, the author shows that the method still works perfectly well if you check it at any single, specific moment in time. To fix the problem for a process that runs indefinitely, the paper proposes a corrected approach. Instead of trying to hold a single, unchanging boundary, the safety net must be allowed to expand slowly over time. The author provides a new formula for this expanding boundary, which grows at a rate proportional to the square root of the logarithm of time. This means that as the system learns for longer and longer periods, the margin of error must be allowed to get slightly larger to remain valid. This correction is not a minor tweak; it is a fundamental requirement. The paper proves that no matter how clever the algorithm is, if it is to remain reliable over an infinite horizon, its error margin must grow at this specific rate.

The implications of this finding ripple through the field of machine learning, affecting many recent studies that relied on the incorrect, unchanging limit. Several prominent papers on non-stationary bandits and reinforcement learning used the flawed inequality to claim that their algorithms had tighter error bounds than they actually do. In some cases, these studies argued that their methods avoided a penalty that grows with time, suggesting a level of efficiency that the corrected mathematics shows is impossible. The author traces these dependencies, showing that while the core algorithms might still work, the theoretical guarantees supporting them need to be adjusted. The corrected bounds are slightly wider, but they are honest. They ensure that the safety net remains intact, even as the system forgets the past and learns from the present.

This work serves as a necessary correction to the mathematical foundations of adaptive learning. It clarifies that while it is possible to build systems that track changing environments effectively, there is a cost to doing so over an indefinite period. The system cannot maintain a perfectly tight grip on the truth forever without paying a price in the form of a slowly expanding margin of error. By exposing the flaw in the previous reasoning and providing a rigorous, proven alternative, the paper restores confidence in the field. It reminds researchers that in the complex dance of learning from changing data, the rules of probability are unforgiving, and shortcuts in the math lead to false promises of certainty. The path forward is clear: accept the slow growth of uncertainty as the price of adaptability, and build algorithms that respect this fundamental limit.