Dynamic Programming & Stochastic Control

Course Description

The course covers the basic models and solution techniques for problems of sequential decision making under uncertainty (stochastic control). We start with dynamic models of random phenomena, and in particular, the most popular classes of such models: Markov chains and Markov decision processes. We then consider optimal control of a dynamical system over both a finite and an infinite number of stages. We will also discuss approximation methods for problems involving large state spaces. This includes systems with finite or infinite state spaces, as well as perfectly or imperfectly observed systems. Applications of dynamic programming in a variety of fields will be covered in recitations.

Content

The following topics will tentatively be covered in the course:

  • Discrete-time Markov chains

    • Basic definitions, transition probabilities

    • Classification of states

    • Stationary and limiting distributions, convergence to equilibrium

    • Hitting times and absorption probabilities

    • Strong Markov property, law of large numbers for Markov chains

    • Markov chain Monte Carlo methods

  • Dynamic programming and stochastic control

    • Basic principles

    • Linear systems and quadratic cost, Ricatti equation

    • Finite-horizon and infinite horizon problems

    • Optimal stopping

    • Correlated disturbances, state augmentation

    • Suboptimal control and approximate dynamic programming methods

    • Incomplete information

Keywords

Markov chains, Markov decision processes, dynamic programming, optimal control

Prerequisites

Solid knowledge of undergraduate probability, especially conditional distributions and expectations, and Markov chains. Mathematical maturity and the ability to write down precise and rigorous arguments are also important. A class in analysis will be helpful, although this prerequisite will not be strictly enforced.

References