Stochastic dynamic programming (Spring 2004)

This is part (8 lectures) of an LNMB course and is lectured in Utrecht for PhD student of all Dutch universities.

Time: 12 Monday mornings (February 16 - April 5; April 19 - May 10.
Location: Room 107A, Buys Ballot Laboratorium, Princetonlaan 4, The Uithof, Utrecht.
Lecturers : S.C. Borst (CWI and Eindhoven University of Technology), prof.dr. L.C.M.
Kallenberg (LNMB and Leiden University) and prof.dr. G.M. Koole (Free University Amsterdam).

Course description:

Stochastic dynamic programming
The theory of Markov decision processes (MPDs) - also known under several other names as sequential stochastic optimization, stochastic control or stochastic dynamic programming, studies sequential optimization of stochastic systems whose transition mechanism can be controlled over time. Each control policy defines a stochastic process and values of objective functions associated with this process. The goal is to select an optimal control policy. In real life, decisions that are made usually have two types of impact: they cost or save time or money, or other resources, as well as they have impact on the future, by influencing the dynamics. In many situations, decisions with the largest immediate profit may not be good in view of future rewards. MPDs model this paradigm and provide results on the structure and existence of good policies and on methods for the computation of optimal policies.

Control of queues
The performance of queueing systems can be controlled by strategies for the arrivals and the servers, e.g. how are customers at arrival be assigned to one of a number of servers; how are one or more servers be assigned to different customer classes of queues? Depending on the objective function we can compare several strategies and look for an optimal strategy. In some cases the optimal strategy has a nice structure, e.g. send an arrival to the server with the shortest queue.

Part 1 (Control of queues I; Borst)
- Stochastic majorization, coupling techniques.
- Routing to parallel queues, load balancing, scheduling in multi-class queues, priority strategies.
- Achievable performance region, conservation laws, performance bounds, asymptotically optimal policies.
- Basic knowledge of probability, stochastic processes as well as queueing theory ( in particular stochastic variables, probability distributions, expectation, M/G1 queue).
Some useful background material:
- R. Nelson; Probability, stochastic processes and queueing theory, Springer, 1995 (Chapters 2, 4, 5, 7).
- S.M. Ross, Introduction to Probability Models, Academic Press, 1989 (Chapters 1 - 8).
- S.M. Ross, Stochastic Processes, Wiley, 1996 (Chapters 1 - 5, 9).
- R.W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice Hall, 1989 (Chapters 1 - 5, 10).

Lecture notes will be provided.

Take home problems.


Part 2 (Control of queues II; Koole)
In this part of the course we focus on the control of queueing systems. We apply the theory to several controlled queueing models. We also pay attention to the curse of dimensionality and its implications

Part 2 of this course.
Lecture notes will be privided.

Take home problems.

Part 3 (Stochastic dynamic programming; Kallenberg)
- Introduction of the model, policies and optimality criteria; the finite horizon.
- Discounted rewards (optimality equation; bounds on the value vector; solution methods).
- Average and more sensitive rewards (laurent expansion; solution methods).
- Application (gambling; optimal stopping; replacement; mullti-armed bandits).

-Elementary knowledge of linear programming (e.g. K.G. Murthy, Linear programming, Wiley, 1983).
- Elementary knowledge of probability theory (e.g. S.M. Ross, A first course in probability, Macmillan, New York, 1976).
- Elementary knowledge of (numerical) analysis (e.g. Banach space; contracting mappings; Newton's method; Laurent series).

Lecture notes are available as pdf file: Survey SDP
The 110 slides of the lectures are available as pdf file: Sheets SDP 2004

Take home problems.
The exercises (deadline June 15) are available as pdf file: Exercises SDP 2004


Addresses of the lecturers: S.C. Borst
Centre for Mathematics and Computer Science
P.O. Box 94079
1090 GB Amsterdam
Phone: 020- 5924205

Prof.dr. L.C.M. Kallenberg
Mathematical Institute
Leiden University
P.O. Box 9512
2300 RA Leiden
Phone: 071 - 5277130

Prof.dr. G.M. Koole
Free University Amsterdam
Faculty of Mathematics and Computer Science
De Boelelaan 1081a
1081 HV Amsterdam
Phone: 020 - 4447755