Regime Switching Stochastic Approximation Algorithms with Application to Adaptive Discrete Stochastic Optimization

This work is devoted to a class of stochastic approximation problems with regime switching modulated by a discrete-time Markov chain. Our motivation stems from using stochastic recursive algorithms for tracking Markovian parameters such as those in spreading code optimization in CDMA (code division multiple access) wireless communication. The algorithm uses constant step size to update the increments of a sequence of occupation measures. It is proved that least squares estimates of the tracking errors can be developed. Assume that the adaptation rate is of the same order of magnitude as that of the time-varying parameter, which is more difficult to deal with than that of slower parameter variations. Due to the time-varying characteristics and Markovian jumps, the usual stochastic approximation (SA) techniques cannot be carried over in the analysis. By a combined use of the SA method and two-time-scale Markov chains, asymptotic properties of the algorithm are obtained, which are distinct from the usual SA results. In this paper, it is shown for the first time that, under simple conditions, a continuous-time interpolation of the iterates converges weakly not to an ODE, as is widely known in the literature, but to a system of ODEs with regime switching, and that a suitably scaled sequence of the tracking errors converges not to a diffusion but to a system of switching diffusion. As an application of these results, the performance of an adaptive discrete stochastic optimization algorithm is analyzed.