Computation and Dynamic Programming
Hüseyin Topaloğlu · Wiley Encyclopedia of Operations Research and Management Science · 2011
Abstract Dynamic programming provides a structured framework for solving sequential decision‐making problems under uncertainty, but its computational appeal has traditionally been limited when dealing with problems with large state and action spaces. In this article, we describe a variety of methods that are targeted towards alleviating the computational difficulties associated with dynamic programming. The methods that we describe here are simulation based and model free methods, the linear programming approach to approximate dynamic programming, approximate policy iteration, rollout policies, and state aggregation. An important aspect of the methods that we describe in this article is that they use parsimoniously parameterized value function approximations to ensure that the approximations can be stored in a tractable fashion and they utilize simulation to avoid computing expectations explicitly.