\documentclass[a4paper,fleqn]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{dsfont}
\usepackage{a4wide}

\parindent0pt

\newcommand{\NN}{\mathds{N}}
\newcommand{\N}{\mathds{N}}
\newcommand{\R}{\mathds{R}}
\newcommand{\set}[1]{\mathbf{#1}}
\newcommand{\vctr}[1]{\boldsymbol{#1}}

\newcommand{\noproof}{
        \vspace{-2.0ex}
        \begin{flushright} \tiny
        $\blacksquare$ \end{flushright} \smallskip

}
\newenvironment{proof}{

         \medskip
    \textbf{Proof:}}{\noproof}

\begin{document}

% out of: J.Rudl, Asynchronous Value Iteration Methods
% with Action Elimination for Solving Markovian and
% Semi-Markovian Decision Problems

[...]

\smallskip

If the points of time, when any of the processors are calculating,
are numbered successively, the originally continuous behavior of
the algorithm can be described by discrete stages, where in each
stage $n$, only a subset of states $\set{S}^{(n)} \subseteq
\set{S}$ is actualized (cf.~figure 1).

\medskip

Therefore, the asynchronous value iteration algorithm can be
described by a sequence of state sets
\begin{equation*}
\big( \mathbf{S}^{(n)} \big)_{n \in \NN}  \quad \textrm{with}
 \quad \mathbf{S}^{(n)} \subseteq \set{S},
\end{equation*}
a derived sequence of mappings
\begin{equation}
 \big(U^{(n)}\big)_{n \in \NN} \quad \textrm{with} \quad
\big(U^{(n)} \vctr{v}\big) (i) \ := \
        \left\{
        \begin{array}{ll}
                \big(U \vctr{v}\big) (i) &
                \mbox{for} \ i \in \set{S}^{(n)} \\
                \vctr{v} (i)  & \mbox{otherwise,}
        \end{array}
        \right.
\end{equation}
and an iteration rule
\begin{equation*}
\vctr{v}^{(n)} \ := \ U^{(n)} \vctr{v}^{(n-1)}, \qquad n \in \N,
\qquad \vctr{v}^{(0)} \in \R^N \ \mbox{arbitrarily.}
\end{equation*}


\begin{figure}[ht]
\fbox{Ein Bild \ldots}
\caption{Example of the run of an
asynchronous value iteration method}
\end{figure}

First of all, conditions must be found which assure the
convergence of such an asynchronous value iteration method with
action elimination. For some special single-step methods and
special tests of suboptimality, the convergence of the respective
methods has already been proved (cf.~[2],[1]). Here, a more
general theorem is presented.

As a first step to prove the convergence for the asynchronous
method, the convergence of a total-step method with action
elimination is shown. This method is defined in the following:

\smallskip

\textbf{Definition 1}
 For a relaxation vector $\Theta =
(\theta_i^a)_{(i,a) \in \set{D}}$ with $0 < \theta_i^a \le
\frac{1}{1-q_{ii}^a}$ let be
\begin{eqnarray*}
& & L \ := \ L_{\Theta}: \
    \vctr{v} \in \R^N \ \mapsto \ \Big(\big( L_{\Theta} \vctr{v} \big) (i,a) \Big)_{(i,a) \in \set{D}} \in
    \R^{|\set{D}|} \mbox{\quad with \ }
\\
& &
    \big(L_{\Theta} \vctr{v}\big)  (i,a)
    \ := \
    \displaystyle
    \theta_i^a \sigma_i^a +
    \theta_i^a
    \sum\limits_{j=1}^N
    q_{ij}^a \vctr{v} (j) + (1-\theta_i^a) \vctr{v} (i). \\
    & & [...]
\end{eqnarray*}

\medskip

The following lemma shows properties of a sequence of mappings,
which provide the convergence of the method described by this
sequence of mappings.

\smallskip

\textbf{Lemma 1} Let $\big(T_n\big)_{n \in \N}$ be a sequence of
mappings on a Banach space $\set{X}$, in which a norm $\| . \|$ is
defined.

\smallskip

If
\begin{itemize}
\item[(a)] $\big\| T_n \vctr{u} -
T_n \vctr{v} \big\| \ \le \ q_n \big\| \vctr{u} - \vctr{v} \big\|$
\quad and \quad $0 \le q_n \le q < 1$

 for all $n\in \N$ and $\vctr{u}, \vctr{v}
\in \set{X}$

and
\item[(b)] there exists a $\vctr{w} \in \set{X}$
with $\vctr{w} = T_n \vctr{w}$ \ for all $n \in \N$,
\end{itemize}
then the sequence $\big(\vctr{w}_n\big)_{n \in \NN}$ with
\begin{align*}
    \vctr{w}_n \ = \ T_n T_{n-1} \ldots T_1 \vctr{w}_0
\end{align*}
converges to $\vctr{w}$ for each $\vctr{w}_0 \in \set{X}$.

\noproof

Now it is shown that each mapping $U_{\set{D}^{(n)}}$, as defined
in definition 1, is contractive.

\smallskip

\textbf{Lemma 2} For $n \in \N$ it holds true that
\begin{eqnarray*}
& &   \big\|U_{\set{D}^{(n)}} \vctr{v} -
    U_{\set{D}^{(n)}} \vctr{u}
    \big\|  \ \le \
    \psi_{\set{D}^{(n)}} \,
    \big\| \vctr{v}-\vctr{u}\big\| \qquad
    \textrm{with} \\
& &   \qquad \qquad \psi_{\set{D}^{(n)}} \ := \
    1 - \!\!\! \min\limits_{(i,a) \in \set{D}^{(n)}} \!
    \Big\{ \theta_i^a
    \Big(
    1 - \sum\limits_{j=1}^N q_{ij}^a
    \Big) \Big\} \qquad \big( \vctr{v}, \vctr{u} \in \R^N \big)
\end{eqnarray*}
and $\psi_{\set{D}^{(n)}} < 1$.

\noproof

The following lemma provides a necessary and sufficient condition
on which the value function $\vctr{v}^{\ast}$ is the (unique)
fixed point of each operator $U_{\set{D}^{(n)}}$ \mbox{$(n \in
\N)$:} At least one optimal action, $a^{\ast} \in \set{D}^{\ast}
(i) \ (i \in \set{S})$, must remain in all respective sets,
$\set{D}^{(n)} (i) \ (n \in \N).$

\smallskip

\textbf{Lemma 3} For $n \in \N$, the value function
$\vctr{v}^{\ast}$ is the unique fixed point of the mapping
$U_{\set{D}^{(n)}}$, iff for all $i \in \set{S}$ an action $a :=
a_n (i) \in \set{D}^{(n)} (i)$ with $a \in \set{D}^{\ast} (i)$
exists.

\noproof


In the following, the convergence of a total-step value iteration
method with action elimination can be proved.

\smallskip

\textbf{Theorem 1} A sequence $\big( \vctr{v}^{(n)} \big)_{n \in
\NN_0}$, which is generated by a total-step value iteration method
with action elimination according to definition 1 converges on the
condition
\begin{equation*}
\set{D}^{(n)} \ \supseteq \ \set{D}^{\ast}  \qquad \mbox{for all
$n \in \N$}
\end{equation*}
to the value function $\vctr{v}^{\ast}.$


\begin{proof}
Since the sequence $\big( \vctr{v}^{(n)} \big)_{n \in \NN_0}$ is
generated by a sequence of mappings $\big( U_{\set{D}^{(n)}}
\big)_{n \in \NN}$, for which according to lemma 2
\begin{eqnarray*}
\big\|U_{\set{D}^{(n)}} \vctr{v} -
    U_{\set{D}^{(n)}} \vctr{u}
    \big\| &   \le &
    \psi_{\set{D}^{(n)}} \,
    \big\| \vctr{v}-\vctr{u}\big\| \qquad
(\vctr{v}, \vctr{u} \in \R^N) \qquad \mbox{with} \\
\psi_{\set{D}^{(n)}} &  = &
    1 - \!\!\! \min\limits_{(i,a) \in \set{D}^{(n)}} \!
    \Big\{ \theta_i^a
    \Big(
    1 - \sum\limits_{j=1}^N q_{ij}^a
    \Big) \Big\} \\
&     \le & 1 - \!\! \min\limits_{(i,a) \in \set{D}} \!
    \Big\{ \theta_i^a
    \Big(
    1 - \sum\limits_{j=1}^N q_{ij}^a
    \Big) \Big\} \ < \ 1,
\end{eqnarray*}
condition (a) of lemma 1 is satisfied. According to lemma 3,
condition (b) of lemma 1 with $\vctr{w} = \vctr{v}^{\ast}$ is
satisfied particularly, if $\set{D}^{(n)} \supseteq \set{D}^{\ast}
$ for all $n \in \N$. Thus the theorem is proved.
\end{proof}

\medskip

Now the asynchronous value iteration method with action
elimination is considered. Firstly, this method will be defined as
a ``composition'' of definition 1 and the asynchronous value
iteration method (1).


\begin{thebibliography}{9}

\bibitem{NH00}
V.~Nollau and D.~Hudak (2000). A Modified
{G}auss-{S}eidel-Algorithm with Exclusion of Suboptimal
  Actions for a Class of Semi-{M}arkovian Decision Problems.
{\em Optimization}, \textbf{48}(4), 429--451.

\bibitem{Ree73}
D.~Reetz (1973). Solution of a {M}arkovian Decision Problem by
Successive Overrelaxation. {\em Zeitschrift f\"ur Operations
Research}, \textbf{17}, 29--32.

\end{thebibliography}

\end{document}
