Stochastic Approximation: Some Theory and an Application

Sameer Kamal School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Monday, 29 Nov 2010 (all day)
A-212 (STCS Seminar Room)
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].


[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
[3] S. Kamal, A vector minmax problem for controlled Markov chains, Preprint available at