\fPart I a) There are two state's that can represent Jamie's Car: : = 0 : = 1 There are five possible actions ( = 5) that Jamie's car can take: Decision Action State Cost 1 Park in one space 0 01 = 0 2 Park in two spaces 0 02 = 4.5* 3 Park in lot 0 03 = 5 4 Have car repaired 1 04 = 50 5 Drive with dented car 1 05 = 9 Decisions 1-3 start with initial state = 0 (assuming Jamie's car is not dented.) Decisions 4-5 are taken only when there is a dent and correspond to state = 1. *For example, in decision 2, the () = ( ) ( ) 3 = ( ) ($15) 10 = $4.5 b) Assuming there is not a dent (initially) and Jamie decides to park in the lot (Decision 3), then there is no chance of a dent and State 1 ( = 1; ) is never entered. This implies there are five stationary deterministic policies to consider: (1 ) (2 ) (3 ) (4 ) (5 ) 0 1 1 2 2 3 1 4 5 4 5 There are only 2 states and the long-term probabilities are denoted by: 0 1. For each policy, we can determine a one-step transition matrix and expected average cost: = 0 ( ) 0 + 1 ( )1 ; = 1,2,3,4,5 Policy 1 Transition Matrix [0.9 0.1 1 0] Expected Average Cost 1 = 501 2 [0.9 0.1 1 0] 3 [0.98 0.02 1 0] 3 + 4.50 = 501 4 [0.98 0.02 0 1] 4 + 4.50 = 91 2 = 91 [1 0 ] 5 5 = 50 The only difference between 1 and 2 is that in 2 , Jamie decides to drive with the dent and so, once the car reaches state = 1, it stays there. Expressed as: (+1 = 0 | = 1) = 0 and (+1 = 1 | = 1) = 1. The opposite holds true for 1 . c) For each policy, steady-state probability can be found by raising the one-step transition matrix to a large number: 1128 = [0.9 0.1 1 0 ]128 = [0.909 0.91 0.909 0.091 ] 0 = 0.909, 1 = 0.091 Repeating the process for the other policies: Policy Probabilities Expected Long-Term Cost 0 , 1 1 0.909 , 0.091 1 = 501 (0.091) = 4.55 2 0 ,1 2 = 91 (1) = 9 3 0.98 , 0.02 3 + 4.50 (0.98) = 501 (0.02) = 5.41 4 0 ,1 4 + 4.50 (0) = 91 (1) = 9 5 1 ,0 5 = 50 (1) = 5 Optimal policy is 1 with minimum cost of $4.55. Jamie's best course of action is to park the car on the street in one space and repair the car if dented