Kushner H.J., Yin.G. Stochastic Approximation and Recursive Algorithms and Applications

Springer-Verlag New York, Inc., 2003, 497 p., 2nd edition. The basic stochastic approximation algorithms introduced by Robbins and Monro and by Kiefer and Wolfowitz in the early 1950s have been the subject of an enormous literature, both theoretical and applied. This is due to the
large number of applications and the interesting theoretical issues in the analysis of dynamically defined stochastic processes. The basic paradigm is a stochastic difference equation such as θn+1 = θn+ nYn, where θn takes its values in some Euclidean space, Yn is a random variable, and the step size n 0 is small and might go to zero as n→∞. In its simplest form,θ is a parameter of a system, and the random vector Yn is a function of noise-corrupted observations taken on the system when the parameter is set to θn. One recursively adjusts the parameter so that some goal is met asymptotically. This book is concerned with the qualitative and asymptotic properties of such recursive algorithms in the diverse forms in which they arise in applications. There are analogous continuous time algorithms, but the conditions and proofs are generally very close to those for the discrete time case.
The original work was motivated by the problem of finding a root of a continuous function g(θ), where the function is not known but the experimenter is able to take noisy measurements at any desired value of θ. Recursive methods for root finding are common in classical numerical analysis, and it is reasonable to expect that appropriate stochastic analogs would also perform well.
In recent years, algorithms of the stochastic approximation type have found applications in new and diverse areas, and new techniques have been developed for proofs of convergence and rate of convergence. The actual and potential applications in signal processing and communications have
exploded. Indeed, whether or not they are called stochastic approximations, such algorithms occur frequently in practical systems for the purposes of noise or interference cancellation, the optimization of post processing or equalization filters in time varying communication channels, adaptive antenna systems, adaptive power control in wireless communications, and many related applications.
New challenges have arisen in applications to adaptive control. There has been a resurgence of interest in general learning algorithms, motivated by the training problem in artificial neural networks, the on-line learning of optimal strategies in very high-dimensional Markov decision
processes with unknown transition probabilities in learning automata, recursive games, convergence in sequential decision problems in economics, and related areas.