3. For the optimal actions of the gambler MDP problem (Example 4.3 on page 84 of Sutton's text, worked out in class) explain why at states 25 and 50 the optimal action is to bet everything, and why at 75 , the optimal action is to bet 25 , while at states immediately next to these states the actions are much smaller. 4. Consider a directed network G=(V,E,d) with V the set of nodes or vertices, E the set of edges or links (of the form (v1,v2) where v1,v2V are not equal), and d:ER+is a nonnegative real-valued function defined on each edge (vi,vj), where d(vi,vj) indicates the "length" of edge (vi,vj). (If there is no edge from vi to vj set d(vi,vj)=.) We wish to compute all shortest paths and their values among all pairs of distinct vertices vi,vj. Suppose the number of vertices V=n and the number of edges E=m. Represent each such graph by a nn matrix D where rows and columns are indexed by vertices. The i,j entry of D is defined as follows: Di,j=0d(vi,vj)ifi=jifthereisanedgefromvitovjifthereisnoedgefromvitovj 4. Consider a directed network G=(V,E,d) with V the set of nodes or vertices, E the set of edges or links (of the form (v1,v2) where v1,v2V are not equal), and d:ER+is a nonnegative real-valued function defined on each edge (vi,vj), where d(vi,vj) indicates the "length" of edge (vi,vj). (If there is no edge from vi to vj set d(vi,vj)=.) We wish to compute all shortest paths and their values among all pairs of distinct vertices vi,vj. Suppose the number of vertices V=n and the number of edges E=m. Represent each such graph by a nn matrix D where rows and columns are indexed by vertices. The i,j entry of D is defined as follows: Di,j=0d(vi,vj)ifi=jifthereisanedgefromvitovjifthereisnoedgefromvitovj 4a) Define D as the matrix whose i,j contains di,j, the shortest distance from vertex vi to vertex vj going through directed edges in between. The following Bellman-like optimality relationship holds: di,j=min(di,+d,j)for1i,j,n Show that this relationship is correct, and explain how prerequisites for dynamic programming lead us to this relation. b) Define di,j(k) as the shortest distance from vi to vj that goes through at most k edges. Define the nn matrix D(k) to have di,j(k) as its i,j entry. What are D(0) and D(1) matrices? 4c) For two arbitrary nn matrices A, B define the min-sum product of AB, by using the ordinary matrix multiplication formula, but replacing ' + ' with that is xy=min(x,y), and multiplication by '+': (AB)i,j=(Ai1+B1j)(Ai2+B2j)(Ain+Bnj) Write the Bellman optimality relation in Q4a) in matrix form using the ' ' operation. d) Use the matrices D(k) step by step for k=0,1, and design a dynamic programming algorithm with them that converges to D. Define Dk=DDDD, that is, D is multiplied k times by itself. Show that Dk=D(k) as defined in Q4b, and that D(n1)=D. Explain how this affects your iterative algorithm for computing D. Write a short Python function to compute all shortest path matrix D given the vertex-distance matrix D of a graph. 4e) Let P be an nn matrix whose i,j entry Pi,j= if in the shortest path from vi to vj the immediate vertex before vj is the vertex v. (The matrix P is called the predecessor matrix.) - Define P(k) as the matrix whose i,j entry is , if the shortest path with at most k edges from vi to vj goes through v right before getting to vj, that is v is the immediate predecessor of vj in this path. Give an algorithm for computing P(k) while you are computing D(k). Adjust your Python script above to also output P. - Once you know both D and P how would you recover the actual shortest path, that is, given vi and vj output the sequence of vertices you traverse starting from vi to reach vj, following the shortest path between them