An Introduction to Approximate Dynamic Programming

Markov decision processes (MDPs) are an elegant and exact way to formulate dynamic decision problems. The solution methods for MDPs, however, suffer from the curse of dimensionality. As a consequence, most problems of realistic size are too large to solve as a MDP. The linear programming approach to approximate dynamic programming is a relatively new technique in operations research. The underlying idea is to approximate the solution of a MDP in order to obtain bounds and theoretically founded heuristics for the problem at hand. In this talk, I will introduce the main ideas of ADP and illustrate its usefulness in a variety of examples including revenue management and patient admission in healthcare.