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 & 1 \\ 1 & 1 \end{pmatrix},$$
$$ P(s,s',1) = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix},$$
$$ P(s,s',2) = \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 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?
