# Stochastic Tracking of Drifting Affine Fixed Points

DevFeed: [Stochastic Tracking of Drifting Affine Fixed Points](<https://devfeed.tech/articles/stochastic-tracking-of-drifting-affine-fixed-points-93532.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2610.25699>)

Author: Sajad Khodadadian

Published: 2026-10-21T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [grpo](<https://devfeed.tech/topics/grpo.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [change](<https://devfeed.tech/tags/change.md>), [changes](<https://devfeed.tech/tags/changes.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [environments](<https://devfeed.tech/tags/environments.md>), [error](<https://devfeed.tech/tags/error.md>), [fixed](<https://devfeed.tech/tags/fixed.md>), [future](<https://devfeed.tech/tags/future.md>), [gaussian](<https://devfeed.tech/tags/gaussian.md>), [generative](<https://devfeed.tech/tags/generative.md>), [invariant](<https://devfeed.tech/tags/invariant.md>), [learning](<https://devfeed.tech/tags/learning.md>), [linear](<https://devfeed.tech/tags/linear.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [model](<https://devfeed.tech/tags/model.md>), [noise](<https://devfeed.tech/tags/noise.md>), [operator](<https://devfeed.tech/tags/operator.md>), [temporal](<https://devfeed.tech/tags/temporal.md>), [time](<https://devfeed.tech/tags/time.md>), [tracking](<https://devfeed.tech/tags/tracking.md>)

## AI overview

The paper analyzes linear stochastic approximation for time-varying affine operators whose fixed points drift, allowing observation noise to be correlated across rounds. For constant-step updates, it bounds cumulative expected squared tracking error in terms of initial error, noise, and fixed-point changes. Scalar Gaussian lower bounds show that, under specified conditions, a suitably chosen constant step size is worst-case optimal up to constant factors, even against estimators using future observations; the analysis also quantifies temporal correlation's effect. To avoid requiring prior knowledge of noise level or fixed-point variation, the authors propose an adaptive method using an additional bounded, unbiased observation of the fixed point. They apply the results to synchronous tabular temporal-difference value estimation in changing environments, assuming generative-model access and a common invariant distribution.

## Source excerpt

arXiv:2610.25699v1 Announce Type: new 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.