# 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 & 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).$$

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

• Thanks Jefferson. I have seen people prove that operators are contractions using all kinds of norms (including $L_2$ and $L_{\infty}$). I must have inferred that norm equivalence applied to proving that an operator is a contraction, but that probably where I screwed up. I'll have a look into it tomorrow. – Martin Van der Linden Feb 21 '15 at 2:31