%&latex
%
%       Intmed.tex
%
%
%
\documentclass[leqno,12pt]{article}
\usepackage{amsmath,amssymb}
\usepackage{latexsym}

\topmargin = 0cm
\oddsidemargin = 0cm    
\evensidemargin = 0cm
\textheight = 24cm      
\textwidth = 16cm
\relpenalty=0
\topmargin=0cm

%------ Definition -------
\newcommand{\BR}{{\mathbb{R}}}
\newcommand{\inc}{{\preccurlyeq}}
\newcommand{\Pf}{\mbox{{\bf Proof.} \ }}
\newcommand{\qed}{{\quad Q.E.D.}}

% \preccurlyeq  % leqq
% \prec         % <
% \preceq       % le

% \succcurlyeq  % geqq
% \succ         % >
% \succeq       % ge


%------ End of Def -------
\begin{document}

\title
{Interval Methods for Uncertain Markov Decision Processes} 
\author
{M. Kurano\footnote{Dep of Mathematics,
Faculty of Education, 
${}^{\dag}$Dep of Mathematics \& Informatics,
Faculty of Science,
Chiba University,
Yayoi-cho, Inage-ku, Chiba, 263-8255 Japan},
Masami Yasuda${}^{\dag}$ and 
J. Nakagami${}^{\dag}$
%and M. Horiguchi{\dag}
}
\date{}

\maketitle

\begin{abstract}%
   In this paper, the average cases of Markov decision processes 
with uncertainty is considered. That is, a controlled Markov 
set-chain model with a finite state and action space
is developed by an interval arithmetic analysis, 
and we will find a Pareto optimal
policy which maximizes the average expected rewards over all 
stationary policies under a new partial order.
The Pareto optimal policies is characterized by a maximal solution 
of
an optimality equation which is derived from the model.
Also, a maximin policy is obtained and shown to be Pareto-optimal.
A numerical example is given.

\end{abstract}

\textit{Keywords}: Controlled Markov set-chains, average reward criterion, 
Pareto optimal, interval arithmetic.

\textit{AMS 1991 subject classification}. Primary: 90c40; Secondary: 90c39.


%%% Section 1
\section{Introduction and notations}

In a real application of Markov decision processes(MDP's in short, 
cf.\cite{hinderer, howard, puterman}), the require data must be 
estimated.
Thus, the mathematical model of MDPs can be only be viewed as 
approximations. 
It may be useful that the model is ameliorated so to be more 
"robust" in
the sense that it's reasonably efficient in rough approximations.
How can be modelized this situation?
One of a realistic way to answer such a problem is 
to use certain intervals containing the required data.

Applying Hartfiel's\cite{hartfiel94, hartfiel98} interval method for 
Markov chains, Kurano et al\cite{kshh} has introduced a decision 
model,
called a controlled Markov set-chain, which is robust for rough 
approximation of the transition matrix in MDPs.
The discounted reward problems was developed in \cite{knh98,kshh}
and the non-discounted case had been discussed in \cite{hosaka}.
However, the functional characterization of optimal
policies for average reward problems 
is not given yet.

In this paper, applying an interval arithmetic analysis, the average
case of MDPs with uncertainty is considered. That is, in a 
controlled 
Markov set-chain with finite state and action spaces, we will find
a Pareto optimal policy which maximizes the average expected rewards
over all stationary policies under some partial order.

Analyzing the behavior of the expected rewards over $T$-horizon as 
$T$
approaches $\infty$ under some regularity condition, the average 
expected 
rewards corresponding to any stationary policy is given as a unique
solution of an interval equation.
Also, Pareto optimal policies are characterized by a maximal 
solution of
an optimality equation determined by the decision model.

Concerning about a Pareto optimal policy, we will consider a maximin 
policy, 
which maximizes
the expected average reward in the worst cases scenarios for the 
decision 
process.
Takahashi\cite{taka84, taka88} has introduced a weak $D$-Markov chain
in order to treat bounds for state probabilities of aggregated 
chains 
in the large scale Markov chains and applied to tandem queueing 
networks.
The results are closely related to ours and we will clear it 
in the sequel.

In the remainder of this section, we shall give some notation 
referring
to the works \cite{hartfiel93, hartfiel94,  hartfiel98} on Markov 
set-chain
and an interval arithmetic by \cite{nenmaier} 
and formulate a controlled Markov set-chain which will be examined in the 
sequel.

Let $R$, $R^n$ and $R^{n\times m}$ be the sets of real numbers, 
real $n$-
dimensional column vectors and real $n\times m$ matrices, 
respectively. 
We 
shall identify $n\times 1$ matrices with vectors and $1\times 1$ 
matrices 
with real numbers, so that $R=R^{1\times 1}$ and 
$R^n = R^{n \times 1}$. 
Also, we denote by $R_+$, $R_+^n$ and $R_+^{n\times m}$ the subsets 
of 
entrywise non-negative elements in $R$, $R^n$ and $R^{n\times m},$ 
respectively. 

We equip $R^{n\times m}$ with the component-wise relations 
$\leq, <, \geq, >$.
For any $\underline A = (\underline a_{ij})$, 
$\overline A = (\overline a_{ij})$ in 
$R_+^{n\times m}$ with $\underline A \leq \overline A$, 
we define the
set of stochastic matrices, 
$\langle\underline A, \overline A \rangle,$ by
$$ 
  \langle \underline A, \overline A \rangle 
  := \{A \;| \; A = (a_{ij}) \; {\rm is an} \;  n \times m \;
  {\rm stochastic matrix with} \; \underline A \leq A \leq 
  \overline A \},
$$
Let
$$
  {\cal M}_n := \{{\cal A} 
  = \langle\underline A,
  \overline A \rangle \; \vert \; \langle 
  \underline A,
  \overline A \rangle \neq \emptyset, \underline A
  \leq \overline A \;
  {\rm and} \; \underline A, \overline A \in R_+^{n\times n}\}.
$$
The product of $\cal A$ and ${\cal B}\in{\cal M}_n$ is defined by 
$$ 
  {\cal AB} := \{AB \; | \; A \in {\cal A}, B \in {\cal B}\}.
