References and Literature
At some level the main idea of dynamic programming, the Principle of Optimality, is a straightforward concept. Nevertheless, it is also a powerful concept and this will be best appreciated once a number of its implications are derived.
The basic ideas of dynamic programming, including the Principle of Optimality, were introduced by Richard Bellman, in his famous monograph, Bellman (1957). Most of the basic results about finite and infinitedimensional dynamic programming problems are contained in this monograph. Interestingly, many of these ideas were anticipated by Shapley (1953) in his study of stochastic games. Shapley analyzed the characterization of equilibrium points of zero-sum stochastic games. His formulation of these games anticipated what later became known as Markov Decision Problems, which are closely related to dynamic programming problems. Moreover, Shapley used ideas similar to the Principle of Optimality and the Contraction Mapping Theorem to show the existence of a unique solution to these dynamic zero-sum games. A more detailed treatment of Markov Decision Problems can be found in Puterman (1994), who also discusses the relationship between Shapley’s (1953) work, the general theory of Markov Decision Problems and dynamic programming.To the best of my knowledge, Karlin (1955) was the first one to provide a simple formal proof of the Principle of Optimality, which is similar to the one presented here. Denardo (1967) developed the use of the contraction mappings in the theory of dynamic programming. Howard (1960) contains a more detailed analysis of discounted stochastic dynamic programming problems. Blackwell (1965) introduced the Blackwell’s sufficient conditions for a contraction mapping and applied them in the context of stochastic discounted dynamic programming problems. The result on the differentiability of the value function was first proved in Benveniste and Scheinkman (1979).
The most complete treatment of discounted dynamic programming problems is in Stokey, Lucas and Prescott (1989). My treatment here is heavily influenced by theirs and borrows much from their insights. Relative to their treatment, some of the proofs have been simplified 253
and we have limited the analysis to the case with compact sets and bounded payoff functions. The reader can find generalizations of Theorems 6.1-6.6 to certain problems with unbounded returns and choice sets in Stokey, Lucas and Prescott (1989), Chapter 4 for the deterministic case, and the equivalent theorems for stochastic dynamic programming problems in their Chapter 9.
A much simpler but insightful exposition of dynamic programming is in Sundaram (1996), which also has a proof of Proposition 6.1 similar to the one given here.
Some useful references on the Contraction Mapping Theorem and its applications include Denardo (1967), Kolmogorov and Fomin (1970), Kreyszig (1978) and the eminently readable Bryant (1985), which contains applications of the Contraction Mapping Theorem to prove existence and uniqueness of solutions to differential equations and the Implicit Function Theorem.
Another excellent reference for applications of dynamic programming to economics problems is Ljungqvist and Sargent (2005), which also gives a more informal introduction to the main results of dynamic programming.
6.10.