Index

Lecture series are sponsored by

Prof. Peter Bartlett (UC Berkeley)

Abstract: Many problems of decision making under uncertainty can be formulated as sequential decision problems in which a strategy's current state and choice of action determine its loss and next state, and the aim is to choose actions so as to minimize the sum of losses incurred. We consider three problems of this kind: Markov decision processes with adversarially chosen transition and loss structures; policy optimization for large scale Markov decision processes; and linear tracking problems with adversarially chosen quadratic loss functions.The key challenge in these problems is to develop methods that are effective with large state spaces, yet computationally efficient.We aim to incur a total loss that is not too much worse than the best in some comparison class. Since optimality with respect to the class of all policies is unachievable in general for large scale problems,we consider more restricted comparison classes. We present algorithms and optimal excess loss bounds for these three problems. We show situations where these algorithms are computationally efficient,and others where hardness results suggest that no algorithm is computationally efficient. Joint work with Yasin Abbasi-Yadkori, Varun Kanade, Alan Malek,Yevgeny Seldin and Csaba Szepesvari.

Short Bio: Peter Bartlett is a professor in Computer Science and Statistics at UC Berkeley and professor in Mathematics at the QueenslandUniversity of Technology. His research interests include machine learning, statistical learning theory, and adaptive control.He was awarded the Malcolm McIntosh Prize for Physical Scientist of the Year in Australia in 2001, was an IMS Medallion Lecturer in 2008, and is an Australian Laureate Fellow and a Fellow of theIMS.