$$
For any sequence $\{{\cal A}_i\}_{i=1}^\infty$ with 
${\cal A}_i\in{\cal M}_n \; (i\geq 1)$, 
we define the multiproduct inductively by
$$ 
  {\cal A}_1{\cal A}_2\cdots{\cal A}_k 
  := ({\cal A}_1 \cdots {\cal A}_{k-1}) {\cal A}_k \quad (k\geq 2).
$$
Denote by $C(R_+)$ the set of all bounded and closed intervals in 
$R_+$.
Let $C(R_+)^n$ be the set of all $n$-dimensional column vectors 
whose
elements are in $ C(R_+),$ i.e.,
$$
  C(R_+)^n := \{D=(D_1,D_2,\cdots,D_n)^\prime \; | \; 
  D_i\in C(R_+) (1 \leq i \leq n)\}.
$$
where $d^\prime$ denotes the transpose of a vector $d$. 

The following arithmetics are used in Section 2. 
For $ D=(D_1,D_2,\cdots,D_n)^\prime,
 E = (E_1, E_2, \cdots, E_n)^\prime \in
C(R_+)^n, h \in R_+^n$ and 
$\lambda \in R_+$, $D + E = \{d + e \; | \; d \in D, e \in E\},
\lambda D = \{ \lambda d \; | \; d \in D\}$ and 
$h + D = \{ h + d \; | \; d \in D\}$. 
If  $D = ([\underline d_1, \overline d_1], \cdots, 
[\underline d_n, \overline d_n])^\prime, D$ will be denoted by 
$D = [\, \underline d,\overline d \,]$,
where 
$ \underline d = (\underline d_1, \cdots, \underline d_n)^\prime,
\quad \overline d = (\overline d_1, \cdots, \overline d_n)^\prime$ 
and $ [\, \underline d, \overline d \,] 
  = \{ d \in R_+^n \; | \; \underline d \leq d \leq \overline d \}$. 

For any $D = (D_1, D_2, \cdots, D_n)^\prime \in C(R_+)^n$ 
and subset $G$ of $ R_+^{1\times n}$ the product of $G$ 
and $D$ is defined as
$$ 
  GD := \{gd \; | \; g = (g_1,\cdots,g_n) \in G,
  d = (d_1, \cdots, d_n)^\prime \in D, 
  d_i \in D_i (1 \leq i \leq n)\}.
$$

The following results are used in the sequel.

\vspace{2ex}
\noindent
{\bf Lemma 1.1 }(\cite{hartfiel98,kshh})
\begin{itemize}\setlength{\itemsep}{0pt}
  \item [(i)] Any ${\cal A} \in {\cal M}_{n}$ is a convex polytope 
in the
    vector space $R^{n\times n}$.
  \item [(ii)] For any compact convex subset 
$G \subset R_+^{1\times n}$ 
  and $D = (D_1, D_2, \cdots, D_n)^\prime \in C(R_+)^n$, 
  it holds $GD \in C(R_+)$.
\end{itemize}

We will give a partial order 
         %%%% 
         $ \succ, \succeq $ 
on $ C(R_+) $ by the definition :
For $[c_1, c_2], [d_1, d_2] \in C(R_+)$, 
$$ 
  [c_1, c_2]  \succeq  [d_1, d_2]  \quad  {\rm if}  \quad
  c_1 \geq d_1, c_2 \geq d_2,
$$
and
$$
  [c_1, c_2] \succ [d_1, d_2] \quad 
  {\rm if} \quad [c_1, c_2] \succeq [d_1, d_2]
  \quad {\rm and} \quad  [c_1, c_2] \neq [d_1, d_2].
$$
For $\mbox{\boldmath $v$} = (v_1, v_2, \cdots, v_n)^\prime$ and 
$\mbox{\boldmath $w$} = (w_1, w_2, \cdots, w_n)^\prime \in C(R_+)^n$, we write 
$\mbox{\boldmath $v$} \succeq \mbox{\boldmath $w$}$ 
(by abase of notation) if 
$v_i \succeq w_i, \quad 1 \leq i \leq n $ 
and $\mbox{\boldmath $v$} \succ \mbox{\boldmath $w$}$ if 
$\mbox{\boldmath $v$} \succeq \mbox{\boldmath $w$}$ and 
$\mbox{\boldmath $v$} \neq \mbox{\boldmath $w$}$.
Define a metric $\Delta$ on $C(R_+)^n$ by
$$ 
  \Delta(\mbox{\boldmath $v$},\mbox{\boldmath $w$}) 
  := \max_{i\in S}\delta(v_i,w_i) 
$$ 
for $ \mbox{\boldmath $v$} = (v_1, v_2, \cdots, v_n)^\prime, 
\mbox{\boldmath $w$} = (w_1, w_2, \cdots, w_n)^\prime \in C(R_+)^n$, 
where $\delta$ is the Hausdorff metric on $C(R_+)$ and given by
$$ 
  \delta([a,b],[c,d]) := \vert a-c \vert \vee \vert b-d \vert \quad 
  {\rm for} \quad [a,b], [c,d] \in C(R_+),
$$
where  $ x \vee y = \max \{x, y\} $.
Obviously, $(C(R_+)^n, \Delta)$ is a complete metric space.

A controlled Markov set-chain consists of four object: 
  $$(S, A, {\underline q}, {\overline q}, r), $$ 
where 
$S = \{1, 2, \cdots, n\}$ and
$A = \{1, 2, \cdots, k\}$ are finite sets and for each 
$
 (i,a) \in S \times A,
 {\underline q} = {\underline q}(\cdot \vert i,a) 
 \in R_+^{1\times n},
$ 
${\overline q} = {\overline q}(\cdot \vert i,a) \in R_+^{1\times n} $ 
with ${\underline q} \leq {\overline q} $ and 
$ \langle {\underline q}, 
{\overline q} \rangle \ne \emptyset $ and 
$r = r(i,a)$ a function on $S \times A$ with $r \geq 0$.
Note that $A$ is used as the set in this section, different from
that in the previous section. We interpret $S$ as the set of states 
of 
some system, and $A$ as the set of actions available at each state.

