An Invariant Measure Approach to the Convergence of Stochastic Approximations with State Dependent Noise

A new method is presented for quickly getting the ODE (ordinary differential equation) associated with the asymptotic properties of the stochastic approximation Xn + 1 = Xₙ + aₙ f(Xₙ ,ζ ₙ ) (or the projected algorithm for the constrained problem). Either aₙ → 0, or aₙ can be constant, in which case the analysis is on the sequence obtained when a → 0. The method requires that \ Xₙ ,ζ n - 1 \ be Markov with a “Feller” transition function, but little else. The simplest result requires that if Xₙ ≡ x, the corresponding noise process \ ζ ₙ (x),n 0\ have a unique invariant measure; but the “nonunique” case can also be treated. No mixing condition is required, nor the construction of averaged test functions, and f(· ,· ) need not be continuous. A detailed analysis of the way that \ ζ ₙ \ varies with \ Xₙ \ is not required. For the class of sequences treated, the conditions seem easier to verify than for other methods. There are extensions to the non-Markov case. Two examples illustrate the power and ease of use of the approach. Aside from the advantages of the method in treating standard problems, it seems to be particularly useful for handling the type of iterative algorithms which arise in adaptive communication theory, where the dynamics are often discontinuous and the “noise” is often state-dependent due to the effects of feedback. If the noise \ ζ ₙ \ is not “state-dependent,” then the Markov assumption can be dropped, and the method is even easier to use.