stochastic approximation

Stochastic approximation is the mathematics of finding a target by taking many small, noisy steps. You cannot compute the exact quantity you want — say, an expectation — but you can sample noisy estimates of it, and if you average them in the right way you still home in on the true value. Q-learning, TD learning, and policy gradients are all stochastic-approximation algorithms in disguise.

The foundational result, due to Robbins and Monro, treats the update as a noisy version of a deterministic iteration whose fixed point you actually want. Under decaying step sizes and zero-mean, bounded-variance noise, the random trajectory tracks the underlying mean dynamics — an idea made precise by the "ODE method," which shows the discrete updates asymptotically follow a smooth ordinary differential equation toward its equilibrium.

The theory is asymptotic: it tells you where the iterates end up, not how fast, and the constants hidden in "eventually" can be enormous. It also assumes the mean update field is well-behaved; with function approximation that assumption can break, which is why convergence in deep RL is never guaranteed for free.