14.451 Lecture Notes 3

14.451 Lecture Notes 3 Fall 2009 Showing that T is a contraction 1 1.1 Blackwell’s su¢ cient conditions One important step in applying our argument to the map T is to show that T is a contraction. Let C (X) be the space of bounded functions on X let k:k be the sup norm. Take any map T : C (X) ! C (X) : (This does not need to come from any optimization problem.) Assume: 1. T is monotone, if f; g 2 C (X) and f (x) T f (x) T g (x) for all x 2 X. g (x) for all x 2 X, then 2. T satis…es a “discounting”property: there is a 2 (0; 1) such that for any a 0 and any g 2 C (X) the function f (x) = g (x) + a satis…es T (f (x) g (x)) a: Then T is a contraction. To prove this let a = sup jf (x) g (x)j = kf x2X gk : Suppose without loss of generality that sup jT f (x) T g (x)j = sup (T f (x) x2X T g (x)) x2X (if this does not hold then it must be sup jT f (x) T g (x)j = sup (T g (x) x2X T f (x)) x2X and the same argument works with the roles of f and g reversed). Then let h (x) = g (x) + a. We have h (x) f (x) for all x by de…nition. So T f (x) T g (x) T h (x) 1 T g (x) from monotonicity and T h (x) T g (x) a from discounting. Combining them we have T f (x) T g (x) a which implies kT f T gk = sup jT f (x) T g (x)j = sup (T f (x) 1.2 Applying Blackwell’s conditions x2X T g (x)) x2X a = kf gk : Now we go back to our dynamic programming problem and show that T , de…ned as T f (x) = max F (x; y) + f (y) y2 (x) is indeed a contraction. (Here we assume we already know that T maps bounded continuous functions into bounded continuous functions). To apply Blackwell’s theorem we need to check conditions 1 and 2. 1. To see that T is monotone suppose f g. Take any x 2 X and suppose y 0 2 arg max F (x; y) + g (y) : y2 (x) Then T f (x) = max F (x; y) + f (y) y2 (x) F (x; y 0 ) + f (y 0 ) F (x; y 0 ) + g (y 0 ) = T g (x) : Since this holds for all x 2 X, we are done. 2. So see that T satis…es discounting notice that for any a g (x) + a T f (x) = max F (x; y) + y2 (x) = max F (x; y) + g (y) + a y2 (x) = T g (x) + a: So discounting applies (with (g (y) + a) = = ). 2 0 is f (x) = 2 Inductive arguments Using induction we can prove properties of the value function. The general idea is to use the fact that our …xed point V is the limit of T n f0 . So if we start from a f0 2 D (f0 satis…es D) and can prove that T f 2 D if f 2 D (T preserves property D), then provided that D is a closed subset of our original metric space C (X) then V 2 D: 2.1 Proving that V is monotone Make all assumptions of bounded dynamic programming plus: F (x; y) is increasing in its …rst argument; (x) is monotone in the sense that (x0 ) (x00 ) if x00 x0 : Then V (x) is increasing in x. Proof. We need to prove our induction step: T f is increasing if f is increasing. We actually prove a stronger version: T f is increasing if f is non-decreasing. Pick an x0 ; x00 2 X with x00 (1) x0 (with at least one >). Choose a y 0 2 arg max0 F (x0 ; y) + f (y) : y2 (x ) Then y 0 2 (x00 ) by monotonicity of , so T f (x00 ) = > max F (x00 ; y) + f (y) y2 (x00 ) F (x00 ; y 0 ) + f (y) > F (x0 ; y 0 ) + f (y) = T f (x0 ) ; where the last inequality comes from the fact that F is increasing. The space of strictly increasing functions is not closed, but the space of non-decreasing functions is closed (and is the closure of the space of increasing functions). So since V is the limit of T n f0 , we have V non-decreasing. Moreover V = TV and V is non-decreasing. So (1) implies that V is increasing. QED. 3 2.2 Proving that V is concave Same idea: move in the space of concave functions. Now the extra assumptions we need are: F (x; y) is concave; is a convex in the sense that if y 0 2 y 0 + (1 ) y 00 2 (x0 ) and y 00 2 ( x0 + (1 ) x00 ) for all (x00 ) then 2 [0; 1] : Then V (x) is concave. Proof. Again we need our inductive step. Suppose f (x) is concave. Take any x0 ; x00 2 X and y0 y Take any 00 2 arg max0 F (x0 ; y) + f (y) y2 (x ) 2 arg max00 F (x00 ; y) + f (y) : y2 (x ) 2 [0; 1] and let x000 = x0 + (1 y 000 = y 0 + (1 ) x00 . Then ) y 00 2 (x000 ) by convexity of . So max F (x000 ; y) + f (y) y2 (x000 ) F (x000 ; y 000 ) + f (y 000 ) (F (x0 ; y 0 ) + f (y 0 )) + (1 ) (F (x00 ; y 00 ) + f (y 00 )) where the last inequality follows from the concavity of F and f . So we have T f (x000 ) T f (x0 ) + (1 ) T f (x00 ) ; showing that T f is concave. Since the space of concave functions is closed, we can start at any f0 concave and we end up at V concave. Again, if needed we can strengthen to strict concavity by making an extra step (like going from weak to strong monotonicity). QED 4