Dynamic Programming and Stochastic Control

Dynamic Programming and Stochastic Control

Label correcting methods for shortest paths. See lecture 4 for more information. (Figure by MIT OpenCourseWare, adapted from course notes by Prof. Dimitri Bertsekas.)

Course Highlights

This course features a complete set of lecture notes, as well as assignments andexams with solutions.

Course Description

This course covers the basic models and solution techniques for problems of sequential decision making under uncertainty (stochastic control). We will consider optimal control of a dynamical system over both a finite and an infinite number of stages (finite and infinite horizon). We will also discuss some approximation methods for problems involving large state spaces. Applications of dynamic programming in a variety of fields will be covered in recitations.

Lecture Notes

This section includes the complete lecture notes from Fall 2008, based on the third edition of the course textbook, both as one file and broken down by session. For reference, it also includes the complete lecture notes from Fall 2003, based on the second edition of the textbook.

Complete Lecture Slides

Complete slides, Fall 2008 (PDF - 2.4 MB)

Complete slides, Fall 2003 (PDF - 1.9 MB)

Lecture Slides by Session

SES #	TOPICS
1	Introduction to dynamic programming; examples and formulation (PDF)
2	The dynamic programming algorithm (PDF)
3	Deterministic systems and the shortest path problem (PDF)
4	Shortest path algorithms (PDF)
5	Deterministic continuous-time optimal control (PDF)
6	Stopping and scheduling problems (PDF)
7	Linear systems with quadratic costs and inventory control (PDF)
8	Problems with imperfect state information (PDF)
9	Sufficient statistics (PDF)
10	Suboptimal control (PDF)
11	Rollout algorithms (PDF)
12	More on suboptimal control (PDF)
13	Infinite horizon I: stochastic shortest path problems (PDF)
14	Infinite horizon II: discounted problems (PDF)
15	Infinite horizon III: average cost problems (PDF)
16	Semi-Markov problems (PDF)
17	Infinite horizon: discounted problems I (PDF)
18	Infinite horizon: discounted problems II (PDF)
	Midterm
19	Stochastic shortest path problems (PDF)
20	Overview of main approaches in approximate dynamic programming (PDF) Detailed outline for approximate dynamic programming, lectures 20-25 (PDF)
21	Cost approximation: discounted cost (PDF)
22	Projected equation methods (PDF)
23	More on projected equations: Q-learning (PDF)
24	Extensions to stochastic shortest path and average cost (PDF)
25	Gradient methods for approximation in policy space (PDF)
26	Project presentations I
27	Project presentations II