OR for the classroom: the linear programming approach to approximate dynamic programming for Markov decision processes

Abstract When the curse of dimensionality prevents an exact solution to a Markov decision process, approximate dynamic programming methods seek approximate solutions. This tutorial introduces the linear programming approach to approximate dynamic programming and three typical solution techniques, which are most suited for settings with a discrete and high-dimensional state space: constraint sampling, constraint generation, and compact reformulation. In our presentation, we assume that the target audience is familiar with the foundations of Markov decision processes, dynamic programming, and linear programming. Even though the ideas we present are generally applicable, we explain the core ideas only in the context of infinite-horizon problems with a discounted-reward criterion. A running example is used throughout to anchor the key ideas and make the methods more accessible.