Stochastic approximation

Estimating a solution of a deterministic equation through repeated noisy samples of its residual or update direction. Temporal-difference policy evaluation is an example. Convergence depends on stability, sampling, noise and step sizes, rather than merely on the existence of an unbiased sample.

A common condition along each repeatedly sampled component is ${\sum }_n{\alpha }_n=\infty$ and ${\sum }_n{\alpha }_n^2<\infty$. The first permits continuing correction; the second limits accumulated noise under the relevant stochastic-approximation hypotheses. The example ${\alpha }_n=1/n$ has a divergent harmonic sum and a convergent sum of squares. These conditions are not sufficient without suitable assumptions about the update dynamics and sampling.