Handbook in Monte Carlo Simulation: Applications in Financial Engineering, Risk Management, and Economics

10.7 Numerical dynamic programming

The decomposition principle behind dynamic programming is extremely powerful, but it requires a set of value functions, which are infinite-dimensional objects when the state space is continuous. Solving a sequence of functional equations involves a mix of numerical methods for integration, optimization, function approximation, and equation solving. In this section we illustrate the building blocks of the mix, by applying dynamic programming to three examples. In Section 10.7.1 we deal with a deterministic budget allocation problem with a continuous-state space. The problem structure allows for an analytical solution, which we use as a benchmark for a numerical method based on the discretization of the state space and the approximation of value functions by cubic splines. Then, in Section 10.7.2 we tackle a simple infinite-horizon, stochastic problem. The example is very simple, as it features a discrete state space and a discrete set of decisions, nevertheless it illustrates the concept of value iteration, which is a key ingredient in approximate dynamic programming. Finally, we tackle a simple consumption–saving problem with income uncertainty in Section 10.7.3. Even though quite simplified with respect to real-life problems, this example is challenging, as it involves mixed states, both continuous and discrete, continuous disturbances, as well as continuous decisions.

10.7.1 APPROXIMATING THE VALUE FUNCTION: A DETERMINISTIC EXAMPLE

Let us consider ...