数理解析研究所講究録 1207 巻 2001 年 165-176

165
Markov decision processes with fuzzy rewards
千葉大学教育学部 蔵野正美 (Masami Kurano)

Faculty of Education, Chiba University
千葉大学理学部 安田正實 (Masami Yasuda)
千葉大学理学部 中神潤一 (Jun-ichi Nakagami)

Faculty of Science, Chiba University
北九州大学経済学部 吉田祐治 (Yuji Yoshida)

Faculty of Economics and Business Administration, Kitakyushu University

Abstract
In this paper, we consider the model that the information on the rewards invector-valued Markov decision processes includes imprecision or ambiguity. The
fuzzy reward model is analyzed as follows: The fuzzy reward is represented by the
fuzzy set on the multi-dimensional Euclidian space
and the infinite horizon fuzzy
expected discounted reward(FEDR) from any stationary policy is characterized as
aunique fixed point of the corresponding contractive operator. Also, we fined a
Pareto optimal policy which maximizes the infinite horizon FEDR over all stationary
policies under the pseudo order induced by aconvex cone
. As anumericalexample, the machine maintenance problem is considered.
$\mathrm{R}^{p}$$\mathrm{R}^{p}$

Keywords: Multi-dimensional fuzzy reward model, Markov decision process,
Pareto optimal, fuzzy optimality equation.
$AMS$ 1991 subject classification. Primary:;Secondary:.
$90\mathrm{c}40$$90\mathrm{c}39$

1. Introduction
In mathematical modeling in terms of Markov decision processes (MDPs, in short, cf. [2, 6,
12, 15]), it often occurs that the information on the reward function includes imprecisionor ambiguity. As an example, the reward earned in aday is about 700 dollars or closed
to 700 dollars. On the other hand, multi-criteria decision making is typically involving
flexible requirements for the optimality. In order to deal with uncertain data and flexible
requirements we can use afuzzy set representation (cf. [17]). In this paper, we consider
the case that the -valued rewards in standard MDPs are specified by fuzzy sets on Rp,
where
is apdimensional Euclidean space $(p\geq 1)$ .
Recently, Kurano et al [10] has introduced apseudo orderin the class of fuzzy, which is anatural extension of fuzzy $\max$ order (cf.[5, 16]) in fuzzy numbers
sets onon and induced by aconvex cone $K$ in . Under this pseudo order, we finedaPareto optimal policy which maximizes the infinite horizon fuzzy expected discounted
reward (FEDR) over all stationary policies. Associated with each stationary policy is acorresponding contractive operator on fuzzy sets, whose fixed point represents the infinite horizon FEDR. Moreover, the Pareto optimal policies are characterized by maxima$\mathbb{R}^{p}$$\mathbb{R}^{p}$$\neg K\prec$$\mathbb{R}^{p}$$\mathbb{R}$$\mathbb{R}^{p}$$\neg K\prec$

