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

On slide no.9, we start with the first step : enter image description here

Ok! So, we have the information about the transition function (desribed 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: enter image description here

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: enter image description here

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


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.