Q: Trouble understanding value iteration I have trouble understanding how the value iteration algorithm for
MDP:s work. I'm trying to follow the canonical grid world example
(slide 17),
but I don't get the correct results. Here's my work:
Initially I set the value function to 0 everywhere. So the matrix
representation of each state's utility becomes:
$$
V_0 = \begin{pmatrix}
0 & 0 & 0 & 0\\
0 & -999 & 0 & 0\\
0 & 0 & 0 & 0
\end{pmatrix}
$$
$-999$ is arbitrarily choosen as a dummy value for the square that
can't be entered. Then I use the Bellman update to calculate values
for the next iteration,
$$
V_{t+1}(s) = R(s) + \max_a\sum_{s'}P(s'|a, s)V_t(s'),
$$
where $P(s'|a, s)$ is the probability of reaching state $s'$ given
current state $s$ and action $a$. Using the values found in the PDF,
the utility for square at row 1 column 4 at time step 1 is calculated
to
$$
V_1((1, 4)) = 1 + \max_a\sum_{s'}P(s'|a, (1,4))V_0(s') = 1.
$$
$V_1((2, 4)) = -1$ is calculated similarily, yielding the matrix
$$
V_1 = \begin{pmatrix}
0 & 0 & 0 & 1\\
0 & -999 & 0 & -1\\
0 & 0 & 0 & 0
\end{pmatrix}.
$$
I again use the Bellman update to calculate $V_2((1,4))$
$$
V_2((1,4)) = R((1,4)) + \max_a\sum_{s'}P(s'|a, (1,4))V_1(s')\\
= 1 + \max_a\sum_{s'}P(s'|a, (1,4))V_1(s').
$$
$a = \mathrm{n}$ (as in go "north") is obviously the action that maximizes the
expression. Then $P((1,4)|\mathrm{n},(1,4)) = 0.9$ and
$P((1,3)|\mathrm{n},(1,4)) = 0.1$ and I get:
$$
V_2((1,4)) = 1 + P((1,4)|\mathrm{n}, (1,4))V_1((1,4)) + P((1,3)|\mathrm{n}, (1,4))V_1((1,3))\\
= 1 + 0.9\cdot1 + 0.1\cdot0 = 1.9
$$
But this result is not correct the value should remain at 1. What am I doing wrong?

A: You are missing how the episode terminates, and possible confusing the difference between reward granted from arriving in a state with reward granted when leaving a state (or other ways of assigning reward).
Working backwards from the correct answers in the slides you linked, it looks like a grid world, where either: 


*

*Reward $R(s)$ is granted for leaving a state $s$, with the +1, -1 reward values associated with the squares as shown (this happens to then equal their utility as I will explain later). In addition there is a not-shown terminal state which is reached by taking any action in either of the squares that grant reward. A terminal state has a fixed value of 0.

*Reward $R(s)$ is granted for entering a state $s$. Separate to this, the +1, -1 rewards are written on the terminal states to show them as targets, in the same place as the utility is written on other states. It might be better to show green and red colours or some other indicator of good vs bad terminal state instead in this case to avoid confusion between rewards and utilities.
You can also take either interpretation and make a consistent answer with it. However, I am assuming the first option, reward is granted for leaving a state, in the rest of this answer.
The first thing this means is that your assertion:

$a = \mathrm{n}$ (as in go "north") is obviously the action that maximizes the expression

is not correct. It doesn't matter what the action is, the state $(1,4)$ always transitions to state $T$ (the terminal state) granting reward $1$, regardless of the action. In addition $V(T) = 0$ by definition, because no future reward is possible for state $T$.
This means that your update for $(1,4)$ is always the same:
$$V_{n+1}((1,4) = R((1,4)) + \max_a\sum_{s'}P(s'|a, (1,4))V_n(s')\\
= 1 + V_n(T) = 1$$
Note your original maths would be correct if the episode never terminated - in which case it should be possible to get a high expected long-term utility by moving to $(1,4)$ and continuing to move North from it. However, that is clearly not the intent of the presented material. They give the expected converged values later in the document, and they are consistent with this view.
Once you allow for the fixed utility of $0$ for terminal states, you should find that updates to all the other states converge to the values you see in the document, using the update mechanism that you are applying.
