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$
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$
  • $\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$ – Martin Van der Linden Feb 21 '15 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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