Markov decision processes, contractions and value iteration I am reviewing Markov decision processes (MDP) and there is something I am missing with respect to the contraction argument. I am pretty sure it is a silly mistake somewhere (maybe computational), but anyways, I cannot figure it out. Here it goes.

Consider a simple MDP with two states and two actions defined as follows.

$$ r(s,a) = \begin{pmatrix} 1 &amp; 1 \\ 1 &amp; 1 \end{pmatrix},$$

$$ P(s,s',1) = \begin{pmatrix} 1 &amp; 0 \\ 1 &amp; 0 \end{pmatrix},$$

$$ P(s,s',2) = \begin{pmatrix} 0.5 &amp; 0.5 \\ 0.5 &amp; 0.5 \end{pmatrix},$$

$$ \beta \in (0,1). $$

Now suppose we start with two guesses for the value function

$$ V_1 (s) = \begin{pmatrix} 100 \\ 0 \end{pmatrix}, $$

and 

$$ V_2 (s) = \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$

If we iterate on these approximate value functions using the Bellman operator we get

$$ T(V_1) = \begin{pmatrix} \max_a \begin{cases} 1 +  100\beta, \qquad \text{ if }  a = 1, \\
                                                 1 +  50\beta,  \qquad \text{ if }  a = 2.                                               \end{cases}\\
                             \max_a \begin{cases} 1 +  100\beta, \qquad \text{ if }  a = 1, \\
                                                 1 +  50\beta,  \qquad \text{ if }  a = 2.                                               \end{cases} \end{pmatrix} = 
\begin{pmatrix} 1 + \beta 100 \\ 1+ \beta 100 \end{pmatrix}$$

and 

$$ T(V_2) = \begin{pmatrix} \max_a \begin{cases} 1 +  0\beta, \qquad \text{ if }  a = 1, \\
                                                 1 +  0.5\beta,  \qquad \text{ if }  a = 2.                                               \end{cases}\\
                             \max_a \begin{cases} 1 +  0\beta, \qquad \text{ if }  a = 1, \\
                                                 1 +  0.5\beta,  \qquad \text{ if }  a = 2.                                               \end{cases} \end{pmatrix} = 
\begin{pmatrix} 1 + \beta 0.5 \\ 1+ \beta 0.5 \end{pmatrix}$$

But then for $\beta$ close enough to $1$ and taking for instance the Manhattan norm, we have

$$ d(V_1(s),V_2(s)) \approx 101,$$

and 

$$ d(T(V_1(s)),T(V_2(s))) \approx 199.$$

Now that sounds weird to me because I thought $T$ was supposed to be a contraction mapping. Where did I screw up? Is there a mistake in my computation? I am forgetting to apply an important hypothesis? Or am I misunderstanding something about contraction mappings?
The value iteration operator is a contraction with respect to the supremum norm. Your example probably provides a counterexample for the statement that it's a contraction with respect to the Manhattan norm.