next up previous
Next: Example: Up: The Solution of the Previous: is a fixed point

   
Uniqueness of $ \vec{v^*}$

If

\begin{eqnarray*}T\vec{v}_1 = \vec{v}_1,\ T\vec{v}_2 = \vec{v}_2,\ and\
\vec{v}_1 \neq \vec{v}_2
\end{eqnarray*}


then

\begin{eqnarray*}\Vert T\vec{v}_1-T\vec{v}_2\Vert = \Vert\vec{v}_1-\vec{v}_2\Vert \leq
\lambda\Vert\vec{v}_1-\vec{v}_2\Vert
\end{eqnarray*}


Hence $\lambda > 1$ in contradiction to the premises.
Thus $ \vec{v^*}$ is unique. $\Box$



Next we will show that the operator L is a contracting operator.

Claim 5.7   $\forall\ 0 \leq \lambda < 1$, L is a contracting operator.

Proof:For all $\vec{u}$, $\vec{v}$, we choose $s\in S$, and assume $L\vec{v}(s) \geq L\vec{u}(s)$.
We define as* such that:

\begin{eqnarray*}a_s^{*} \in argmax_{a \in A_s}\{r(s,a)+\lambda\sum_{j \in
S}P(j\vert s,a)\vec{v}(j)\}
\end{eqnarray*}



\begin{eqnarray*}0 & \leq & L\vec{v}(s)-L\vec{u}(s)\\ & \leq &
\underbrace{r(s,...
...rt\vec{v}-\vec{u}\Vert\\ & = & \lambda\Vert\vec{v}-\vec{u}\Vert
\end{eqnarray*}


We have shown that

\begin{eqnarray*}L\vec{v}(s)-L\vec{u}(s) \leq \lambda \Vert\vec{v}-\vec{u}\Vert
\end{eqnarray*}


(The same proof holds for $L\vec{v}(s) \leq L\vec{u}(s)$)

Thus, for all $s\in S$,

\begin{eqnarray*}\Vert L\vec{v}-L\vec{u}\Vert \leq \lambda \Vert\vec{v}-\vec{u}\Vert
\end{eqnarray*}


Hence L is a contracting operator. $\Box$

Theorem 5.8   Let $0 \leq\lambda<1$ and S a finite set, then
1.
There exists a unique solution v* such that Lv* and $v_{\lambda}^{*} = v^{*}$
2.
For all $\pi \in
\Pi^{MR}$ there exists a unique v such that $L_{\pi}v = v$ and $v_{\lambda}^{\pi} = v$

Proof:

1.
As L has been shown to be a contracting operator there is a unique solution for the equation Lv = v by theorem [*]. This fixed point is $v_{\lambda}^{*}$.
2.
Is true by the same argument.
$\Box$


next up previous
Next: Example: Up: The Solution of the Previous: is a fixed point
Yishay Mansour
1999-11-24