Proofs of the Stochastic Dynamic Programming Theorems*
This section provides proofs for the main theorems provided in the previous section, Theorems 16.1-16.3. The proofs for theorems 16.5-16.7. are left as exercises.
621
and
The following lemma is as straightforward generalization of Lemma 6.1 in 6
note that U continuous over X ?X ?Z (with the finite set Z endowed with the natural discrete topology).
Then by the same argument as in the proof of Theorem 6.1, Assumptions 16.1 and 16.2 imply that the objective function in Problem B1 is continuous in the product topology (recall Theorem A.11) and the constraint set is compact (this again follows from Theorem A.12 and Fact A.2 in Appendix Chapter A as in the proof of Theorem 6.1). Therefore, by Weierstrass’s Theorem, Theorem A.9, a solution to this maximization problem exists and
loss of generality taking z = zι,
contradicting (16.14) and completing the induction step, which establishes that
attains the supremum starting from x* [zt] and any z (t + 1) ∈ Z.
Equation (16.12) then implies that
establishing (16.6) and thus completing the proof of the first part of the theorem.
Now suppose that (16.6) holds for x* ∈Φ(x (0),z (0)).
Then substituting repeatedly for
we obtain 
thus x* attains the optimal value in Problem B1. This completes the proof of the second part of the theorem. ?
Proof of Theorem 16.3. Consider Problem B2. In view of Assumptions 16.1 and 
because they are continuous and both X and Z are compact.
Now define the operator T 
Suppose that V (x, z) is continuous and bounded. Then
is also continuous and
bounded, since it is simply given by
a continuous function over a compact set, and by Weierstrass’s Theorem, it has a solution. Consequently, T is well defined. It can be verified straightforwardly that it satisfies Blackwell’s sufficient conditions for a contraction (Theorem 6.9 from Chapter 6). There-
Finally, the proofs of Theorems 16.4-16.6 are similar to those of Theorems 6.4-6.6 from Chapter 6, and are left as exercises (see Exercises 16.3-16.5). The proof of Theorem 16.7 is similar to 16.5 and is left to Exercise 16.6.
16.3.