<p>The value iteration operator is a contraction with respect to the <em>supremum</em> norm. Your example probably provides a counterexample for the statement that it's a contraction with respect to the Manhattan norm.</p>

CC BY-SA 3.0
2015-02-21T02:31:35.383Z
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
CC BY-SA 3.0
2015-02-20T23:32:18.597Z
2015-02-20T23:32:18.597Z
Jefferson Huang
<p>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.</p>

<p>Consider a simple MDP with two states and two actions defined as follows.</p>

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

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

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

<p>$$ \beta \in (0,1). $$</p>

<p>Now suppose we start with two guesses for the value function</p>

<p>$$ V_1 (s) = \begin{pmatrix} 100 \\ 0 \end{pmatrix}, $$</p>

<p>and </p>

<p>$$ V_2 (s) = \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$</p>

<p>If we iterate on these approximate value functions using the Bellman operator we get</p>

<p>$$ 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}$$</p>

<p>and </p>

<p>$$ 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}$$</p>

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

<p>$$ d(V_1(s),V_2(s)) \approx 101,$$</p>

<p>and </p>

<p>$$ d(T(V_1(s)),T(V_2(s))) \approx 199.$$</p>

<p>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?</p>

<decision-theory><academic-graduate><optimization><markov-chain><bellman-equations>
Markov decision processes, contractions and value iteration
Martin Van der Linden
# Markov decision processes, contractions and value iteration

(Asked by: username_0 on 2015-02-20)

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?

**Tags:** decision-theory, academic-graduate, optimization, markov-chain, bellman-equations

---

## 1 answers

### Answer by username_1 on 2015-02-20. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

