Unable to understand the second iteration update in value iteration algorithm for solving MDP

Question

I am trying to understand the value iteration method for Markov Decision Process(MDP) and I was referring to UC Berkeley's slides titled Markov Decision Processes and Exact Solution Methods

On slide no. 9, we start with the first step :

Ok! So, we have the information about the transition function (described elaborately in slide no. 5 as well), the resting reward is 0 and discount of 0.9.

Using this, I am able to compute the utility value of the cell left to terminal state with R = +1 (Green cell). The action that is going to be most rewarding at this cell is moving forward, so putting the values in the equation as:

$$0.0 + 0.9 (0.8*1 + 0.1*0 + 0.1*0) =0.72$$

which seems to be correct:

Now, using the same algorithm I am able to compute the value of the cells adjacent to this newly obtained utility cell value. However, I really do not know how did they update the value from

0.72 -> 0.78

in the next slide:

I have tried searching at various sites and seen some videos but most of them stop at the first iteration assuming the next step is the same, as it is a recursive equation (And it should have been so!), but I am stuck at this!

Answer 1

First thing to know is that, in this case, values for the gridworld in new iteration are completely calculated with respect to the old values from the previous iteration. Value of $0.78$ is got like this:

$0.9 \cdot (0.8 \cdot 1 + 0.1 \cdot 0.72 + 0.1 \cdot 0) = 0.7848 \approx 0.78$

term $0.8 \cdot 1$ is for going to the right with probability of $0.8$ and getting reward of $1$.

term $0.1 \cdot 0.72$ is for going up with probability of $0.1$, we hit the wall and stay in the same field which value is $0.72$ (from previous iteration)

term $0.1 \cdot 0$ is for going down with probability of $0.1$, even though value of that field in the image is $0.43$ we take the value from previous iteration which is $0$.

Answer 2

In second iteration,

using the bellman equation,

for (3,3), we got 0.8[0+(0.9)(1)]+0.1[0+(0.9)(0.72)]+0.1[0+(0.9)(0)] = 0.78

for (3,2), we got 0.8[0 + 0.9(0.72)] + 0.1[0 + 0.9(0)] + 0.1[0 + 0.9(-1)] = 0.43

for (2,3), we got 0.8[0 + 0.9(0.72)] + 0.1[0 + 0.9(0)] + 0.1[0 + 0.9(0)] = 0.52