Lecture 9 Notes: Markov Rewards and Dynamic Programming

6.262: Discrete Stochastic Processes Lecture 9: Markov rewards and dynamic prog. Outline: • Review plus of eigenvalues and eigenvectors • Rewards for Markov chains • Expected first-passage-times • Aggregate rewards with a final reward • Dynamic programming • Dynamic programming algorithm The determinant of an M by M matrix is given by det A = ! µ ± M " i=1 Ai,µ(i) (1) where the sum is over all permutations µ of the integers 1, . . . , M. If [AT ] is t by t, with   [AT ] [A] =  [0]  [AT R]   [AR] det[A] = det[AT ] det[AR] The reason for this is that for the product in (1) to be nonzero, µ(i) > t whenever i > t, and thus µ(i) ≤ t when i ≤ t. Thus the permutations can be factored into those over 1 to t and those over t+1 to M. det[P − λI] = det[PT − λIt] det[PR − λIr ] det[P − λI] = det[PT − λIt] det[PR − λIr ] The eigenvalues of [P ] are the t eigenvalues of [PT ] and the r eigenvalues of [PR]. If " π is a left eigenvector of [PR], then (0, . . . , 0, π1, . . . , πr ) is a left eigenvector of [P ], i.e.,  (" 0|" π )  [PT ]  [0]  [PT R]   [PR] = λ(" 0|" π) The left eigenvectors of [PT ] are more complicated but not very interesting. Next, assume   [PT ]   [P ] =  [0]   [0] [PT R] [PT R# ] [PR] [0] [0] [PR# ] In the same way as before,        det[P − λI] = det[PT − λIt] det[PR − λIr ] det[PR# − λIr# ] The eigenvalues of [P ] are comprised of the t from [PT ], the r from [PR], and the r# from [PR# ]. If " π is a left eigenvector of [PR], then (" 0, " π, " 0) is a left eigenvector of [P ]. If " π is a left eigenvector of " " [PR# ], then (0, 0, " π ) is a left eigenvector of [P ]. Rewards for Markov chains Suppose that each state i of a Markov chain is associated with a given reward, ri. Letting the rv Xn be the state at time n, the (random) reward at time n is the rv R(Xn) that maps Xn = i into ri for each i. We will be interested only in expected rewards, so that, for example, the expected reward at time n, ) n. given that X0 = i is E [R(Xn)|X0 = i] = j rj Pij The expected aggregate reward over the n steps from m to m + n − 1, conditional on Xm = i is then * + vi(n) = E R(Xm) + · · · + R(Xm+n−1)|Xm = i = ri + ! j vi(n) = ri + Pij rj + · · · + ! j ! j Pij rj + · · · + n−1 Pij rj ! j n−1 Pij rj If the Markov chain is an ergodic unichain, then successive terms of this expression tend to a steady state gain per step, g= ! πj rj , j which is independent of the starting state. Thus vi(n) can be viewed as a transient in i plus ng. The transient is important, and is particularly important if g = 0. Expected first-passage-time Suppose, for some arbitrary unichain, that we want to find the expected number of steps, starting from a given state i until some given recurrent state, say 1, is first entered. Assume i = $ 1. This can be viewed as a reward problem by assigning one unit of reward to each successive state until state 1 is entered. Modify the Markov chain by changing the transition probabilities from state 1 to P11 = 1. We set r1 = 0, so the reward stops when state 1 is entered. $ 1, the For each sample path starting from state i = probability of the initial segment until 1 is entered is unchanged, so the expected first-passage-time is unchanged. The modified Markov chain is now an ergodic unichain with a single recurrent state, i.e., state 1 is a trapping state. $ 1 and let r1 = 0. Let ri = 1 for i = Thus if state 1 is first entered at time $, then the aggregate reward, from 0 to n, is $ for all n ≥ $. The expected first passage time, starting in state i, is vi = limn→∞ vi(n). There is a sneaky way to calculate this for all i. $ 1, assume that X0 = i. There is then For each i = a unit reward at time 0. In addition, given that X1 = j, the remaining expected reward is vj . Thus ) $ 1, with v1 = 0. vi = 1 + j Pij vj for i = The expected first-passage-time to state 1 from state i = $ 1 is then vi = 1 + ! Pij vj with v1 = 0 j This can be expressed in vector form as "v = " r + [P ]"v where " r = (0, 1, 1, . . . , 1), and v1 = 0 and P11 = 1. Note that if "v satisfies "v = " r + [P ]"v , then "v + α"e also satisfies it, so that v1 = 0 is necessary to resolve the ambiguity. Also, since [P ] has 1 as a simple eigenvalue, this equation has a unique solution with v1 = 0. Aggregate rewards with a final reward There are many situations in which we are interested in the aggregate reward over n steps, say time m to m + n − 1, followed by a special final reward uj for Xm+n = j. The flexibility of assigning such a final reward will be particularly valuable in dynamic programming. The aggregate expected reward, including this final reward, is then u) = ri + vi(n, " ! j In vector form, Pij rj + · · · + ! j n−1 Pij rj + ! nu Pij j j r + · · · + [P n−1]" r + [P n]" u "v (n, " u) = " r + [P ]" Dynamic programming Consider a discrete-time situation with a finite set of states, 1, 2, . . . , M, where at each time $, a decision maker can observe the state, say X$ = j and choose one of a finite set of alternatives. Each al(k) ternative k consists of a current reward rj and a (k) set of of transition probabilities {Pj$ ; 1 ≤ $ ≤ M} for going to the next state. 0.99 $ 1! # " ! r1 =0 0.01 0.99 % ! ! " 2! 0.01 (1) r2 =1 Decision 1 0.01 0.99 % ! ! $ 1! # 2 " ! 1 r1 =0 r2(2) =50 Decision 2 For this example, decision 2 seeks instant gratification, whereas decision 1 seeks long term gratification. Assume that this process of random transitions combined with decisions based on the current state starts at time m in some given state and continues until time m + n − 1. After the nth decision, made at time m+n−1, there is a final transition based on that decision. At time m + n, there is a final reward, (u1, . . . , uM) based on the final state. The objective of dynamic programming is both to determine the optimal decision at each time and to determine the expected reward for each starting state and for each number n of steps. As one might suspect, it is best to start with a single step (n = 1) and then proceed to successively more steps. Surprisingly, this is best thought of as starting at the end and working back to the beginning. The algorithm to follow is due to Richard Bellman. Its simplicity is a good example of looking at an important problem at the right time. Given the formulation, anyone could develop the algorithm. The dynamic programming algorithm As suggested, we first consider the optimal expected aggregate reward over a single time period. That is, starting at an arbitrary time m in a given state i, we make a decision, say decision k at time m. (k) This provides a reward ri at time m. Then the k lead to a final selected transition probabilities, Pij expected reward ) k j uj Pij at time m + 1. The decision k is chosen to maximize the corresponding aggregate reward, i.e.,  vi∗(1) = max ri(k) + k ! j  k uj Pij Next consider vi∗(2, " u), i.e., the maximal expected aggregate reward starting at Xm = i with decisions made at times m and m + 1 and a final reward at time m + 2. The key to dynamic programming is that an optimal decision at time m + 1 can be selected based only on the state j at time m + 1. This decision (given Xm+1 = j) is optimal independent of the decision at time m. That is, whatever decision is made at time m, the maximal expected reward0at times m + 1 1and m + 2, (k) given Xm+1 = j, is maxk rj vj∗(1, " u), as just found. + ) (k) $ Pj$ u$ . This is We have just seen that   ! (k) (k) u) = max rj + Pj$ u$ vj∗(1, " k $ is the maximum expected aggregate reward over times m + 1 and m + 2, conditional Xm+1 = j. Thus the maximum expected aggregate reward over m, m + 1, m + 2, conditional on Xm = i, is 0 1 ! (k) (k) ∗ ∗ vi (2, " u) = max ri + j Pij vj (1, " u) k This same procedure can be used to find the optimal policy and optimal expected reward for n = 3, 0 1 ! (k) (k) ∗ ∗ vi (3, " u) = max ri + j Pij vj (2, " u) k This solution shows how to choose the optimal decision at time m and finds the optimal aggregate expected reward, but is based on first finding the optimal solution for n = 2. In general, 0 1 ! (k) (k) ∗ ∗ vi (n, " u) = max ri + j Pij vj (n−1, " u) k For any given n, then, the algorithm calculates vj∗(m, " u) for all states j and all m ≤ n, starting at m = 1. This is the dynamic programming algorithm.