4
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 21, 2015 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.