Improving algorithms that track changing patterns in noisy data
Stochastic Tracking of Drifting Affine Fixed Points
Machine Learning
Summary
Estimating evolving hidden values from noisy observations is a common problem in data science. The authors study a method to track these changing values when the underlying system shifts over time and the noise is correlated. They provide mathematical guarantees on how close the tracking remains to the true values, even when noise and changes occur simultaneously. They also propose an adaptive technique that works well without needing prior knowledge about noise or changes. Finally, they show how their results apply to improving certain reinforcement learning algorithms that learn value functions in environments that keep changing.
What this means in practice
- •For machine learning engineers: Improve reinforcement learning algorithms to better track value functions when environments change dynamically.
- •For control system developers: Design adaptive filters that more accurately track shifting system states under correlated and noisy sensor data.
Authors
Sajad Khodadadian
Abstract
Linear stochastic approximation (SA) is widely used to estimate fixed points from noisy observations, but most finite-time analyses assume that the underlying operator remains fixed. We study linear SA with time-varying affine operators, where the fixed points change over time and the observation noise may be correlated across rounds. For constant-stepsize updates, we establish a bound on the cumulative expected squared distance between the iterates and the corresponding fixed points. The bound accounts for the initial error, observation noise, and changes in the fixed points over time. We also establish lower bounds for scalar Gaussian models, showing that, under specified conditions, a suitably chosen constant stepsize achieves the smallest possible worst-case cumulative error up to constant factors, even compared with estimators that use future observations. These results further quantify the effect of temporal correlation on estimation accuracy. Since choosing an appropriate stepsize generally requires knowledge of the noise level and how much the fixed points change, we develop an adaptive method that uses an additional bounded, unbiased observation of the fixed point to achieve an almost optimal algorithm without needing the knowledge of the noise level and the fixed point variation over time. Finally, we apply our results to value-function estimation using synchronous tabular temporal-difference learning in changing environments, assuming generative-model access and a common invariant distribution.