166
solutions of an optimal equation including efficient fuzzy set functions. As anumericalexample, the machine maintenance problem is considered.
For an interval or fuzzy treatment for MDPs with uncertain transition matrices, see[8, 9, 11] in which the intervals or fuzzy sets are used to describe uncertain transition
matrices. Also, for the optimization of fuzzy dynamic system refer to $[7, 19]$ .
This paper is organized as follows: In Section 2, we shall give some notations needed
for fuzzy treatments and apseudo order relation of fuzzy sets on
is reviewed referring
to Kurano etand the expectation of discrete fuzzy random variables is specified. In
Section 3, we describe the fuzzy reward model and specify the optimization problem. In
Section 4, the infinite horizon FEDR from astationary policy is given as afixed point of acorresponding operator, which is used to obtain the optimality equation and characterizeaPareto optimal policy in Section 5.
$\mathrm{R}^{p}$$\mathrm{a}1[10]$2. Preliminaries
by their membership functions
We write fuzzy sets on
and Zadeh [20] . The -cut $(\alpha\in[0,1])$ of the fuzzy set on$\tilde{s}:\mathrm{R}^{p}arrow[0,1]$$\mathrm{R}^{p}$$)$$\tilde{s}$$\alpha$and$\tilde{s}_{\alpha}:=\{x\in \mathrm{R}^{p}|\tilde{s}(x)\geq\alpha\}(\alpha>0)$(see Novak [13]is defined as$\tilde{s}_{0}:=\mathrm{c}1\{x\in \mathrm{R}^{p}|\tilde{s}(x)>0\}$where cl denotes the closure of the set. Afuzzy set$\mathrm{s}(\mathrm{X}\mathrm{x}+(1-\lambda)y)\geq\tilde{s}(x)\wedge\tilde{s}(y)$$\mathrm{R}^{p}$$x$$\tilde{s}$,,is called convex if$y\in \mathrm{R}^{p}$, A $\in[0,1]$ ,where $a \wedge b=\min\{a, b\}$ .
is aconvex set for all $\alpha\in[0,1]$ . Let
Note that is convex if and only if the -cutarebe the set of all convex fuzzy sets whose membership functions :and have acompact support. In theupper-semicontinuous and normal
be thedenotes the set of all fuzzy numbers. Let
one-dimensional case $p=1$ ,denotes the set
set of all compact convex subsets of Rp. We note that when $p=1$ ,of bounded and closed intervals in R.
are as follows: For
The definitions of addition and scalar multiplication on,
and A$\tilde{s}$$\tilde{s}_{\alpha}$$\alpha$$\tilde{s}$$F(\mathrm{R}^{p})$$\mathrm{R}^{p}arrow[0,1]$$( \sup_{x\in \mathrm{R}^{p}}\tilde{s}(x)=1)$$F(\mathrm{R})$$\mathrm{C}(\mathrm{R}^{p})$$\mathcal{F}(\mathrm{R})$$\mathcal{F}(\mathrm{R}^{p})$$\tilde{s},\tilde{r}\in F(\mathrm{R}^{p})$(2.1)$\geq 0$$( \tilde{s}+\tilde{r})(x):=\sup_{x_{1},x_{2}\in \mathrm{R}^{\mathrm{p}}}\{\tilde{s}(x_{1})\wedge\tilde{r}(x_{2})\}$(Ai)(x) $:=\{$(2.1)$\tilde{s}(x/\lambda)$$1_{\{0\}}(x)$

if
if

,

$\lambda>0$$(x\in \mathrm{R}^{p})$,$\lambda=0$

is an indicator. By using set operations $A+B:=\{x+y|x\in A, y\in B\}$ and, the following holds immediately.
,$\lambda A:=\{\lambda x|x\in A\}$ for any non-empty setswhere

$1\{\cdot\}(\cdot)$

$A$

(2.3)

$(\tilde{s}+\tilde{r})_{\alpha}=\tilde{s}_{\alpha}+\tilde{r}_{\alpha}$and$B\subset \mathrm{R}^{p}$$(\lambda\hat{s})_{\alpha}=\lambda\tilde{s}_{\alpha}$$(\alpha\in[0,1])$

.

167
Let

$\rho$

be the Hausdorff metric on$\mathrm{C}(\mathrm{R}^{p})$, that is, for$A$,$B\in \mathrm{C}(\mathrm{R}\mathrm{P})$,$\rho(A, B)=\max\{\max d(a, B), \max d(b, A)\}a\in Ab\in B$ ’is ametric in

where

$d$

this

to

$\rho$$\mathrm{C}(\mathbb{R}^{p})$and $d(x, D)= \min_{y\in D}d(x, y)$ for$\mathbb{R}^{p}$$x\in \mathrm{R}^{p}$and$D\in \mathrm{C}(\mathrm{R}^{p})$, we define, with abuse of notation, the Hausdorff metric on(2.4)$\rho(\overline{u},\tilde{v})=\sup_{\alpha\in[0,1]}\rho(\tilde{u}_{\alpha},\tilde{v}_{\alpha})$for$\tilde{u}$,$\tilde{v}\in \mathrm{C}(\mathrm{R}\mathrm{P})$. Extending$F(\mathrm{R}^{p})$

by

,

where
and
are -cuts of and respectively.
Then, the following facts are well known.
$\overline{u}_{\alpha}$$\tilde{u}$$\tilde{v}_{\alpha}$$\tilde{v}$$\alpha$Lemma 2.1 (cf. [14]).

The metric space

Lemma 2.2 (cf. [3]).

If ,

(i)

$\rho(\lambda\overline{u}, \lambda\tilde{v})=\lambda\rho$$\overline{u}$$\overline{v},\tilde{u’},\tilde{v’}$( , i) for all

and$\lambda\geq 0$$\mathrm{i}$$(F(\mathbb{R}^{p}), \rho)$$\overline{r}\in \mathcal{F}(\mathbb{R}^{p})$is complete.

, then.
,(ii)$\rho(\overline{u}+\overline{u’}, \tilde{v}+\tilde{v’})\leq\rho(\overline{u},\tilde{v})+\rho(\overline{u’},\tilde{v’})$

(iii)

.

$\rho(\overline{r}+\overline{u}, \overline{r}+\overline{v})--\rho(\overline{u},\overline{v})$Here, we pick up apseudo order relation introduced in Kurano et al [10], which isnecessary for our problem formulation in the sequel. The partial order relationon,
is defined as follows: For any,means that.
and
Let $K$ be anon-empty cone of Rp. Using this $K$ , we can define apseudo order relation
byon
if and only if $y-x\in K$ . By the pseudo order
on , apseudoorder
on
is defined as follows.
$\neg\prec 1$$[c_{1}, c_{2}]$$\mathrm{C}(\mathbb{R})$$c_{2}\leq c_{2}’$$c_{1}\leq c_{1}’$$\mathbb{R}^{p}$$\neg K\prec$$\neg K\prec$For ,$\overline{s}$$[c_{1}, c_{2}]\neg 1\prec[d_{1}, \phi]$$[d_{1}, c_{2}’]\in \mathrm{C}(\mathbb{R})$$x\neg\prec_{K}y$$\neg K\prec$$\mathbb{R}^{p}$$\mathcal{F}(\mathbb{R}^{p})$$\overline{r}\in \mathcal{F}(\mathbb{R}^{p})$(F.a) For any(F.b) For any,$\tilde{s}\prec_{\neg K}\overline{r}$$x\in \mathbb{R}^{p}$$y\in \mathbb{R}\mathrm{p}$means the following (F.a) and (F.b) :, there exists$y\in \mathbb{R}^{p}$such that$x\neg\prec_{K}y$and$\tilde{s}(x)\leq\overline{r}(y)$.

, there exists$x\in \mathbb{R}^{p}$such that$x\neg K\prec y$and$\overline{s}(x)\geq\tilde{r}(y)$.

is apartial order and called the fuzzyonWhen $p=1$ and $K=[0, \infty)$ , the,$\max$ order (cf. [5, 16]) defined by. That is, for ,means thatfor all $\alpha\in[0,1]$ , where the -cuts of and are denoted respectively by
and
.
and
Define the dual cone of acone $K$ by$F(\mathrm{R})$$\neg K\prec$$\tilde{s}$$\neg 1\prec$$\overline{s}$$\tilde{s}_{\alpha}^{U}\leq\tilde{r}_{\alpha}^{U}$$\overline{s}_{\alpha}=[\overline{s}_{\alpha}^{L},s_{\alpha}]\triangleleft\gamma$$a\in \mathbb{R}^{p}$(2.5)$\tilde{s}_{\alpha}^{L}\leq\overline{r}_{\alpha}^{L}$$\tilde{r}$$\tilde{r}_{\alpha}=[\overline{r}_{\alpha}^{L}, \tilde{r}_{\alpha}^{U}]${$a\in \mathbb{R}^{p}|a\cdot x\geq 0$

denotes the inner product on, we define$x\cdot y$$\tilde{s}\prec_{\neg 1}\overline{r}$$\alpha$$K^{+}:=$

where$\tilde{r}\in F(\mathbb{R})$$\mathrm{R}^{p}$for all $x\in K$ },

for ,
$x$

$y\in \mathbb{R}^{p}$$a\cdot A:=\{a\cdot x|x\in A\}(\subset \mathbb{R})$.

. For asubset$A\subset \mathbb{R}^{p}$

and

168
The definition (2.5) means the projection of on the extended line of the vector if$a\cdot a=1$ . It is trivial that.
ifandthrough theonon
is characterized by
The pseudo order relation
projection (2.5), where the proof is in [10].
$A$$a\cdot A\in \mathrm{C}(\mathrm{R})$Let$\in K^{+}$$\mathcal{F}(\mathrm{R})$$\tilde{u},\tilde{v}\in F(\mathrm{R}^{p})$and$\alpha\in[0,$. Then,$F(\mathbb{R})$$\neg\prec 1$$\overline{u}\prec_{\neg K}\tilde{v}$on$F(\mathrm{R}^{p})$if and only if$a\cdot\overline{u}_{\alpha}\neg\prec_{1}a\cdot\overline{v}_{\alpha}$1].

Let asequence. Tien, it holds that

Lemma 2.4 [10].

$a\in \mathbb{R}^{p}$$A\in \mathrm{C}(\mathrm{R}^{p})$$F(\mathrm{R}^{p})$$\neg\prec K$

Lemma 2.3 [10].
onfor all a$a$$\{\tilde{u}_{l}\}\subset \mathcal{F}(\mathrm{R}^{p})$$\tilde{u}=\lim_{larrow\infty}\tilde{u}_{l}\in F(\mathrm{R}^{p})$be such that$\tilde{u}_{1}\neg\prec_{K}\tilde{u}$$\tilde{u}_{1}\neg\prec K\tilde{u}_{2}\neg\prec K\ldots$

, and

.

The following lemma is used in the sequel.
Lemma 2.5.

Let A, B$\in \mathrm{C}(\mathrm{R}^{p})$and a$\in \mathrm{R}^{p}$. Then, we have:(i) a. $(A+B)=a$ . $A+a$ . B,(ii) a.

$(\lambda A)=\lambda(a$.A) for all$\lambda\geq 0$.

, so that, $a\cdot(A+B)=[a\cdot(x^{L}+y^{L}), a\cdot(x^{U}+y^{U})]$,
Proof. For ,. andfor some $x^{L},x^{U}\in A$ and , $y^{U}\in B$ . Since $(x^{L}+y^{L})=a\cdot$ $x^{L}+a\cdot$ ,, it holds $a\cdot(x^{L}+y^{L})\in a\cdot A+a\cdot B$ . Similarly, $a\cdot(x^{U}+y^{U})\in a\cdot A+a\cdot B$ . Thus,,$a\cdot(A+B)\subset a\cdot A+a\cdot B$ . Conversely, if we set
and$A+a\cdot$$a\cdot(A+B)=[a\cdot(x^{L}+y^{L}),a\cdot(x^{U}+y^{U})]$ , which implies$(A+B)$ .
Also, (ii) clearly holds, as required.
$A$$B\in \mathrm{C}(\mathrm{R}^{p})$$a\cdot(A+B)\in \mathrm{C}(\mathrm{R})$$y^{L}$$y^{L}$$a\cdot$$a\cdot x^{L}\in a$$A$$a\cdot y^{L}\in a\cdot B$$a\cdot A=[a\cdot x^{L}, a\cdot x^{U}]$$a\cdot$$a\cdot$$B=[a\cdot y^{L}, a\cdot y^{U}]$$B\subset a\cdot$$\square$

In order to formulate the optimization problem in the next section, we need the conceptof the expectation of discrete fuzzy random variables.
:
adiscrete fuzzy random
Let $(\Omega, B, P)$ be aprobability space and. Then, we define the expectation of byvariable with its range$\tilde{X}$$\Omegaarrow \mathcal{F}(\mathrm{R}^{p})$$\overline{X}$$\{\tilde{s}_{1}, \tilde{s}_{2}, \cdots, \tilde{s}_{l}\}\subset \mathcal{F}(\mathrm{R}^{p})$(2.6)$E[ \tilde{X}]=\sum_{\dot{|}=1}^{l}\tilde{s}_{\dot{1}}P(\tilde{X}=\tilde{s}_{\dot{1}})$.

Note that the expectation in (2.6) is defined in (2.1) and (2.2). The definition of (2.6) iscorresponding to the discrete case of the integral of aset-valued function (cf. [1]) or the
expectation of general fuzzy random variables (cf. [14]).
The following clearly holds.
Lemma 2.5.
subsets of$\mathcal{F}(\mathrm{R}^{p})$

(i)

(ii)

(iii)

If and, then$\tilde{X}$$E[\tilde{X}]\in F(\mathrm{R}^{p})$$\tilde{\mathrm{Y}}$are discrete fuzzy random variables whose ranges are finite,$E[\tilde{X}+\tilde{\mathrm{Y}}]=E[\tilde{X}]+E[\tilde{\mathrm{Y}}]$$E[\lambda\tilde{X}]=\lambda E[\tilde{X}]$for all,$\lambda\geq 0$.

169
3. The fuzzy reward modeland specify our optimization
In this section, we formulate MDPs with fuzzy rewards on
problem. Let and be finite sets denoted by $S=\{1,2, \cdots,n\}$ and $A–\{1,2, \cdots, k\}$ .
The sequential decision model consists of four objects:$\mathrm{R}^{p}$

$A$

$S$

$(S, A, \{q_{\dot{l}j}(a);i,j\in S, a\in A\},\tilde{r})$,where and denote the state and action spaces respectively andis the law of motion, i.e., for eachis afuzzy reward function on $S\cross A$ and$(i, a)\in S\cross A$ , $q_{ij}(a)\geq 0$ and $\sum_{j\in S}q_{ij}(a)=1$ .
When the system is in state $i\in S$ and we take action $a\in A$ , the present state moves toand we receive
anew state $j\in S$ selected according to the probability distribution. This process is then repeated from the new state $j\in S$ .
afuzzy reward
andThe sample space is the product space $\Omega=(S\cross A)^{\infty}$ such that the projection
on the -th factor and describe the state and the action at the -th time of theprocess $(t=1,2, \ldots)$ .
to . Apolicy
is asequence
We denote by $F$ the set of all functions fromof functions with $f_{t}\in F(t\geq 1)$ . Let be the class of policies. We denotewith $f_{t}=f$ for all $t\geq 1$ and some $f\in F$ . Such apolicy is
the policy
bycalled stationary and denoted simply by $f\in F$ . The set of all stationary policies will be. Then, for each policy $\pi\in\Pi$ and starting state $i\in S$ , we can define thedenoted byon in ausual way. Here, we consider the expected fuzzy reward
probability measure.
in which the future reward is discounted with afactor
For any policy $\pi\in\Pi$ and starting state $i\in S$ , let
$A$

$S$

$\overline{r}=\overline{r}(i, a)\in F(\mathbb{R}^{p})$$\{q_{ij}(a)\}$$q_{i}.(a)$$\overline{r}(i, a)\in F(\mathrm{R}^{p})$$X_{t}$

$A$

$S$

$t$

$\triangle_{t}$

$t$

$A$

$S$

$\pi$

$\Pi$

$(f_{1}, f_{2}, \ldots)$$(f_{1}, f_{2}, \ldots)$$f^{\infty}$$\Pi_{F}$$P_{\pi}^{\dot{1}}$$\Omega$$\beta(0<\beta<\mathrm{I})$(3.1)$\tilde{\phi}_{T}(i, \pi)=\sum_{t=1}^{T}\beta^{t-1}E_{\pi}^{i}[\overline{r}(X_{t}, \Delta_{t})]$,and its expectation of fuzzy randomis the expectation with respect towhere
for $i\in S$ ,variable is defined by (2.6). We note from Lemma 2.5 thatand $T\geq 1$ .
In order to rewrite (3.1) by using vectors and matrices, we shall introduce some notabe the set of all -dimensional column vectors whose elements are intions. Let, i.e.,$P_{\pi}^{i}$$E_{\pi}^{i}$$\phi\sim\tau(i, \pi)\in \mathcal{F}(\mathbb{R}^{p})$$\pi\in\square$$n$$\mathcal{F}(\mathbb{R}^{p})^{n}$$\mathcal{F}(\mathbb{R}^{p})$$\mathcal{F}(\mathbb{R}^{p})^{n}:=\{\tilde{u}=(\tilde{u}_{1}, \overline{u}_{2}, \ldots,\overline{u}_{n})’|\tilde{u}_{i}\in F(\mathbb{R}^{p}), 1\leq i\leq n\}$,where denotes the transpose of avector .
is defined (with abuse of notation) by
The Hausdorff metric on
$d$

$d’$

$\rho$$F(\mathrm{R}^{p})^{n}$$\rho(\tilde{u},\tilde{v})=\max_{1\leq i\leq n}\rho(\tilde{u}_{\dot{l}},\overline{v}_{\dot{1}})$

,

170
,
where
and
Then, from Lemma 2.1, we observe that the metric space
For a $n\cross n$ stochastic matrix
andproduct
will be defined by$\tilde{u}=$$(\tilde{u}_{1},\tilde{u}_{2}, \ldots, \tilde{u}_{n})’$$\tilde{v}=(\tilde{v}_{1}, \tilde{v}_{2}, \ldots, \tilde{v}_{n})’\in F(\mathrm{R}^{p})^{n}$$\rho(\tilde{u}_{\dot{1}}, \tilde{v}_{\dot{l}})$$(F(\mathrm{R}^{p})^{n}, \rho)$$Q=(q_{\dot{l}j})$is defined in (2.4).
is complete.
, the$\tilde{u}=(\tilde{u}_{1},\tilde{u}_{2}, \ldots,\tilde{u}_{n})’\in F(\mathbb{R}^{p})^{n}$$Q\tilde{u}\in F(\mathrm{R}^{p})^{n}$(3.2)$(Q \overline{u}):=\sum_{j=1}^{n}q_{\dot{\iota}j}\overline{u}_{j}(1\leq i\leq n)$.

Here, we associate with each $f\in F$ the -dimensional column fuzzy vector
whose -th element isand thestochastic matrix $Q(f)$ whose $(i, j)$. For each policy $\pi\in\Pi$ , letelement is
$n$

$i$

$\tilde{r}(f)\in F(\mathbb{R}^{p})^{n}$$n\cross n$$\tilde{r}(i, f(i))\in \mathcal{F}(\mathrm{R}^{p})$$q_{\dot{*}j}(f(i))$$\phi\sim T(n, \pi))\in F(\mathrm{R}^{p})^{n}(T\geq 1)$$\tilde{\phi}_{T}(\pi)=(\tilde{\phi}_{T}(1, \pi),\tilde{\phi}(2, \pi),$$\ldots,$.

Then, we have the following.

Lemma 3.1. For any $\pi=(f_{1}, f_{2}, \ldots)\in\Pi$ , we have:(i)is described by the following matrix representation.
$\tilde{\phi}_{T}(\pi)$(3.3)$\tilde{\phi}_{T}(\pi)=\tilde{r}(f_{1})+\beta Q_{1}(\pi)\tilde{r}(f_{2})+\cdots+\beta^{T-1}Q_{T-1}(\pi)\tilde{r}(f_{T})(T\geq 1)$,

where $Q_{t}(\pi)=Q(f_{1})\cdots$ $Q(f_{t})(t\geq 1)$ .
(ii)$\{\tilde{\phi}(\pi)\}_{T=1}^{\infty}$

is aCauchy sequence.

Proof. By the definition, for any $t\geq 0$ we have that$Q_{t}(\pi).\cdot j\tilde{r}(j, f_{t}(j))$$E_{\pi} \dot{.}=\sum_{j\in S}P_{\pi}\dot{.}(X_{t}=j)\tilde{r}(j, f_{t}(j))=\mathrm{I}$,which clearly leads to (3.2).
For any $T>H$ , it holds from Lemma 2.2 that$\rho(\tilde{\phi}_{T}(\pi),\tilde{\phi}_{H}(\pi))\leq\rho(\tilde{0},\sum_{t=H+1}^{T}\beta^{t-1}Q_{t-1}\tilde{r}(f_{t}))$,$= \beta^{H}\rho(\tilde{0},\sum_{t=H+1}^{T}\beta^{t-H-1}Q_{t}\tilde{r}(f_{t}))\leq\beta^{H}\rho(\tilde{0}, \tilde{r})/(1-\beta)$

where$0\equiv 1\{0\}$. This implies (ii), as required.

$\square$By Lemma 3.1, the infinite horizon FEDR fromcan be defined by$\pi$$\tilde{\phi}(\pi)=\lim_{Tarrow\infty}\tilde{\phi}_{T}(\pi)$.

on
In order to specify our optimization problem, we extend the pseudo order,
as follows: For
given in the preceding section to that on
for all $i(1\leq i\leq n)$ .
means
over all policies $\pi\in\Pi$ with
Then, our problem is to maximize the.
respect to the pseudo order$\neg\prec K$$F(\mathrm{R}^{p})^{n}$$\tilde{v}=$$(\tilde{v}_{1}, \tilde{v}_{2}, \ldots, \tilde{v}_{n})’\in F(\mathrm{R}^{p})^{n},\tilde{u}\prec_{\neg K}\tilde{v}$$\tilde{u}_{\dot{l}}\neg\prec_{K}\tilde{v}_{\dot{l}}$$\tilde{\phi}(\pi)\in F(\mathrm{R}^{p})^{n}$$\neg\prec K$$\mathcal{F}(\mathbb{R}^{p})$$\tilde{u}=(\overline{u}_{1},\overline{u}_{2}, \ldots,\tilde{u}_{n})’$171
4. Stationary policies and operators
In this section, the infinite horizon FEDR from astationary policy is given as auniquefixed point of acorresponding operator. Associated with each $f\in F$ is acorresponding
operator:
defined as follows: For,$U_{f}$$\mathcal{F}(\mathbb{R}^{p})^{n}arrow F(\mathrm{R}^{p})^{n}$(4.1)$\tilde{u}\in F(\mathrm{R}^{p})^{n}$$U_{f}\tilde{u}=\overline{r}(f)+\beta Q(f)\tilde{u}$,where the arithmetics in (4.1) are defined in the preceding sections.
Since it holds that
any
and A
lemma is easily proved.
$\lambda(\tilde{c}+\tilde{d})=\lambda\overline{c}+\lambda\overline{d}\mathrm{f}\mathrm{o}\mathrm{r}$Lemma 4.1.

If

$Q$

is

$n\cross n$$\overline{c},\tilde{d}\in \mathcal{F}(\mathrm{R}^{p})$stochastic matrix and ,$\tilde{u}$$\overline{v}\in F(\mathbb{R}^{p})^{n}$$\geq 0$, the following, then it holds that.

$Q(\tilde{u}+\tilde{v})=Q\overline{u}+Q\tilde{v}$

For any policy $\pi=$, let $\pi^{-l}=(f_{l+1}, fi_{+2}, \ldots)$ for eachis recursively described.
$(f_{1}, f_{2}, \ldots)$$\mathit{1}\geq 1$. The sequence$\{\overline{\phi}_{T}(\pi)\}_{T=1}^{\infty}$

For any policy $\pi=$Lemma 4.2.
(4.2)$(f_{1}, f_{2}, \ldots)$$\tilde{\emptyset}\tau(\pi)=Uf_{1}Uf_{2}\ldots$

Proof. Since$\overline{\phi}_{1}(\pi^{-1})=\tilde{r}(f_{2})$, we have$U_{f\iota}\overline{\phi}\tau-l(\pi^{-l})$for each $l\geq 1$ .

, we have.

$\tilde{\phi}_{2}(\pi)=\tilde{r}(f_{1})+\beta Q(f_{1})\overline{r}(f_{2})=U_{f_{1}}\tilde{\phi}_{1}(\pi)$

For $T=3$ , from Lemma 4.1, we have that$\overline{\phi}_{3}(\pi)=\overline{r}(f_{1})+\beta Q(f_{1})\tilde{r}(f_{2})+\beta^{2}Q(f_{1})Q(f_{2})\overline{r}(f_{3})$$=\tilde{r}(f_{1})+\beta Q(f_{1})(\tilde{r}(f_{2})+\beta Q(f_{2})\tilde{r}(f_{3}))=U_{f_{1}}\overline{\phi}_{2}(\pi^{-1})$

By induction on$T$

and , we can easily prove (4.2).
$l$Here are some basic properties ofLemma 2.2.
Lemma 4.3.

For $f\in F$ ,$U_{f}$$U_{f}$$\square$. The following lemma is easily proved fromis acontraction with modulus , $i.e.$ ,$\beta$$\rho(Uf\tilde{u}, Uf\overline{v})\leq\beta\rho(\overline{u}, \tilde{v})$,for$\tilde{u},\overline{v}\in F(\mathbb{R}^{p})^{n}$.

Lemma 4.4.
Let $K$ be aconvex cone of . Then, for $f\in F$ ,respect to the pseudo order, i.e., for any ,onholds that.
$\mathbb{R}^{p}$$\neg K\prec$$U_{f}\overline{u}\prec_{\neg K}U_{f}\overline{v}$.

$F(\mathbb{R}^{p})^{n}$$\tilde{u}$$U_{f}$

is monotone with
, it
with

$\tilde{v}\in F(\mathbb{R}^{p})^{n}$$\tilde{u}\prec_{\neg K}\overline{v}$172
for all $a\in K$ ,Proof. Prom Lemma 2.3, it suffices to show that.
$\alpha\in[0,1]$ and $i=1,2$ ,is the -cut of the -th element of, , where
Applying Lemma 2.5, we get$a\cdot$$\ldots$

(4.2)

$n$

$(U_{J}\tilde{v}):,\alpha$$(U_{f}\tilde{u}):,\alpha\neg\prec 1a\cdot$$(U_{f}\tilde{v})_{i,\alpha}$$i$$\alpha$$U_{f}\overline{v}$$a \cdot(U_{f}\tilde{v}):,\alpha=a\cdot\tilde{r}(i, f(i))_{\alpha}+\beta\sum_{j=1}^{n}q_{\dot{l}j}(f(i))(a\cdot\tilde{u}_{j,\alpha})$.

for all $j=1,2$ ,implies from Lemma 2.3 that
. This completes the proof.
implies thatSince$a\cdot$$\tilde{u}\prec_{\neg K}\overline{v}$$a\cdot(U_{f}\tilde{u})_{j,\alpha}\neg\prec_{1}a\cdot$$\tilde{u}_{j,\alpha}\neg\prec_{1}a\cdot$$\tilde{v}_{j,\alpha}$$\ldots$, , (4.2)$n$$\square$$(U_{f}\tilde{v})_{j,\alpha}$

is a
for all $T\geq 2$ . As $Tarrow\infty$ in the above,
By Lemma 4.2,
is immediately
fixed point of . Thus, noting Lemma 4.3, the characterization of
formulated as atheorem.
$\overline{\phi}(f)$$\tilde{\phi}_{T}(f)=U_{f}\tilde{\phi}_{T-1}(f)$$\tilde{\phi}(f)$$U_{f}$For any stationary policy $f\in F,\tilde{\phi}(f)$ is aunique solution of the
Theorem 4.1.
following equation:(4.3)$\tilde{u}=U_{f}\tilde{u}$,$\tilde{u}\in F(\mathrm{R}^{p})^{n}$.

Note that (4.3) can be rewritten as the -cut equation:$\alpha$

(4.4)

where

$\tilde{u}_{\alpha}=\tilde{r}(f)_{\alpha}+\beta Q(f)\tilde{u}_{\alpha}$$\tilde{u}_{\alpha}=$$\mathrm{C}(\mathrm{R}^{p})^{n}$$(\tilde{u}_{1,\alpha},\tilde{u}_{2,\alpha}, \ldots,\tilde{u}_{n,\alpha})’$and,$\alpha\in[0,1]$,$\tilde{r}(f)_{\alpha}=(\tilde{r}(1, f(1))_{\alpha},\tilde{r}(2, f(2))_{\alpha},$$\ldots,\tilde{r}(n, f(n))_{\alpha})’\in$.

Prom acontraction ofCorollary 4.1.

$U_{f}$, the next corollary holds.

For any stationary policy $f\in F$ ,$\tilde{\phi}(f)=\lim_{larrow\infty}U_{f}^{l}\tilde{u}$$(\tilde{u}\in F(\mathrm{R}^{p})^{n})$.

As asimple example, we consider afuzzy treatment for amachine maintenance problem dealt with in ([12], p.l, p.17-18).
amachine maintenance problem. Amachine can be operated synchronously, say,once an hour. At each period there are two states; one is operating(state 1), and theother is in failure(state 2). If the machine fails, it can be restored to perfect functioning
by repair. At each period, if the machine is running, we earn the fuzzy return of (2,3,4)
dollars per period; the probability of being in state 1at the next step is 0.7 and theprobability of moving to state 2is 0.3 where for any $a<b<c$ , the fuzzy number $(a, b, c)$
on is defined by$\mathrm{R}$$(a, b, c)(x)=\{$$(x-a)/(b-a)\vee \mathrm{O}$$(x-c)/(b-c)\vee \mathrm{O}$

if $x\leq b$ ,if $b\leq x$ .

173
If the machine is in failure, we have two actions to repair the failed machine; one is ausual
repair, denoted by 1, that yields the fuzzy reward $(-2,$ $-1, 0)$ dollars with the probability
0.4 moving in state 1and the probability 0.6 being in state 2; another is arapid repair,denoted by 2, that requires the ffizzy reward $(-3,$ $-2,$ $-1)$ dollars with the probability 0.6
moving in state 1and the probability 0.4 being in state 2.
For the model considered, $S=\{1,2\}$ and there exists two stationary policies, $F=$
with $f_{1}(2)=1$ and $f_{2}(2)=2$ , where
denotes apolicy of the usual repair andapolicy of the rapid repair. The state transition diagrams and fuzzy reward vector for
two policies are shown in Figure 1.
$\{f_{1}, f_{2}\}$$f_{1}$$f_{2}$( )$\overline{r}$(a) Usual repair$f_{1}$

$=$

$($

(–( )
$22$

$-13,)$$4)0)$ $)$$f_{1}$$\overline{r}(f_{2})=(\begin{array}{llll}( 2 3 4)(-3,-2 -1)\end{array})$(b) Rapid repair$f_{2}$

Figure.l Transition diagrams and fuzzy rewards.
Applying Theorem 4.1, we obtain the infinite horizon FEDR as aunique solution of(4.3). So, putting,$\tilde{\phi}(f_{1})_{\alpha}=([x_{\alpha}^{1}, y_{\alpha}^{1}], [x_{\alpha}^{2}, y_{\alpha}^{2}])’$

the -cut interval equations (4.4) with $\beta=0.9$ become:$\alpha$$x_{\alpha}^{1}=2+\alpha+0.9(0.7x_{\alpha}^{1}+0.3x_{\alpha}^{2})$$y_{\alpha}^{1}=4-\alpha+0.9(0.7y_{\alpha}^{1}+0.3y_{\alpha}^{2})$$x_{\alpha}^{2}=-2+\alpha+0.9(0.4x_{\alpha}^{1}+0.6x_{\alpha}^{2})$$y_{\alpha}^{2}=-\alpha+0.9(0.4y_{\alpha}^{1}+0.6y_{\alpha}^{2})$After asimple calculation, we obtain$\tilde{\phi}(f_{1})_{\alpha}=([10\alpha+\frac{380}{73}, \frac{1840}{73}-10\alpha],$ $[10 \alpha-\frac{20}{73}, \frac{1440}{73}-10\alpha])’$which leads to$\overline{\phi}(f_{1})=((\frac{380}{73}, \frac{1110}{73}, \frac{1840}{73}),$$(- \frac{20}{73}, \frac{710}{73}, \frac{1440}{73}))’$

.

,

174
5. Pareto optimality
Here, we confine our attention to the class of stationary policies, which simplifies ouris called Pareto
discussion in the sequel. Let $K$ be aconvex cone in . Apolicy. In this section, we derive
optimal if there does not exist $f\in\Pi_{F}$ such thatthe optimal equation, by which Pareto optimal policies are characterized.
The following important result is crucial to the development in the characterizationof Pareto optimality.
$f^{*}\in\Pi_{F}$$\mathrm{R}^{p}$$\tilde{\phi}(f^{*})\neg\prec_{K}\tilde{\phi}(f)$Lemma 5.1. For any , $g\in F$ , suppose that
$f$

(5.1)
Then, it holds that$U_{g}\tilde{\phi}(f)$$\tilde{\phi}(f)$$\{\begin{array}{l}\prec_{\backslash K}\prec_{K}\end{array}\}$(5.2)$\phi-(g)$$\tilde{\phi}(f)$$\{\begin{array}{l}\prec_{\backslash K}\prec_{K}\end{array}\}$Proof. Suppose that$\phi\sim(f)\{_{\prec\kappa}^{\prec}\backslash K\}U_{g}\tilde{\phi}(f)$$\tilde{\phi}(f)$$\{\begin{array}{l}\prec_{\backslash K}\prec_{K}\end{array}\}$So, taking the limit in the above as
2.4.

.

.

. Then, we have from Lemma 4.3 that$U_{g}\tilde{\phi}(f)$$larrow\infty$$\neg\prec$$U_{g}^{l}\tilde{\psi}(f)$$(l\geq 2)$,, (5.2) follows from Corollary 4.1 and Lemma$\square$. Apoint
is called an efficient element
Let $D$ be an arbitrary subset of
if and only if it holds that there does not exist
onof $D$ with respect tothe set of all elements of $D$ efficient with respect. We denote bysuch that. Note that
, let
. For anyonto$\tilde{u}\in D$$F(\mathrm{R}^{p})^{n}$$\tilde{u}\prec_{K}\tilde{v}$$\neg\prec K$$\mathrm{e}\mathrm{f}\mathrm{f}(D)$$\tilde{u}\in F(\mathbb{R}^{p})^{n}$$F(\mathrm{R}^{p})^{n}$$\mathcal{U}(\tilde{u})\subset \mathcal{F}(\mathrm{R}^{p})^{n}$$\overline{v}\in D$$F(\mathrm{R}^{p})^{n}$$\neg\prec K$$\mathcal{U}(\tilde{u}):=\mathrm{e}\mathrm{f}\mathrm{f}(\{U_{f}\tilde{u}|f\in F\})$.

Here, we consider the following fuzzy equation including efficient fuzzy functions:
on$\mathcal{U}(\cdot)$$F(\mathrm{R}^{p})^{n}$(5.3)$\tilde{u}\in \mathcal{U}(\tilde{u})$,$\tilde{u}\in F(\mathrm{R}^{p})^{n}$.

The equation (5.3) is called an optimality equation, by which Pareto optimal policies arecharacterized. Asolution of (5.3) is called maximal if there does not exist any solution,. Pareto optimal policies are characterized by maximalof (5.3) such thatsolutions of the optimality equation (5.3).
$\tilde{u}$$\tilde{u}$$\tilde{u}\prec_{K}\tilde{u}’$Theorem 5.1. A policy is Pareto optimal if and only $ifa$ fixed point of the corresponding, is amaximal solution to the optimal equation (5.3).
$f$$U_{f},\tilde{\phi}(f)$Proof. The proof of “only if “part is easily obtained from Lemma 5.1. In order to proveis amaximal solution of (5.3) but is not Pareto optimal.
“if “part, suppose that.
Then, there exists $f^{(1)}\in F$ such that$\tilde{\phi}(f)$$f$$\tilde{\phi}(f)\prec_{K}\tilde{\phi}(f^{(1)})$

175
Now, suppose that
. This assumption assures that there exists$f^{(2)}\in F$ satisfying, which implies from (5.1) that
. By repeating this method successively, we come to the conclusion that there
exists $f^{(l)}\in F$ such thatandsatisfies (5.3), which contradicts
thatis maximal, as required. Cl$\tilde{\phi}(f^{(1)})\not\in \mathrm{e}\mathrm{f}\mathrm{f}(\tilde{\phi}(f^{(1)}))$$\overline{\phi}(f^{(1)})\prec_{K}U_{f}(2)\tilde{\phi}(f^{(1)})$$\tilde{\phi}(f^{(1)})\prec_{K}$$\overline{\phi}(f^{(2)})$$\tilde{\phi}(f)\prec_{K}\tilde{\phi}(f^{(l)})$$\tilde{\phi}(f^{(l)})$$\overline{\phi}(f)$Remark. For vector-valued discounted MDPs, Furukawa[4] and White[18] had derived
the optimality equation including efficient set-function on Rp, by that Pareto optimal
policies are characterized. The form of the optimal equation (5.3) is corresponding to afuzzy version of MDPs.
For the machine maintenance problem given in Section 4, we find that$U_{f_{2}} \tilde{\phi}(f_{1})=((\frac{380}{73}, \frac{1110}{73}, \frac{1840}{73})$,$(- \frac{21}{73}, \frac{709}{73}, \frac{1439}{73}))’$,

Recall that$U_{f_{1}} \tilde{\phi}(f_{1})=\overline{\phi}(f_{1})=((\frac{380}{73}, \frac{1110}{73}, \frac{1840}{73}),$$(- \frac{20}{73}, \frac{710}{73}, \frac{1440}{73}))’$,

which satisfies,
is the fuzzy $\max$ order onand corresponding toin case of $K=[0, \infty)$ .
Thus,, so that from Theorem 5.1
is Pareto optimal.
In fact, we can find, by solving (4.3) or (4.4) for , that$U_{f_{2}}\overline{\phi}(f_{1})\prec_{1}\overline{\phi}(f_{1})$$\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\prec_{1}$$F(\mathbb{R})^{2}$$\neg\prec K$$\overline{\phi}(f_{1})\in \mathrm{e}\mathrm{f}\mathrm{f}(\{U_{f}\overline{\phi}(f_{1})|f\in F)$$f_{1}$$f_{2}$$\overline{\phi}(f_{2})=((\frac{470}{91}, \frac{1380}{91}, \frac{2290}{91}),$$(- \frac{30}{91}, \frac{880}{91}, \frac{1790}{91}))’$, and$\overline{\phi}(f_{2})\prec_{1}\overline{\phi}(f_{1})$.

References[1] Aumann, R. J., Integrals of set-valued functions, J. Math. Anal. Appl. 12 (1965),
1-12.
[2] Blackwell, D., Discrete dynamic programming, Ann. Math. Stat. 33 (1962), 719-726.

[3] Diamond, P. and Kloeden, P., Metric Spaces of Fuzzy Sets, Theorry and Applications,(1994), World Scientific.
[4] Furukawa, N., Characterization of optimal policies in vector-valued Markovian decision processes, Math. Oper.
. 5 (1980), 271-279.
${\rm Res}$[5] Furukawa, N., Parametric orders on fuzzy numbers and their roles in fuzzy optimization problems, Optimization 40 (1997), 171-192.
[6] Howard, R., Dynamic Programming and Markov processes, (1960), MIT Press, Cambridge MA.

176[7] Kurano, M., Yasuda, M., Nakagami, J. and Yoshida, Y. Markov-type fuzzy decision
processes with adiscounted reward on aclosed interval, European J. Oper. Res., 92
62.
(1996),$649\ovalbox{\tt\small REJECT}$[8] Kurano, M., Song, J., Hosaka, M. and Huang, Y., Controlled Markov Set-Chainswith Discounting, J. Appl Prob., 35 (1998), 293-302.

[9] Kurano, M., Yasuda, M. and Nakagami, J., Interval methods for uncertain Markov
decision processes, submitted to the International Workshop on Markov Processes
and Controlled Markov Chains, Changsha, Husan, China on August 22-28, 1999.
[10] Kurano, M., Yasuda, M., Nakagami, J. and Yoshida, Y., Ordering of fuzzy sets
Abrief survey and new results, J. Operations Research Society of Japan, 43 (2000),-

138-148.
[11] Kurano, M., Yasuda, M., Nakagami, J. and Yoshida, Y. Afuzzy treatment of uncertain Markov decision processes, Proceedings of ASSM2000 International Conference
on Applied Stochastic System Modeling (Kyoto, March 2000), 148-157.
[12] Mine, H. and Osaki, S., Markov Decision Processes, (1970), Elsevier, Amsterdam.
[13] Nov&k, V., Fuzzy sets and their applications, (1989), Adam Hilger, Bristole-Boston.
[14] Puri, M. L. and Ralesca, D. A., Fuzzy random variable, J. Math. Anal. Appl, 114(1986), 402-422.

[15] Puterman, M. L., Markov decision processes: Discrete Stochastic Dynamic Programming, (1994), John Wiley&Sons, INC.

im\’anek, Inequality relation between fuzzy numbers and its use in[16] J.Ram\’ik andfuzzy optimization, Fuzzy Sets and Systems, 16 (1985), 123-138.
$\mathrm{J}.\dot{\mathrm{R}}$[17] Stow\’inski, R., (ed.), Fuzzy Sets in Decision Analysis, Operation Research and Statistics, (1998), Kluwer Academic Publishers.
[18] White, D. J., Multi-0bjective infinite-horizon discounted Markov Decision Processes,
J. Math. Anal. Appl, 89 (1982), 639-647.
[19] Yoshida, Y., Atime-average fuzzy reward criterion in fuzzy decision processes, Information Sciences, 110 (1998), 103-112.
[20] Zadeh, L. A., Fuzzy sets, Inform, and Control, 8 (1965), 338-353