Stochastic Tracking of Drifting Affine Fixed Points

Policy evaluation in a changing environment requires tracking a value function that moves during learning. We study this problem through affine contractions whose fixed points change over time. For a constant step size, we bound the total expected squared tracking error in terms of the initial error, observation noise, and target movement. The result extends known deterministic bounds to observations that can be correlated across time. In a scalar Gaussian model, matching lower bounds identify when a suitably chosen step size achieves the best possible tracking rate and quantify the cost of temporal correlation. We also show how to combine trackers with different step sizes without knowing the noise level or target variation, using additional bounded, unbiased observations of the target. Finally, we apply the analysis to synchronous tabular temporal-difference learning with simulator access and a common invariant distribution, and quantify the extra sampling cost of adaptation.