MDP Algorithms

Consider the below MDP$.$ There is no discounting $(=1).$

$($a$)$ Give the results of the first four iterations of Value iteration $($i$.$e$.$ compute $V_0,V_1,V_2,$ and $V_3$ for

each of the six states$).$

$($b$)$ Give the results of the first four iterations of Policy Evaluation for the policy that always goes

right $($i$.$e$.$ compute $V_0^{},V_1^{},V_2^{},$ and $V_3^{}$ for each of the six states$).$

$($c$)$ Suppose we perform policy extraction using the $V_3^{}$ you calculated in the previous part. What is

the new policy that results?