Tata Institute of Fundamental Research
Stochastic Approximation: Some Theory and an Application
Synopsis Seminar
Speaker:
Sameer Kamal
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Monday, 29 Nov 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Sameer Kamal School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Monday, 29 Nov 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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
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