When noise has memory, how wrong can stochastic algorithms go?

Stochastic approximation algorithms power reinforcement learning and online optimization, but their behavior under realistic noise—correlated and heavy-tailed—remained poorly understood. This work establishes tight concentration bounds showing how error tails depend on step size and operator properties, ranging from sub-Gaussian to heavy Pareto distributions. The analysis introduces a novel Lyapunov function technique and shows when errors stay well-behaved versus when noise correlation causes catastrophic tail blow-up.