When the system is in state $i \in S$ and we take action $a \in A$, 
we move to a new state $j \in S$ selected according to the 
probability
distribution on $S$, $q(\cdot \vert i,a)$, and we receive an 
immediate return, 
$r(i,a)$, where we know only that $q(\cdot \vert i,a)$ is arbitrarily
chosen from $\langle {\underline q}(\cdot \vert i,a), 
{\overline q}(\cdot \vert i,a) \rangle$. 
This process is then repeated from the new state $j$.
Denote by $F$ the set of functions from $S$ to $A$.

A policy $\pi$ is a sequence $(f_1, f_2, \cdots)$ of functions with
$ f_t \in F, (t \geq 1) $.  
Let $\Pi$ denote the class of policies. 
We denote by $f^\infty$ the policy $(h_1, h_2, \cdots)$ with 
$h_t = f$ for all $t \geq 1$ and some $f \in F$. 
Such a policy is called stationary, denoted
simply by $f$, and the set of stationary policies is denoted by 
$\Pi_F$. 

We associate with each $f \in F$ the $n$-dimensional column vector
$r(f) \in R_+^n$ whose $i$-th element is $r(i,f(i))$ and the set of
stochastic matrices 
${\cal Q}(f) := \langle {\underline Q}(f), 
{\overline Q}(f) \rangle \in {\cal M}_n$, 
where the $(i,j)$ elements of ${\underline Q}(f)$ and 
${\overline Q}(f)$ are ${\underline q}(j \vert i,f(i))$ and 
${\overline q}(j\vert i, f(i))$, respectively, and 
$\langle {\underline Q}(f), {\overline Q}(f) \rangle$
is already defined. 

For any $\pi = (f_1, f_2, \cdots) \in \Pi$, let 
$\mbox{\boldmath $v$}_1(\pi) = r(f_1)$ and,
 by setting $Q_0 = \textrm{identity}$,
$$
  {\mbox{\boldmath $v$}}_T(\pi) = 
     \{\displaystyle{\Sigma_{i=1}^{T} Q_1 Q_2 \cdots Q_{t-1}r(f_t)
     \mid 
     Q_i \in {\cal Q}(f_i), i=1,2,\cdots,T-1\}} \quad  (T \geq 2).
\eqno{(1.1)}
$$
We observe, for example, that 
$$
  \mbox{\boldmath $v$}_3(\pi) = r(f_1) + 
       {\cal Q}(f_1) {\left(r(f_2)+{\cal Q}(f_2)r(f_3)\right)},
$$
so that by Lemma 1.1 (ii) it holds that 
$\mbox{\boldmath $v$}_T(\pi)\in C(R_+)^n $ 
for all $T\geq 1$.
For any $\pi \in \Pi $, let
$$
  \mbox{\boldmath $v$}(\pi) := 
  \liminf_{T \to \infty} \frac{1}{T} \mbox{\boldmath $v$}_T(\pi), 
\eqno{(1.2)}
$$
where, for a sequence $\{D_k\} \subset C(R_+)^n$,
$$
  \liminf_{k\to \infty}D_k 
  :=\left\{ x \in R^n \left| \limsup_{k \to \infty}
  \delta_1(x,D_k) = 0 \right. \right\}, 
$$
and 
$\delta_1(x,D) := {\inf_{y \in D} \delta_2(x,y)}$, 
$\delta_2$ is a metric in $R^n$. 
Since $\mbox{\boldmath $v$}(\pi) \in C(R_+)^n, 
\mbox{\boldmath $v$}(\pi)$ is written as 
$\mbox{\boldmath $v$}(\pi) = [\underline{v}(\pi),
\overline{v}(\pi)]$.

\vspace{2ex}
\noindent
\textbf{Definition.}
A policy $f^* \in \Pi_F$ is called \textsl{Pareto optimal} if 
there does not exist $f \in \Pi_F$ such that  
$\mbox{\boldmath $v$}(f^*) \prec \mbox{\boldmath $v$}(f)$.

\vspace{2ex}
In the above definition, we confine ourselves to the stationary 
policies,
which simplifies our discussion in the sequel.
In Section 2, a regularity condition for the class of transition
matrices
is introduced, under which the interval equations concerning the 
average
rewards are investigated. 
In Section 3, the asymptotic behavior of 
$\mbox{\boldmath $v$}_T(f)$ as $T$
approaches $\infty$ is given. 
And in Section 4, 
Pareto optimal policies are characterized by maximal solutions of 
optimality
equation. Also, a maximin policy which maximizes the expected 
reward earned
in the worst cases scenarios is given and shown to be Pareto 
optimal.




%%% Section 2
\section{Assumption and preliminary lemmas}


Henceforth, the following assumption will remain operative.

\vspace{2ex}
\noindent
\textbf{Assumption A (Primitivity).}  For any $f \in F$, 
each $Q \in {\cal Q}(f)$ is primitive, i.e., $Q^t>0$ for some 
$t \geq 1$.

\vspace{2ex}
Obviously, if ${\underline Q}(f)$ is primitive in the sense of 
non-negative
matrix ( cf.\cite{seneta}), Assumption A holds.

The following facts on Markov matrices are well-known
(cf.\cite{blackwell, kemeny}).

\vspace{2ex}
\noindent
\textbf{Lemma 2.1}  
For any $f \in F$, let $Q$ be any matrix in ${\cal Q}(f)$.
\begin{itemize} 

  \vspace{-1ex}
  \item[(i)] The sequence $(I+Q+\cdots +Q^t)/(t+1)$ converges as 
    $t \to \infty $ to
    a stochastic matrix $Q^*$ with $Q^* Q = Q^*, \quad Q^* > 0$ and
    $\mbox{rank}(Q^*) = 1$.
  
  \vspace{-1ex}
  \item[(ii)] The matrix $Q^*$ in (i) is uniquely determined by 
    $Q^* Q = Q$ and
    $\mbox{rank}(Q^*) = 1$.
\end{itemize}

Associated with each $f \in F$ is a corresponding operator $L(f)$, 
mapping
$C(R_+)^n$ into $C(R_+)^n$, defined as follows.

For $\mbox{\boldmath $v$} \in C(R_+)^n,$ 
$$
  L(f)\mbox{\boldmath $v$}:=r(f)+{\cal Q}(f)\mbox{\boldmath $v$}.
