MS&E339/EE377b: Approximate Dynamic Programming

MS&E339/EE377b
Approximate Dynamic Programming
Spring 2003-2004

Course Description

This is an advanced course in dynamic programming, the goal of this course is to help the audience with their research in high dimensional dynamic programming or related topics. The class format will be somewhere between seminars and formal lectures, while the topics will adapted to the interests of audience.

Potential topics include:

Standard dynamic programming algorithms such as value iteration, policy iteration, linear programming
Simulation-based dynamic programming algorithms such as real-time dynamic programming and Q-learning
Value function approximation
Gradient-based policy search methods

Course Information

Class Times and Locations

Lectures: Mondays and Wednesdays 4:00-5:30PM, in Terman 453

Prerequisites/Corequisites

Prerequisite: familiarity with mathematical proofs (e.g., through having taken a 300-level optimization course), one graduate-level probability course, ability to implement algorithmic ideas in code (e.g., in Matlab or Java)

Grading

There will be several homeworks and a final project. In each class two volunteers are needed to scribe the lecture in Latex. The grade will be determined by these three parts.

Instructors

Lecturer: Ben Van Roy

Office: Terman 315
Office hours: Tuesdays 1:30-3:30
Email: bvr@stanford.edu

Course Notes

To scribes: Please follow the format of the first lecture note, and you are welcome to use this style file (provided by Ciamac).
To scribes: Please send the lecture note to Jared (jrhan@stanford.edu) before the next lecture, the note will then be reviewed and posted here.

PDF	Latex	Last Updated
Lecture 1	Lecture 1	04/04
Lecture 2	Lecture 2	04/07
Lecture 3	Lecture 3 Figure	04/13
Lecture 4	Lecture 4 Figure 1 2	04/14
Lecture 5	Lecture 5 Figure	04/18
Lecture 6	Lecture 6 Figure 1 2	04/27
Lecture 7	Lecture 7 Figure 1 2	05/03
Lecture 8	Lecture 8 Figure 1 2	05/12
Lecture 9	Lecture 9	05/12
Lecture 10	Lecture 10 Figure	05/17
Lecture 11	Lecture 11 Figure 1 2	05/18
Lecture 12	Lecture 12 Figure	05/18
Lecture 13	Lecture 13	05/25
Lecture 14	Lecture 14	05/25
Lecture 15	Lecture 15	05/31

Handouts

Learning to Act using Real-Time Dynamic Programming, A. Barto, S. Bradtke, S. Singh
On the Convergence of Stochastic Iterative Dynamic Programming Algorithms, T. Jaakkola, M. Jordan, S. Singh, Neural Computation, vol 6, number 6, pages 1185-1201, 1994.
J. N. Tsitsiklis, "Asynchronous Stochastic Approximation and Q-learning", Machine Learning, 16, 1994, pp. 185-202. (Online version not available)
Stochastic Algorithms, Symmetric Markov Perfect Equilibrium, and the 'Curse' of Dimensionality, A. Pakes, P. McGuire, 2000
Tetris: Experiments with the LP approach to Approximate DP, V. F. Farias, Benjamin Van Roy
Temporal Differences-Based Policy Iteration and Applications in Neuro-Dynamic Programming, D. P. Bertsekas, S. Ioffe, 1996
J. N. Tsitsiklis and B. Van Roy, ``Regression Methods for Pricing Complex American-Style Options,'' IEEE Transactions on Neural Networks, Vol. 12, No. 4 (special issue on computational finance), July 2001, pp. 694-703.
J. N. Tsitsiklis and B. Van Roy, ``Optimal Stopping of Markov Processes: Hilbert Space Theory, Approximation Algorithms, and an Application to Pricing High-Dimensional Financial Derivatives,'' IEEE Transactions on Automatic Control, Vol. 44, No. 10, October 1999, pp. 1840-1851.
J. N. Tsitsiklis and B. Van Roy, ``An Analysis of Temporal-Difference Learning with Function Approximation,'' IEEE Transactions on Automatic Control, Vol. 42, No. 5, May 1997, pp. 674-690.
D. P. de Farias and B. Van Roy, ``The Linear Programming Approach to Approximate Dynamic Programming,'' Operations Research, Vol. 51, No. 6, November-December 2003, pp. 850-865.
D. P. de Farias and B. Van Roy, ``On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming,'' to appear in Mathematics of Operations Research (submitted 2001).
Uncertain Convex Problems: Randomized Solutions and Confidence Levels, G. Calafiore, M. C. Campi
Temporal Difference Learning and TD-Gammon, Gerald Tesauro

Homeworks

PDF	Due Date
Homework 1	04/14
Homework 2	04/26
Homework 3	05/24

Announcements

03/31: The class time has been changed to 4:00-5:30pm on Mondays and Wednesdays.
04/03: Ciamac Moallemi has kindly scribed the first lecture, he has also provided a style file. Thanks to Ciamac!
04/07: Lecture 2 posted, thanks to Vassil Chatalbashev and Randy Cogill.
04/07: Homework 1 posted.
04/12: Lecture 3 posted, thanks to Jose Blanchet and Su-In.
04/14: Lecture 4 posted, thanks to Mark Peters and Michael Rotkowitz.
04/14: Handouts updated.
04/18: Lecture 5 posted, thanks to Rick Johnston and Brad Null.
04/19: Handouts updated.
04/21: Lecture 6 posted, thanks to Lykomidis Mastroleon and Jeffrey Randall Sadowsky.
04/21: Homework 2 posted.
04/21: Handouts updated.
05/03: Lecture 7 posted, thanks to Shahriar Azizpour and Amirpouya Kavousian.
05/05: Handouts updated.
05/11: Handouts updated.
05/12: Lecture 8 posted, thanks to Eymen Errais and Donald Lee.
05/12: Lecture 9 posted, thanks to Yirong Shen and Chih-Han Yu.
05/17: Lecture 10 posted, thanks to Vishal Kasera and Priyendra Deshwal.
05/17: Lecture 11 posted, thanks to Erick Delage and Penka Markova.
05/18: Lecture 12 posted, thanks to Jiarui Han and Ciamac Moallemi.
05/25: Lecture 13 posted, thanks to Mark Peters and Mike Rotkowitz.
05/25: Lecture 14 posted, thanks to Ben.
05/31: Lecture 15 posted, thanks to Erick Delage and Lykomidis Mastroleon.

Web page maintained by Jiarui Han (jrhan@stanford.edu)