Stochastic Approximation: Some Theory and an Application

We discuss a vector minmax problem for controlled Markov chains [3]. The problem of controlling a finite state Markov chain in the presence of an adversary so as to ensure desired performance levels for a vector of objectives is cast in the framework of Blackwell approachability. Relying on an elementary two time scale construction a control scheme is proposed which ensures almost sure convergence to the desired set regardless of the adversarial actions. This problem serves as an example of stochastic approximation. We conclude with some general theoretical results in stochastic approximation. These relate to stability [2] and sample complexity [1].

References

[1] S. Kamal, On the convergence, lock-in probability, and sample complexity of stochastic approximation, SIAM Journal on Control and Optimization, Volume 48, Number 8, October 2010, pp. 5178-5192.
[2] S. Kamal, Stabilization of stochastic approximation by step size adaptation, Preprint available at http://arxiv.org/abs/1007.4689
[3] S. Kamal, A vector minmax problem for controlled Markov chains, Preprint available at http://arxiv.org/abs/1011.0675