\eqno{(2.1)}
$$
Note that from Lemma 1.1, $L(f)\mbox{\boldmath $v$}\in C(R_+)^n$ 
for each
$\mbox{\boldmath $v$}\in C(R_+)^n.$
Putting $\mbox{\boldmath $v$} = [\underline{v},
\overline{v}]$ with 
$\underline{v} \leq 
\overline{v}$, 
$\underline{v}, 
\overline{v} 
\in R_+^n$, (2.1) can be written as
$$
  L(f) \mbox{\boldmath $v$} = [{\underline L}(f) 
  {\underline{v}}, {\overline L}(f) 
  {\overline{v}}], 
\eqno{(2.2)}
$$
where ${\underline L}$ and ${\overline L}$ are operators from 
$R^n$ into 
itself, defined by :
$$
  \left\{
  \begin{array}{l}
    {\underline L}(f)v = 
    r(f) + \min_{Q \in {\cal Q}(f)} Qv, \\
    
    \vspace{1ex}
    {\overline L}(f)v = 
    r(f) + \max_{Q \in {\cal Q}(f)} Qv. 
  \end{array}
  \right.
\eqno{(2.3)}
$$
and min(max) represents component-wise minimization(maximizing).

Let ${\bf e} := (1,1,\cdots,1)'$.
Here, for any $f \in F$, we consider the interval equation:
$$ 
   r(f) + {\cal Q}(f)\mbox{\boldmath $h$} = 
   \mbox{\boldmath $v$}+\mbox{\boldmath$h$}, 
\eqno{(2.4)}
$$
where $\mbox{\boldmath $v$} := [{\underline v} \textbf{e},
{\overline v} \textbf{e}], \; 
\mbox{\boldmath$h$} = [{\underline h}, {\overline h}] \in C(R)^n,
\; {\underline v}, {\overline v} \in R, {\underline h}, 
{\overline h} \in
R^n$ with ${\underline v} \leq {\overline v}, {\underline h} \leq 
{\overline h}$.

Obviously, the interval equation can be rewritten by their extremal 
points as
$$
  \left\{
  \begin{array}{l}
   r(f) + \min_{Q \in {\cal Q}(f)} Q{\underline h} 
    = {\underline v}\textbf{e} + {\underline h}  \\
   
   \vspace{1ex}
   r(f) + \max_{Q\in {\cal Q}(f)} Q{\overline h }
    = {\overline v} \textbf{e} + {\overline h}
  \end{array} \right.
\eqno{(2.5)}
$$
with
$$
  {\underline v} \leq {\overline v}, \quad {\underline h} \leq 
  {\overline h}
\eqno{(2.6)}
$$
where
${\underline v}, {\overline v} \in R, {\underline h}, {\overline h} 
\in R^n$.

Takahashi\cite{taka84, taka88} has showed that upper or lower bounds 
of the 
average rewards for weak $D$-Markov chains satisfies both of the 
equations (2.5), and had calculated them with Howard's policy 
improvement (\cite{howard}).

We have the following lemma.  

\vspace{2ex}
\noindent
\textbf{Lemma 2.2}(\cite{bather, hosaka})
For any $f\in F$, the interval equation (2.5) determines 
$\mbox{\boldmath$v$}$ uniquely and $\mbox{\boldmath$h$}$ 
up to an additive constant
$[c_1{\bf e}, c_2{\bf e}]$ with $c_1, c_2 \in R (c_1<c_2)$.


%%% Section 3
%\section{Asymptotic properties of $v_T(f)$ }
\section{Asymptotic bounds for the finite horizon reward }


In this section we give the asymptotic behavior of 
$\mbox{\boldmath$v$}_T(f)$ as $T \to \infty$ under Assumption A,
whose proofs are given in \cite{hhk}.
Throughout this section, we assume that Assumption A holds.

For any $\mbox{\boldmath $g$}\in C(R)^n $ and $f \in F$, the sequence
$\left\{\mbox{\boldmath $v$}_T(f,\mbox{\boldmath $g$}) , 
T \geq 0 \right\}$ is defined as follows:
$$
  \mbox{\boldmath $v$}_0(f,\mbox{\boldmath $g$})
  :=\mbox{\boldmath $g$}
  %\hspace{1cm}\mbox{ and }\hspace{9cm}
$$
and
$$
  \mbox{\boldmath $v$}_T (f,\mbox{\boldmath$g$})
  :=\left\{ \Sigma_{i=1}^{T} Q_1 \cdots Q_{t-1} r(f) 
      + Q_1 \cdots Q_T \mbox{\boldmath $g$} \mid 
     Q_i  \in {\cal Q}(f), i=1,\cdots,T \right\} \;\; (t \geq 1).  
\eqno{(3.1)}
$$

\vspace{2ex}
\noindent
\textbf{Lemma 3.1} 
For any $\mbox{\boldmath $g$} \in C(R_+)^n $ and $f\in F$, the 
sequence
$\left\{\mbox{\boldmath $v$}_T(f,\mbox{\boldmath $g$})\right\}$ 
satisfies
that 
$$
  \mbox{\boldmath $v$}_T(f,\mbox{\boldmath $g$}) = 
  L(f)\mbox{\boldmath$v$}_{T-1}(f,\mbox{\boldmath $g$})\;\;\;(T\geq 1).  
\eqno{(3.2)}
$$


Since the solutions $\underline v,\;\overline v,\;\mbox{\boldmath 
$h$}$ of
(2.4)-(2.6) in Section 2 are depending on $f\in F$, we will denote 
them
respectively by $\mbox{\boldmath $v$}(f)=[\underline v(f){\bf e},
\overline
v(f){\bf e}]$ and $\mbox{\boldmath $h$}(f)=[\underline h(f),
\overline h(f)].$

\vspace{2ex}
\noindent
\textbf{Lemma 3.2}
For any $f \in F$, it holds that
$$
  \mbox{\boldmath $v$}_T(f,\mbox{\boldmath $h$}(f)) = T 
  \mbox{\boldmath$v$}(f) + \mbox{\boldmath $h$}(f)\;\;
  \mbox{  for all } \; T \geq 0. 
\eqno {(3.3)}
$$


The following theorem is concerned with the asymptotic properties of
$\mbox{\boldmath $v$}_T(f)$ as $T \to \infty$.

\vspace{2ex}
\noindent
\textbf{Theorem 3.1}
For any $f\in F$, there exists $c_1, c_2, c_1', c_2' \in R 
\; (c_1' \le c_1, c_2' \le c_2 )$ such that 
$$ 
  [(T \underline v(f) + c_1){\bf e}, (T \overline v(f)+c_2'){\bf e}]
  \subset
  \mbox{\boldmath $v$}_T(f) \subset [(T \underline v(f)+c_1')
  {\bf e},(T\overline v(f)+c_2){\bf e}]$$
$$\hspace{10cm} \mbox{for all } \; T \geq 0,  \eqno{(3.4)}$$
where $[a,b] = \emptyset$, if $a > b$.

\vspace{2ex}
For simplicity of the notation, let, for any $d \in R^n$ and 
$f \in F$,  
$$
  {\underline{\cal Q}}(f,d) := 
  \left\{Q\in{\cal Q}(f) \left| Qd = \min_{Q\in{\cal Q}(f)}Qd\right.
  \right\},
$$
and
$$
  {\overline{\cal Q}}(f,d) := 
  \left\{Q\in{\cal Q}(f)\left| Qd = \max_{Q\in{\cal Q}(f)}Qd\right.
  \right\}.
$$

\vspace{2ex}
\noindent
\textbf{Corollary 3.1} 
For any $f\in F$, it holds
$$
  \mbox{\boldmath $v$}(f) = [\underline v(f){\bf e},
  \overline v(f){\bf e}]
  \hspace{5cm}\leqno{\rm (i)}
$$
and
$$
  \underline v(f){\bf e} = \underline Q^*r(f) , \quad \overline v(f)
  {\bf e} = \overline Q^*r(f) 
  \hspace{3cm}\leqno{\rm (ii)}
$$
for any 
$\underline Q \in \underline{\cal Q}(f, \underline h) \: 
\mbox{ and }\:
\overline Q \in \overline {\cal Q} (f, \overline h),\;$ 
where
$\displaystyle{Q^* = \lim_{T \to \infty} \frac{1}{T} 
\sum_{t=0}^{T-1} Q^t}$ 
for $Q \in {\cal Q}(f)$.




%%% Section 4
\section{Characterization of Pareto optimal policies}


In this section, we derive the optimality equation by which all 
Pareto 
optimal policies are characterized.

\vspace{2ex}
\noindent
\textbf{Lemma 4.1} 
Let $f$ be Pareto optimal and 
  $\mbox{\boldmath $v$}(f) = [\underline v(f){\bf e},
  \overline v(f){\bf e}] $.
Then, it holds
$$
  \underline v(f){\bf e} = \min_{Q \in {\cal Q}(f)} Q^*r(f),
  \hspace{5cm}\leqno{\rm (i)}
$$
and
$$
  \overline v(f){\bf e} = \max _{Q \in {\cal Q}(f)} Q^*r(f).
  \hspace{3cm}\leqno{\rm (ii)}
$$
Proof.
Let $\overline v(f), \underline v(f) \in R$ and 
$\overline h(f), \underline h(f) \in R^n$
be a solution of (2.5).
Then, for any $Q \in {\cal Q}(f)$, (2.5) implies
$$
   r(f) + Q{\underline h}(f) 
    \succeq
   {\underline v}(f)\textbf{e} + {\underline h}(f) 
\eqno{(4.1)}
$$
By $Q^*Q =Q$, (4.1) derives that 
$\underline v(f){\bf e} \preceq Q^*r(f)$
This fact implies (i) by Corollary 3.1(ii).
Similarly, (ii) can be proved.
\qed

\vspace{2ex}
\noindent
\textbf{Lemma 4.2}
For any $f,g$ in $F$,  suppose that
$$
   \mbox{\boldmath $v$}(f) + \mbox{\boldmath $h$}(f)
   \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
   r(g) + {\cal Q}(g) \mbox{\boldmath $h$}(f).
\eqno{(4.2)}
$$
Then, it holds that
$$
   \mbox{\boldmath $v$}(f)
   \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
   \mbox{\boldmath $v$}(g).
\eqno{(4.3)}
$$
Proof.
The left and right extremal equation of (4.2) are given as follows.
$$
   \underline v(f) {\bf e} + \underline h(f)
   \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
   r(g) + \min_{Q \in {\cal Q}(f)} Q {\underline h(f)}
\eqno{(4.4)}
$$
$$
   \overline v(f) {\bf e} + \overline h(f)
   \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
   r(g) + \max_{Q \in {\cal Q}(f)} Q {\overline h(f)}.
\eqno{(4.5)}
$$
By Lemma 4.1, there exists $\underline Q \in  {\cal Q}(g)$ 
with $\underline v(g) {\bf e} =  \underline Q^* r(g)$.
Multiplying the both sides of (4.4) by $\underline Q^*$, 
we get that
from $\underline Q^* \underline Q = \underline Q^*$ 
and $ \underline Q^* > 0$ that
$
 {\underline v}(f){\bf e} 
  \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
 {\underline Q}^* r(g)
$.
Thus   ${\underline v}(f) {\bf e} 
  \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
 \underline v(g) {\bf e}$  
follows.
Similarly, we get 
  $\overline v(f) {\bf e} 
  \left\{
   \begin{array}{c}
      \preceq \\
      \prec
   \end{array}
   \right\}
  \overline v(g) {\bf e}$, 
which proves (4.3).
\qed

Let ${\cal U}$ be an arbitrary subset of ${\cal C}(R)^n$.
A point $\mbox{\boldmath $u$} \in {\cal U}$ is called 
an efficient element of
${\cal U}$  with respect to $\preceq$ on ${\cal C}(R)^n$
iff it holds that there does not exist $\mbox{\boldmath $v$}
 \in {\cal U}$ 
such that $\mbox{\boldmath $u$} \prec \mbox{\boldmath $v$}$.
We denote by eff(${\cal U}$) the set of all elements of 
${\cal U}$ efficient with 
respect to $\preceq$
on ${\cal C}(R)^n$.
For any $\mbox{\boldmath $u$} \in {\cal C}(R)^n$, let
$$
  {\cal L}(\mbox{\boldmath $u$}) 
 := \textrm{eff}\left(\{ L(f)\mbox{\boldmath $u$} 
  \mid f \in  F \}\right),
$$
where $ L(f)\mbox{\boldmath $u$} \in {\cal C}(R)^n$ is defined in (2.1).
We note that ${\cal L}(\mbox{\boldmath $u$}) \subset {\cal C}(R)^n$ 
for any 
$\mbox{\boldmath $u$} \in {\cal C}(R)^n$.

Here, we consider the following interval equations inducing 
efficient 
set-function ${\cal L}(\cdot)$ on ${\cal C}(R)^n$.
$$
  \mbox{\boldmath $v$} + \mbox{\boldmath $h$} 
  \in {\cal L}(\mbox{\boldmath $h$}),
\eqno{(4.6)}
$$
where 
$ \mbox{\boldmath $v$} = [\underline v{\bf e},
    \overline v{\bf e}] , 
  \mbox{\boldmath $h$} = [\underline h,
    \overline h] \in {\cal C}(R)^n$
and
$ \underline v \leq \overline v, 
  \underline h \leq \overline h $,
$ \underline v,  \overline v \in R, 
  \underline h, \overline h \in R^n$.
The equation (4.6) is called an optimality equation, by which Pareto 
optimal 
policies are characterized.
A solution $(\mbox{\boldmath $v$},\mbox{\boldmath $h$})$ of the 
optimal equation (4.6) is called maximal 
if there does not exist any solution $(\mbox{\boldmath $v$}',
\mbox{\boldmath $h$}')$ of (4.6) such that
 $\mbox{\boldmath $v$} \prec \mbox{\boldmath $v$}'$.
In the following, Pareto optimal policies are characterized by 
maximal 
solutions of the optimality equation.

\vspace{2ex}
\noindent
\textbf{Theorem 4.1}
A policy $f^{\infty}$ is Pareto optimal if and only if the pair 
$(\mbox{\boldmath $v$}(f), \mbox{\boldmath $h$}(f))$ 
given by Lemma 2.2 is a maximal solution to the 
optimality 
equation (4.6).

Proof.
The proof of "only if " part is easily obtained from Lemma 4.2.
In order to prove "if" part, suppose that $(\mbox{\boldmath $v$}(f),
\mbox{\boldmath $h$}(f))$ is a maximal 
solution of (4.6) but $f^{\infty}$ is not Pareto optimal.
Then, there exists $g \in F$ with $\mbox{\boldmath $v$}(f) \prec 
\mbox{\boldmath $v$}(g)$.
Since $\{ \mbox{\boldmath $v$}(g') \vert \mbox{\boldmath $v$}(g) 
\preceq \mbox{\boldmath $v$}(g'), g' \in  F \}$ 
is finite, it has a maximal element $\mbox{\boldmath $v$}(g^{(1)})$ 
with respect to 
the partial order $\preceq$.
For this $g^{(1)}$, suppose that 
  $\mbox{\boldmath $v$}(g^{(1)}) + \mbox{\boldmath $h$}(g^{(1)}) 
  \notin {\cal L}(\mbox{\boldmath $h$}(g^{(1)}))$.
Then, there exists an $i_0 \in S$ and $a_0 \in A$ such that
$$
      \mbox{\boldmath $v$}(g^{(1)})_{i_0} + 
      \mbox{\boldmath $h$}(g^{(1)})_{i_0} \prec
      r(i_0, a_0) +
      \left( q(i_0, a_0) \mbox{\boldmath $h$}(g^{(1)})\right)_{i_{0}}, 
\eqno{(4.7)}
$$
where $ q(\cdot |i_0, a_0) := \langle \underline q(\cdot |i_0, a_0), 
        \overline q(i_0, a_0)\rangle $.
Define $f^{(1)}$ by
$$
  f^{(1)} = 
    \left\{
    \begin{array}{ll}
        a_0, \quad & \textrm{if} \quad i = i_0, \\
        g^{(1)}(i), \quad & \textrm{if} \quad i \neq i_0. 
    \end{array}
    \right.
$$
Then, from (4.6), it holds that
$$
      \mbox{\boldmath $v$}(g^{(1)}) + 
      \mbox{\boldmath $h$}(g^{(1)}) \prec
      r(f^{(1)}) + Q(f^{(1)}) \mbox{\boldmath $h$}(g^{(1)}). 
\eqno{(4.8)}
$$
Thus, by Lemma 4.2, $\mbox{\boldmath $v$}(g^{(1)}) 
\prec \mbox{\boldmath $v$}(f^{(1)})$.
For this $f^{(1)}$, obviously $\mbox{\boldmath $v$}(f) 
\prec \mbox{\boldmath $v$}(f^{(1)})$.
If $\mbox{\boldmath $v$}(f^{(1)}) + \mbox{\boldmath $h$}(f^{(1)}) 
\notin {\cal L}(\mbox{\boldmath $h$}(f^{(1)}))$, 
we can construct $f^{(2)}$ with $\mbox{\boldmath $v$}(f^{(1)}) 
\prec \mbox{\boldmath $v$}(f^{(2)})$, 
repeating the above
discussion.
Since $F$ is a finite set, by repeating this method successively,
we come to the conclusion that there exists $f^{(k)} \in F$ 
such that $\mbox{\boldmath $v$}(f) \prec \mbox{\boldmath $v$}(f^{(k)})$ 
and $(\mbox{\boldmath $v$}(f^{(k)}), \mbox{\boldmath $h$}(f^{(k)}))$ 
satisfies (4.6). However, 
this contradicts that $(\mbox{\boldmath $v$}(f), 
\mbox{\boldmath $h$}(f))$ is maximal.
\qed

\vspace{2ex}
\noindent
\textbf{Remark.}
For vector-valued discounted MDPs, Furukawa\cite{furu} and 
White\cite{white} had derived the optimal equation including
efficient set-function on $R^n$, by which optimal policies are
characterized.
The form of the optimality equation (4.6) is corresponding 
to the average case of controlled Markov set-chains.


%%% Section 5
\section{The maximim policy and an numerical example}

In this section, a maximin policy which maximizes the expected 
average 
reward earned in the worst case scenarios of the decision process is 
given and shown to be Pareto optimal.
Also a numerical example is given.


Let ${\bf q}(i,a) := \langle {\underline q}(\cdot \vert i,a),
{\overline q}(\cdot \vert i,a) \rangle \;$ 
for each $ i \in S $ and $a \in A$.
For each $i \in S$ and $f \in F$, denote by $\underline G(i,f)$ 
the set of
$a \in A$ for which 
$$
  {\underline v}(f) + {\underline h}(f)_i < r(i,a) + 
   \min_{q \in {\bf q}(i,a)}
   \sum_{j=1}^n q(j|i,a) {\underline h}(f)_j,
$$
where $\underline v(f)$ and 
$\underline h(f) = (\underline h(f)_1, \cdots , \underline h(f)_n)$ 
is solution of (2.5).
Let $g \in F$ be such that $g(i) \in \underline G(i,f)$ for any $ i$
 with
$\underline G(i,f) \neq \emptyset$ and $g(i) = f(i)$ for any $i$ with
$\underline G(i,f) = \emptyset$.
Then, we have the following.

\vspace{2ex}
\noindent
\textbf{Lemma 5.1} 
For any $f$ with $\underline G(i,f) \neq \emptyset$ for some 
$i \in S$,
$\underline v(f) \prec \underline v(g)$.

The following lemma is proved from the idea of policy improvement 
(cf.\cite{howard} ).

\vspace{2ex}
\noindent
\textbf{Lemma 5.2} 
The left side optimality equations (5.1) below determine
${\underline v}^*$ uniquely and ${\underline h} \in R^n$ up to an 
additive
constant.
$$
  {\underline v}^* + {\underline h}_i 
  = \max_{a \in A} \left(r(i,a) + 
  \min_{q \in \textbf{q}(i,a)} \sum_{j=1}^n q(j|i,a) 
  {\underline h}_j \right) \quad (1 \leq i \leq n).
\eqno{(5.1)} 
$$


Let, for each $i~(1\leq i\leq n)$,
$$
  A_i := arg\max_{a\in A} \left( r(i,a) + 
  \min_{q \in \textbf{q}(i,a)}
  \sum_{j=1}^n q(j|i,a) {\underline h}_j \right).
$$
For each $i \in S$ and $f \in F$ with $f(i) \in A_i$ for all 
$i \in S$,
denote by $\overline G(i,f)$ the set of $a \in A_i$ for which 
$$
  \overline v(f) + \overline h(f)_i < 
  r(i,a) + \max_{q\in \textbf{q}(i,a)} \sum_{j=1}^n q(j|i,a)
  \overline h(f)_j,
$$
where $\overline v(f)$ and 
$\overline h(f)=(\overline h(f)_1,\cdots,\overline h(f)_n)$ 
is a solution of (2.5).
Using $\overline G(i,f)$, we can prove the following.

\vspace{2ex}
\noindent
\textbf{Lemma 5.3} 
The right side optimality equations below determine
$\overline v^*$ uniquely and $\overline h \in R^n$ up to an 
additive constant.
$$
  \overline v^* + \overline h_i 
  = \max_{a \in A_i} \left(r(i,a)+\max_{q \in \textbf{q}(i,a)}
    \sum_{j=1}^n q(j|i,a) \overline h_j\right) \quad 
    (1 \leq i \leq n).
\eqno{(5.2)} 
$$



Let, for each $i (1 \leq i \leq n )$,
$$
  A_i^* := arg \max_{a \in A_i} \left(r(i,a) 
  + \max_{q \in \textbf{q}(i,a)}
    \sum_{j=1}^n q(j|i,a) \overline{h}_j \right).
$$

A policy $f^*$ with $f^*(i) \in A^*_i$ for all $i$ in $S$ is 
called a maximin policy.
Then, 
$(\mbox{\boldmath $v$}(f^*), \mbox{\boldmath $h$}(f^*))$ 
corresponding to a maximin policy is obviously 
a maximal solution of the optimality equation (4.6).
So, from Theorem 4.1,
we have the following Theorem.

\vspace{2ex}
\noindent
\textbf{Theorem 5.1} 
A maximin policy $f^*$ is Pareto optimal and 
$\mbox{\boldmath $v$}(f^*) = 
[{\underline v}^*{\bf e},{\overline v}^*{\bf e}]$.

\vspace{2ex}

Here we shall give a numerical example which illustrates Theorem 5.1.
For simplicity, let ${\underline q}^a_{ij} := \underline q(j|i,a),
\quad {\overline q}^a_{ij} := \overline q(j|i,a)$ and 
$r(a) := (r(1,a),r(2,a))$.
Consider the following controlled Markov set-chain model:
$S=\{1,2\},A=\{1,2\},$
$$
  ({\underline q}^1_{ij})
   = \left(\begin{array}{ll}
       \frac{1}{3} & \frac{1}{3} \\
       \noalign{\vskip0.2cm}
       \frac{1}{3} & \frac{1}{3} 
   \end{array}\right), \quad
  ({\overline q}^1_{ij}) 
   = \left(\begin{array}{ll}
       \frac{2}{3} & \frac{1}{2} \\
       \noalign{\vskip0.2cm}
       \frac{1}{2} & \frac{2}{3} 
     \end{array}\right),
$$
$$
  ({\underline q}^2_{ij}) = 
    \left(\begin{array}{ll}
      \frac{2}{5} & \frac{2}{5} \\
      \noalign{\vskip0.2cm}
      \frac{2}{5} & \frac{2}{5} 
    \end{array}\right), \quad 
  ({\overline q}^2_{ij}) = 
    \left(\begin{array}{ll}
      \frac{1}{2} & \frac{3}{5} \\
      \noalign{\vskip0.2cm}
      \frac{3}{5} & \frac{1}{2} 
    \end{array}\right),
$$
and $r(1)=(1,2), \quad r(2)=(1, 2.1)$.
Then, the equation (5.1) which $\underline v^*$ and $\underline
h=({\underline h}_1,{\underline h}_2)^\prime$ is given as follows :
$$
  \underline v^* + {\underline h}_1 = 
  \max
  \left\{\begin{array}{l}
    1 + \min\{
        ( 2 {\underline h}_1 + {\underline h}_2 ) / 3,
        ( {\underline h}_1 + {\underline h}_2 ) / 2, \\
    \noalign{\vskip0.2cm}
    1 + \min\{
        (2 {\underline h}_1 + 3 {\underline h}_2 )/ 5,
        ( {\underline h}_1 + {\underline h}_2) / 2
  \end{array}\right.
$$
and
$$
  \underline v^* + {\underline h}_2 = 
  \max
  \left\{\begin{array}{l}
    2 + \min\{
        ({\underline h}_1 + 2 {\underline h}_2 ) / 3,
        ({\underline h}_1 + {\underline h}_2 ) / 2, \\
    \noalign{\vskip0.2cm}
    2.1 + \min\{
        ( 3 {\underline h}_1 + 2 {\underline h}_2 ) / 5,
        ( {\underline h}_1 + {\underline h}_2 ) / 2.
  \end{array}\right.
$$

After a simple calculation, the solution of the above with 
${\underline
h}_1 =0$ becomes that $\underline v^*=1.5$ and 
$\underline h=(0,1)^\prime.$
Also, we easily find $A_1=\{2\}$ and $A_2=\{1,2\}.$
Similarly, by solving the equation ${\overline h}_1=0$, we get
$\overline v^*=23/14, {\overline h} = (0, 15/14)^\prime, 
A^*_1 = \{2\}$ and $A^*_2 = \{1\}$. 
So, by Theorem 5.1, $f^*$ with $f^*(1)=2$ and $f^*(2)=1$ is
Pareto optimal and $\mbox{\boldmath $v$}(f^*)=[(3/2){\bf e},
(23/14){\bf e}]$.





%%% References

\begin{thebibliography}{99}
\bibitem{bather}
Bather, J.; 
(1973)  
Optimal decision procedures for finite
Markov chains, Part II : Communicating systems, 
{\it Adv. Appl. Prob.}, \textbf{5}, pp.521-540.

\bibitem{blackwell}
Blackwell, D.;
 (1962) 
Discrete dynamic programming, 
{\it Ann. Math. Statist.} \textbf{33}, pp.719-726.

\bibitem{furu}
Furukawa,N.; (1980)
Characterization of Optimal Policies in Vector-valued
Markovian Decision Process, Math.Oper.Res. vol.5, pp.271-279.

\bibitem{hartfiel93}
Hartfiel, D. J.; (1993) Cyclic Markov set-chain. 
\textit{J.Stat.Comp.Simul.}, \textbf{46}, pp.145-167.


\bibitem{hartfiel94}
Hartfiel, D. J. and Seneta, E.; (1994) On the theory of
Markov Set-chains, \textit{Adv. Appl. Prob.} 26, pp.947-964.

\bibitem{hartfiel98}
Hartfiel, D. J.; (1998) Markov Set-chains, Springer-Verlag, Berlin.

\bibitem{hinderer}
Hinderer, K.; 
(1970) {\it Foundations of Non-Stationary
Dynamic Programming with Discrete Time Parameter.} Springer-Verlag, 
New York.

\bibitem{hosaka}
Hosaka, M. and Kurano, M.; 
Non-discounted Optimal policy in controlled
Markov Set-chains, \textit{Submitted to Journal of Opern. Res. of 
Japan}.

\bibitem{hhk}
Hosaka, M., Horiguchi, M. and Kurano, M.; 
Controlled Markov Set-chains under Average Criteria,
\textit{Submitted to the 7th Bellman Continuum}.


\bibitem{howard}
Howard, R.; (1960) 
{\it Dynamic Programming and Markov processes,} 
MIT Press, Cambridge MA.

\bibitem{kemeny}
Kemeny, J. G. and Snell, J. L.; (1960) 
{\it Finite Markov-Chains,} Van Nostrand, New York.

\bibitem{knh98}
Kurano, M., Nakagami, J. and Horiguchi, M.; (1998)
Controlled Markov Set-Chains with Set-valued rewards,
{\it To appear in the Proceeding of International Conference
on Nonlinear Analysis and Convex Analysis(NACA98).
}

\bibitem{kshh}
Kurano, M. , Song, J. , Hosaka, M. and Huang, Y.;(1998) 
Controlled
Markov Set-Chains with Discounting, {\it J.Appl.Prob.}, 
pp.293-302.

\bibitem{nenmaier}
Nenmaier, A.; (1984) New techniques for the analyses of
linear interval equations, {\it Linear Algebra Appli.} 58, 
pp.273-325.

\bibitem{puterman}
Puterman, M. L.; (1994) {\it Markov decision processes:
Discrete Stochastic Dynamic Programming,} John Wiley \& Sons, INC.

\bibitem{seneta}
Seneta, E. (1981) {\it Nonnegative Matrices and Markov
Chains,} Springer-Verlag, New York.

%\bibitem{song}
%Song, J. , Hosaka, M. and Kurano, M.; A Span Seminorm Approach
%to Controlled Markov Set-chains (Preprint).

\bibitem{taka84}
Takahashi,Y.; (1984)
Weak D-markov Chain and Its Application to a Queueing Network,
in G.Iazeolla, P.J.Courtois, and A.Hordijk eds.
\lq\lq Mathematical Computer Performance and Reliability\rq\rq,
North-Holland, Amsterdam, pp.153-165.

\bibitem{taka88}
Takahashi,Y.; (1988)
A Weak D-markov Chain approach to Tandem Queueing Network,
in G.Iazeolla, P.J.Courtois, and A.Hordijk eds.
\lq\lq Mathematical Computer Performance and Reliability\rq\rq,
North-Holland, Amsterdam, pp.151-159.


\bibitem{white}
White,D.J.; (1982)
Multi-objective infinite-horizon discounted Markov Decision
Processes,
J.Math.Anal.Appl., vol.89, pp.639-647.


\end{thebibliography}

\end{document}

