Playing Dice with the Universe: Algorithms for Random Environments

Abstract

We describe stochastic recursive algorithms that find many applications in optimization under uncertainty, computational statistics, soft computing and machine learning, signal processing, communications, adaptive control, etc. The basic paradigm is that of the ‘stochastic approximation’ scheme introduced by Robbins and Monro in 1951. We describe the basic scheme and various theoretical and computational aspects related to its convergence and convergence rates. Several specific instances are also described, followed by more sophisticated versions such as distributed schemes and simulated annealing.