数理解析研究所講究録 1207 巻 2001 年 41-54

41
Stopped Markov Decision Processes
with Multiple Constraints
千葉大学・自然科学研究科

堀口正之 (Masayuki HORIGUCHI)

Abstract
In this PaPer, aoptimization problem for stopped Markov decision processes with
vector-valued terminal reward and multiple running cost constraints is considered.
APPlying the idea of occupation measures and using the scalarization technique forvector maximization problems we obtain the equivalent Mathematical Programming
problem and show the existence of aPareto optimal pair of stationary policy andstopping time requiring randomization in at most states, where is the number of
constraints. Moreover Lagrange multiplier approaches are considered. The saddlepoint statements are given, whose results are applied to obtain arelated parametric
Mathematical Programming, by which the problem is solved. Numerical examples
are given.
$k$

$k$

Key words: Stopped Markov decision process, multi-0bjective, multiple constraints, Mathematical Programming formulation, Lagrange multiplier.

1

Introduction

The aim of this paper is to establish aMathematical Programming method for finite
state stopped Markov decision processes(MDPs) with vector-valued terminal reward andmultiple running cost constraints. In the preceding paper Horiguchi [9], we consider aoptimization problem for stopped Markov decision processes with aconstrained stopping
time. The problem is solved through randomization of stopping times and Mathematical
Programming formulation by occupation measures. Here, we consider the vector-valued
and multiple constrained case. The optimality is defined by the concept of efficiency,
based on apseud0-0rder preference relationinduced by aclosed convex cone $K$ in. Then aPareto optimization with respect to the pseud0-0rder
is considered(cf. [6,18]). Applying the idea of Horiguchi[9], we derive arelated Mathematical Programming
to solve the problem treated in this paper and show the existence of aPareto optimal
pair of stationary policy and stopping time requiring randomization in at most states,
whereis the number of constraints. Also, introducing acorresponding Lagrangefunction, the saddle-point statements for our constrained problem are given, whose
results are applied to obtain arelated parametric Mathematical Programming, by which
the problem is solved. Numerical examples are given to illustrate the results. For theunconstrained case, refer to Purukawa and IwamOtO[7], Hordijk[8] and Rieder[16]. A
Lagrangian approach to aconstrained optimal stopping problem has been discussed
originally by Nachman[15] and Kennedy[12]. For the dynamic programming approachto the constrained Markov decision processes, see Horiguchi et.
In the reminder of this section, we shall establish some notation that will be usedthroughout this paper referring to the preceding work[9] and define the vector-valued
optimization problem with multiple constraints. Also, aPareto optimal pair of policy
and randomized stopping time is defined$\neg\prec K$$\mathbb{R}^{p}$$\backslash \prec K$

$k$

$k$

$\mathrm{a}1[10]$42
Let and be finite sets denoted by $S=\{1,2, \ldots N\}$ and $A=\{1,2, \ldots, K\}$ . The
stopped Markov decision model consists of five objects:
$A$

$S$

$(S, A, \{pij(a) :i,j\in S, a\in A\}, \{c^{l}, l=1,2, \ldots, k\}, r)$where and denote the state and action spaces respectively andis the lawof motion, i.e., for each $(i, a)\in S\cross A,p_{\dot{\iota}j}(a)\geqq 0$ and $\sum_{j\in S}p_{ij}(a)=1$ , and $c^{l}=c^{l}(i, a)$ ,$l=1,2$ ,, , are running cost functions on, which will be related to constraints,
and $r=r(i)=(r^{1}(i), \ldots, r^{p}(i))$ is avector-valued terminal reward function on whenselecting “stoP” in state .
When the system is in state $i\in S$ , if we select “stoP” the process terminates with theterminal reward $r(i)$ . If we select “continue” and take $a\in A$ , we move to anew state$j\in S$ selected according to the probability distribution
and the costs $d(i, a)$ , $l=$
$1,2$ ,
, are incurred. This process is repeated from the new state $j\in S$ . Let ,$(x_{1}, a_{1}, \ldots, x_{t})\in(S\cross A)^{t-1}\cross S$ the history
be the state and action at time anduP to time $t(t\geqq 1)$ . Apolicy for controlling the system is asequence, is aconditional probability measure on Agiven history
such that, for eachwith $\pi_{t}(A|(x_{1}, a_{1}, \ldots,x_{t}))=1$ for each $(x_{1}, a_{1}, \ldots,x_{t})\in(S\cross A)^{t-1}\cross S$ . Let denotes
the set of all policies. Apolicy $\pi=$is aMarkov policy if is afunctionof only , i.e.,
for all $(x_{1}, a_{1}, \ldots, x_{t})\in(S\cross A)^{t-1}\cross S$ .
AMarkov policy $\pi=$is stationary if there exists aconditional probability, given $i\in S$ such thaton ,for all $x_{t}\in S$ and $t\geqq 1$ , anddenoted simply by . Astationary policy is called deterministic if there exists amap
$g:Sarrow A$ with $w(g(i)|i)=1$ for all $i\in S$ and such apolicy is identified by . The sets,of all Markov, stationary and deterministic policies will be denoted byandrespectively. Note that
. The sample spaces is the product space. Let , be random quantities such thatand
, a2, )(
for all. For any given policy $\pi\in\Pi$ and initial distribution !
on we can specify the probability measure
on in ausual way.
$H_{t}=$,, where $B(H_{t})$ is the a-field induced
. Let
Let
by
. Let
.
and
the smallest -field containing each
In order to solve our constrained decision problem described in the sequel, we need to
introduce randomized stopping time (cf. [2, 5, 12]) . To this purpose, enlarging to, we can embed, wheretois Borel subsets of$[0, 1]$ . For afiltration
with
we can assume without lossof generality that for each
$A$

$S$

$\{\mu_{j}(a)\}$$S\cross A$$k$$\ldots$

$k$

$S$

$i$

$p_{i}.(a)$$k$$\ldots$$x_{t}$$a_{t}$$h_{t}=$$t$$\pi=(\pi_{1}, \pi_{2}, \ldots)$$t\geqq 1$$h_{\mathrm{t}}$$\pi_{t}$$\Pi$$(\pi_{1}, \pi_{2}, \ldots)$$\pi_{t}$$\pi_{t}(\cdot|x_{1}, a_{1}, \ldots, x_{t})=\pi_{t}(\cdot|x_{t})$$x_{t}$$(\pi_{1}, \pi_{2}, \ldots)$$A$$w(\cdot|i)$$\pi_{t}(\cdot|x_{t})=w(\cdot|x_{t})$

$w$

$w$

$g$

$\Pi_{M}$$\Pi_{D}$$\Pi_{S}$$\Pi_{D}\subset\Pi_{S}\subset\Pi_{M}\subset\Pi$$\Omega$$=(S\cross A)^{\infty}$$\omega$$=$$X_{t}$$X_{t}(\omega)=x_{t}$$\Delta_{t}$$\Delta_{t}(\omega)=a_{t}$$\in\Omega$$x_{1},$ $a_{1},$ $x_{2}$$\ldots$$S$$\Omega$$\mathbb{P}_{\beta}$$(X_{1}, \Delta_{1}, \ldots, X_{t})$$H_{t}$$F_{\infty}$$\mathcal{F}_{t}=B(H_{t})$$t\geqq 1$$\overline{N}=\{1,2, \ldots\}\cup\{\infty\}$$\mathcal{F}_{t},t\geqq 1$$\sigma$$\Omega$$)$$\overline{\Omega}:=\Omega\cross[0,1]$$(\overline{\Omega}, F_{\infty}\cross \mathrm{B}_{1})$$(\Omega, \mathcal{F}_{\infty})$$F^{*}=\{\mathcal{F}_{t}^{*}, t\in\overline{N}\}$$\mathrm{B}_{1}$$F_{t}^{*}=F_{t}\cross \mathrm{B}_{1}$$t\in\overline{N}$$F_{t}\subset F_{t}^{*}$

.

(1.1)

We call amap :arandomized stopping time (hereafter called RST) w.r.t.
if. For simplicity, the upper bar of RST will befor eachomitted and written by with some abuse of notation. The class of RSTs w.r.t. $P$ will
be denoted by . For each initial distribution and each policy $\pi\in\Pi$ , we denote theprobability measure on by , where
and Ais Lebesgue measure on .
Let
be the set of real pdimensional row vectors andanontrivial closed
and pointed convex cone(cf. [17]). We introduce apseud0-0rder relation
byon, apoint $x\in U$ is called efficient
iff $y-x\in K$ . For anonempty subset
with respect to the orderon
if
for some $y\in U$ implies $x=y$ . Let $e(U)$denote the set of all efficient points of with respect to.
$\overline{\Omega}arrow\overline{N}$$\overline{\tau}$$F^{*}$$t\in\overline{N}$$\{\overline{\tau}=t\}\in F_{t}^{*}$$\overline{\tau}$$\tau$$S$$\beta$$\overline{\Omega}$$\overline{\mathrm{P}}_{\beta}^{\pi}=\mathrm{P}_{\beta}^{\pi}\cross\lambda$$\neg \mathrm{P}_{\beta}$$\mathrm{B}_{1}$$K\subset \mathbb{R}^{p}$$\mathbb{R}^{p}$$\neg\prec K$$X\neg\prec K$$U\subset \mathbb{R}^{p}$$y$$\neg\prec K$$\mathbb{R}^{p}$$x\prec_{\neg K}y$$U$$\neg\prec K$$\mathbb{R}^{p}$

43
For any$\alpha=$$(\alpha^{1}, \ldots, \alpha^{k})\in \mathbb{R}^{k}$$\Lambda^{k}(\alpha, \beta):=${and initial distribution$(\pi,$ $\tau)\in\Pi\cross S|\mathrm{E}_{\beta}\sum_{t=1}^{\tau-1}\neg c^{l}(X_{t}$,$\Delta_{t})\leqq\alpha^{l}$$\beta$on , let$S$

for $l=1,2$ ,$\ldots$

,

$k$

}

(1.2)

is the expectation with respect to .
where
We shall consider the vector-valued constrained optimization problem(VCOP):$\neg \mathrm{P}_{\beta}$$\overline{\mathrm{E}}_{\beta}^{\pi}$

VCOP :Maximize
subject toApair$(\pi^{*}, \tau^{*})\in\Lambda^{k}(\alpha, \beta)$$\neg \mathrm{E}_{\beta}r(X_{\tau}):=(\overline{\overline{\mathrm{E}}}_{\beta}^{\pi}r^{1}(X_{\tau}), \ldots,\mathrm{E}_{\beta}r^{p}(X_{\tau}))\neg$$(\pi, \tau)\in\Lambda^{k}(\alpha, \beta)$.

is called Pareto optimal if

.

(1.3)

$\neg^{*}\mathrm{E}_{\beta}r(X_{\tau}*)\in e(\{\mathrm{E}_{\beta}r(X_{\tau})|(\pi, \tau)\neg\in\Lambda^{k}(\alpha, \beta)\})$, , the running cost constraints are reduced tofor $l=1,2$ ,Note that if, whose case have been studied in [9], so that works, wherein this paper are thought of as ageneralization of those in [9].
$c^{l}\equiv 1$$k$$\ldots$$d= \min_{1\leq l\leq k}\alpha^{l}+1$$\neg \mathrm{E}_{\beta}^{\mathrm{r}}\tau\leqq d$

Now, we define $F$-representation of aRST (cf. [9, 11]). For any RST $\tau\in S$ and, let,$t\in\overline{N}$$g_{t}(\omega):=\lambda(\{\tau=t\}_{\omega})$

where
Note thatis the -section defined by $\{\tau=t\}_{\omega}=\{x\in[0,1]|(\omega, x)\in\{\tau=t\}\}$ .
, we define the set
is -measurable for $t\geqq 1$ . From thisas follows:(1.4),$\{\tau=t\}_{\omega}$$\omega$$g_{t}(t\in\overline{N})$$\mathcal{F}_{t}$$g_{t}$$f=(f_{t})_{t\in\overline{N}}$$(\omega\in\Omega)$$t\in\overline{N}$$f_{t}:= \frac{g_{t}}{1-\sum_{k=1}^{t-1}g_{k}}$where if the denominator is 0in (2.1) let $f_{t}=1$ .
, and if $a_{j}=1a_{i}--1$ for $i>j$ }. Then,: $0\leqq a_{j}\leqq 1$ ,Let $F=$ {, each is -measurable and for any
it is shown in Lemma 2.1 of [9] that :$(\pi,\tau)\in\Pi\crossS$
it holds
initial distribution and pair$a_{\infty}=1$$a=(a_{j})_{j\in\overline{N}}$$f$$\Omegaarrow F$$f_{t}$$F_{t}$$\beta$$f_{t}=, \frac{\neg \mathrm{P}_{\beta}(\tau--t|H_{t})}{\neg,\mathrm{P}_{\beta}(\tau\geqq t|H_{t})}$The setby$f=(f_{t})_{t\in\overline{N}}$$f^{\tau}=(f_{t}^{\tau})_{t\in\overline{N}}$.

construct$\mathrm{e}\mathrm{d}$from$\tau\in S$,$\mathrm{P}_{\beta}^{\pi}$

-a.s.

(1.5)

is called $F$-representation of , denoted$\tau$: $\Omegaarrow F$ such that for eachbe any function
Conversely, letting
is -measurable, we can construct the RST from (see Lemma 2.2 of [9]),denoted by . Hence, there is one-t0-0ne correspondence between $S$ and the set of$F$ -representations. Using this fact, we define several types of RSTs.
$F$ -representation
is afuncis -measurable $(t\geqq 1)$ ,corresponding
Since the.
tion of $H_{t}=$$f$$f=(f_{t})_{t\in\overline{N}}$$t\in\overline{N}f_{t}$$f$$\mathcal{F}_{t}$$\tau^{f}$$f=(f_{t})_{t\in\overline{N}}$$f_{t}^{\tau}$$(X_{1}, \Delta_{1}, \ldots, X_{t})$$\mathcal{F}_{t}$$f_{t}^{\tau}$

44
, the
Definition 1.1. If is depending only on , that is,for all$RST\tau$ is called Markov. A Markov $RST$ is called stationary
if there exists a function$t\geqq
1$$Sarrow[0,1]$,
simply by . Whendenoted:such thatfor all$RST\delta$$\delta(i)\in\{0,1\}$
is called deterministic.
for all $i\in S$ , the stationary$t\geqq 1$$f_{t}^{\tau}(H_{t})=f_{t}^{\tau}(X_{t})$$X_{t}$$f_{t}^{\tau}$$f_{t}^{\tau}(X_{t})=\delta(X_{t})$$\delta$$\delta$

We denote the sets of all Markov RSTs, all stationary RSTs and all deterministic
respectively. With some abuse of notation, we often use for a
RSTs by $S_{M},Ss$ and.
such asstationary RST
the -representation with
It is easily shown(cf. [9]) that the running costs and terminal reward under aas follows.
and a are represented using -representation$S_{D}$$\tau\in S_{s}$$\delta$$\mathrm{F}$$\delta\in S_{s}$$\delta=(f_{t}^{\tau})$$\tau\in S$

$F$

$\Pi$

$\pi$

$f^{\tau}=(f_{t}^{\tau})_{t\in\overline{N}}$(1.6)$\overline{\mathrm{E}}_{\beta}^{\pi}\sum_{t=1}^{\tau-1}c^{l}(X_{t}, \Delta_{t})$$= \sum_{t=1}^{\infty}\mathrm{E}_{\beta}^{\pi}(1-f_{1})(1-f_{2})\cdots(1-f_{t-1})f_{t}(\sum_{n=1}^{t-1}c^{l}(X_{n:}\Delta_{n}))$, $l=1,2$ ,$\ldots$

,

$k$

and
(1.7)

$\neg \mathrm{E}_{\beta}r^{m}(X_{\tau})$$= \sum_{t=1}^{\infty}\mathrm{E}_{\beta}^{\pi}(1-f_{1})(1-f_{2})\cdots(1-f_{t-1})f_{t}r^{m}(X_{t}, \Delta_{t})$Letdenote the dual cone of aconvex cone
for all $x\in K$ } where , means inner product in
The following result is well known(cf. [3])$K^{*}$$0$$K\subset \mathbb{R}^{p}$$\langle\cdot$$\cdot\rangle$$\mathbb{R}^{p}$.

, $m=1,2$ , $\ldots,p$ .
, i.e.,$K^{*}=\{b\in \mathbb{R}^{p}$:$\langle b, x\rangle\geq$

be compact and convex set. Then $x\in e(B)$ if and only if
Lemma 1.1. Let
there $\dot{m}tsb\in K^{*}(b\neq 0)$ such thatfor all $y\in B$ .
$B\subset \mathbb{R}^{p}$$\langle b,x\rangle\geq\langle b, y\rangle$$e$

In Section 2, the running and stopped occupation measures are introduced, by which
VCOP is reduced equivalently to multi-0bjective Mathematical Programming problem.
In Section 3, studying the properties of the set of running occupation measures we canprove the existence of aPareto optimal pair of stationary policy and stopping timerequiring randomization in at most states. Section 4is devoted to Lagrange approaches
for VCOP. Finally, the proof of key Lemma used in Section 3is given in Section 5.
$k$

2Occupation measures in Stopped MDPs
In this section, we introduce two types of occupation measures in stopped MDPs andconsider the properties of them.
, we
with
Definition 2.1. For any initial distribution and a pairmeasure,,by
occupationoncalled the runningdefine the measure$\beta$$x(\beta,\pi, \tau)$$(\pi,\tau)$$\mathrm{E}_{\beta}^{\neg}[\tau]<\infty$$S\cross A$$x( \beta, \pi, \tau;i, a):=\sum_{t=1}^{\infty}\mathrm{P}_{\beta}(X_{t}=i, \Delta_{t}=a, \tau>t)\neg$

for $i\in S$, $a\in A$ .

(2.1)

45
, we
with
Definition 2.2. For any initial distribution and a pair (vr,$y(\#,$
measure,by
occupation
stoppedxA,
called them,ondefine the measure$\#$$\mathrm{q}[\mathrm{r}]<\mathrm{o}\mathrm{o}$$\ovalbox{\tt\small REJECT})$$S^{\ovalbox{\tt\small REJECT}}$$\ovalbox{\tt\small REJECT})$

for $i\in S$, $a\in A$ .

$y( \beta,\pi, \tau;i, a):=\sum_{t=1}^{\infty}\mathrm{P}_{\beta}(X_{t}=i, \Delta_{t}=a, \tau=t)\neg$(2.2)

The state running and stopped occupation measures will be defined by$x( \beta, \pi, \tau;i):=\sum_{a\in A}x(\beta, \pi, \tau;i, a)$and$y( \beta, \pi, \tau;i):=\sum_{a\in A}y(\beta, \pi, \tau;i, a)$for all $i\in S$ .

given $i\in S$ ,on
and conditional distribution
element is $P_{ij}(w)(1-\delta(j)):=$
the $N\cross N$ matrix where$\sum_{a\in A}p_{ij}(a)w(a|i)(1-\delta(j))$ or simply. With some abuse of notation, for any
is defined by, the row vector
initial distribution and

For any
we define by:$\delta$$Sarrow[0,1]$$A$$w(\cdot|i)$$P^{\delta}(w)$$(i,j)\mathrm{t}\mathrm{h}$$(P^{\delta}(w))_{ij}$$x(\beta, \pi, \tau)\in \mathbb{R}^{N}$$(\pi, \tau)\in\Pi \mathrm{x}S$$\beta$$x(\beta, \pi, \tau):=(x(\beta, \pi, \tau;1), \ldots, x(\beta, \pi, \tau;N))$.

Then, in the following lemma, the state stopped occupation measure is proved tobe represented by the running one and for each $(w, \tau)\in\Pi_{S}\cross Ss$ , the state runningoccupation measure is determined uniquely as asolution of the corresponding equations
below.

Lemma 2.1. ([9]) For any initial distribution
we have the following:$\beta$and pair$(\pi, \tau)\in\Pi\cross Swith\mathrm{E}_{\beta}[\tau]\neg<\infty$(i) $x(\beta, \pi, \tau;i)<\infty$ and $y(\beta, \pi, \tau;i)<\infty$ for all $i\in S$ .
(ii).

$\overline{\overline{\mathrm{E}}}_{\beta}^{\pi}[\tau]=\sum_{i\in S}x(\beta, \pi, \tau;i)+1$(iii) $y( \beta, \pi, \tau;i)=\beta(i)+\sum_{j\in S,a\in A}x(\beta, \pi, \tau;j, a)p_{ji}(a)-x(\beta, \pi, \tau;i)$ .
Moreover, if $(w, \tau)\in\Pi_{S}\cross S_{S}$ , then the state running occupation measure $x(\beta, w, \tau)$ is$tte$ unique solution to$x=\beta(1-\delta)+xP^{\delta}(w)$ ,(2.3)$x\in \mathbb{R}^{N}$

whose -th component is $\beta(i)(1-\delta(i))$ and
where
is in
is -representation of .
$\beta(1-\delta)$

$F$

Let

$\mathbb{R}^{N}$$i$$\delta:=f^{\tau}$: $Sarrow[0,1]$$\tau$$\mathbb{R}^{N\cross K}$

be the set of real $N\cross K$ matrices. For any subset$\mathrm{X}^{k}(U):=\{x(\beta, \pi, \tau;i, a)_{i\in S,a\in A} :Note that$\mathrm{X}^{k}(U)\subset \mathbb{R}^{N\mathrm{x}K}$.

$U\subset\Pi \mathrm{x}S$.

(\pi, \tau)\in U\cap\Lambda^{k}(\alpha, \beta)\}$, denote(2.4)

46Here, we define the multi-0bjective Mathematical Programming problem(MMP (i)related to VCOP as follows:

MMP(I): Maximize
subject to$\sum_{i\in S}r(i)y(i):=(\sum_{i\in S}r^{1}(i)y(i), \ldots, \sum_{\dot{l}\in S}r^{p}(i)y(i))$$x\in \mathrm{X}^{k}(\Pi \mathrm{x} S)$,

and$y\in \mathbb{R}^{N}$$y(i)= \beta(i)+\sum_{j\in S,a\in A}x(j, a)p_{j:}(a)-x(i)$,$i\in S$,

where $x(i)= \sum_{a\in A}x(i, a)$ .
Then, we have the following theorem, which is proved from Lemma 1.1 by the useof (Theorem 3.1 of [9]).

Theorem 2.1. VCOP is equivalent tofor VCOP if and only if the corresponding
optimal for MMP(I).

$\mathrm{M}\mathrm{M}\mathrm{P}(\mathrm{I}),$$i.e.$, a pair$(\pi^{*}, \tau^{*})$

is Pareto optimal$\{x(\beta, \pi^{*}, \tau^{*};i, a)\}\in \mathrm{X}^{k}(\Pi\cross S)$

is Pareto

Proof Prom Lemma 1.1, an efficient point for VCOP is given by solving the following

maximization problem for some $b\in K^{*}$ :Maximizesubject to(2.5)$\langle b,\mathrm{E}_{\beta}^{\mathrm{r}}r(X_{\tau})\rangle\neg$$(\pi,\tau)\in \mathrm{A}^{k}(\alpha, \beta)$.

Applying (Theorem 3.1 of [9]) will complete the proof of Theorem 2.1. 1

3Mathematical Programming approach and Pareto
optimal pairIn this section, we present another Mathematical Programming formulation by which
VCOP is explicitly solved.
To this end, we define several basic sets below. For simplicity, we put. For any initial distribution on and
and
, let
$(a\mathfrak{z}_{a})=$$\{x:a\}:\in S,a\in A\in \mathbb{R}^{N\mathrm{x}K}$$\delta$$=\{\delta(i)\}:\in s\in \mathbb{R}^{N}$$S$$\beta$$\alpha=(\alpha^{1}, \ldots, \alpha^{k})\in \mathbb{R}^{k}$$\hat{\mathbb{Q}}^{k}:=\{\begin{array}{llll}((x_{ia}),\delta)\in \mathbb{R}^{N\mathrm{x}K}\cross \mathbb{R}^{N} (\mathrm{i})\sum_{a\in A}x_{\dot{l}a}=\beta(i)(1-\delta(i))+ \sum_{j\in S,a\in A}x_{ja}p_{ji}(a)(1-\delta(i)),(i\in S)(\mathrm{i}\mathrm{i})0\leqq\delta(i)\leqq 1(i\in S) (\mathrm{i}\mathrm{i}\mathrm{i})\sum_{i\in S,a\in A}c^{l}(i,a)x_{ia}\leqq\alpha^{l} (l=\mathrm{l},2 \cdots k)(\mathrm{i}\mathrm{v})x_{\dot{l}a}\geqq 0(i\in S,a\in A) \end{array}\}$$\mathbb{Q}^{k}:=\{(x:a)\in \mathbb{R}^{N\mathrm{x}K}$:$((x_{a}.\cdot), \delta)\in\hat{\mathbb{Q}}^{k}$

We introduce the following assumption

for some$\delta\}$

.

,

(3.1)

(3.2)

47
Assumption $(*)$ . For any w$\in\Pi_{S}$and $l(1\leqq l\leqq k)$ ,$\max_{1\leqq\iota\leqq k}c^{l}(i|w)>0$

for each $i\in S$(3.3)

where $c^{l}(i|w)= \sum_{a\in A}d(i, a)w(a|i)$ .
We have the following theorem, whose proof is similar to (Theorem 4.1, Lemma 4.1
and Theorem 4.2 in [9] and omitted.
$)$

Theorem 3.1. Suppose that Assumption $(*)$ holds. Then
(i)
(ii)
(iii)

$\mathrm{X}^{k}(\Pi\cross S)=\mathrm{X}^{k}(\Pi_{M}\cross S_{M})=\mathrm{X}^{k}(\Pi s\cross Ss)$$\mathbb{Q}^{k}=\mathrm{X}^{k}(\Pi_{S}\cross S_{S})$$\mathbb{Q}^{k}$.

.

is compact and convex.

The following corollary holds clearly from Theorem 3.1 and observing (3.2).

Corollary 3.1.

$\mathrm{X}^{k}(\Pi_{S}\cross S_{S})$Remark. For any
For each $a\in A$ and $i\in S$ ,is compact and convex.

$((x_{ia}), \delta)\in\hat{\mathbb{Q}}^{k}$, we define astationary policy$\underline{x_{\dot{l}a}}$$w(a|i)=\{$$w$

as follows:

if $x_{i}>0$ ,,$x_{i}$

any probability distribution on$A$,

if $x_{i}=0$ ,(3.4). Then, $x=(x_{i})$ with $x_{i}=x(\beta, w, \delta;i)$ , $i\in S$ is given as auniquewheresolution of (2.3).
Also, (i) and (iii) in (3.1) are rewritten as follows:$x_{i}= \sum_{i\in A}x_{ia}$$x_{i}= \beta(i)(1-\delta(i))+\sum_{j\in S}x_{j}P_{ji}(w)(1-\delta(i))$$(\mathrm{i}’)$

$\{$

(ii)

$)$

$\sum_{i\in S}d(i, w)x_{i}\leqq\alpha^{l}$, $l=1,2$ ,$\ldots$,, $i\in S$

(3.5)

$k$

where $d(i, w)= \sum_{a\in A}c^{l}(i, a)w(a|i)$ .
Now, we define another multi-0bjective Mathematical Programming problem (MMP (II))
for VCOP:
MMP(I ) :Maximize

subject to$\sum_{i\in S}r(i)y_{i}$$(x_{ia})\in \mathbb{Q}^{k}$,$y_{i}= \beta(i)+\sum_{j\in S,a\in A}$

xjapji $(a)- \sum_{a\in S}x_{ia}$ , $i\in S$

Here we get the following corollary which is obviously given ffom Theorem 2.1 and 3.1
and Corollary 3.1.
Corollary 3.2. It holds that(i) VCOP and MMP(II) are equivalent48(ii) A Pareto optimal pair exists on $\Pi s\cross Ss$ .

For any stationary policy $w\in\Pi_{S}$ , let $n(w)$ be the total number of randomization
under , that is,,$n(w)= \sum_{\dot{\iota}\in S}(m(i, w)-1)$$w$

where $m(i, w)$ is the number of elements in $\{a\in A|w(a|i)>0\}$ . Define$\Pi_{S}^{k}:=\{w\in\Pi_{S} :and$S_{S}^{k}:=$For$(x_{ia})\in \mathbb{Q}^{k}$,{$\tau\in S_{S}|f^{\tau}(i)\in\{0,1\}$$\mathrm{I}((x_{\dot{l}a}))\subset\{1,2, \ldots k\}$$\{l_{1}, l_{2}, \ldots, l_{h}\}\subset\{1,2, \ldots, k\}$except at most$k$states}.

\sum_{i\in S,a\in A}c^{l}(i, a)x_{\dot{\iota}a}=\alpha^{l}\}$

.

, let

$\mathbb{Q}_{\{l_{1},\ldots,l_{h}\}}:=\{(x:a)|((x_{ia}), \delta)\in\hat{\mathbb{Q}}$

where

,

is defined as follows:$\mathrm{I}((x:a)):=\{l\in\{1,2, \ldots, k\} :For anyn(w)\leqq k\}${$l_{1},l_{2},\ldots,l_{h}\rangle$$\hat{\mathbb{Q}}\{l_{1},\ldots,l_{h}\}:=\{((x:a), \delta)\in\hat{\mathbb{Q}}^{k} :for so me$\delta$$\in \mathbb{R}^{n}$},.

\mathrm{I}((x_{\dot{l}a}))=\{l_{1}, l_{2}, \ldots, l_{h}\}\}$

the set of extreme points of
For any compact convex set $D$ we denote byThen, we have the following, whose proof is done in Section 5.
$\mathrm{e}\mathrm{x}\mathrm{t}(D)$Lemma 3.1. Under Assumption $(*)$ , it holds that for any$\mathrm{e}\mathrm{x}\mathrm{t}(\mathbb{Q}_{\{l_{1\prime}\ldots,l_{h}\}})\subset\{x(\beta, w, \delta) :

where

$k$

is the number$D$$\{l_{1}, \ldots, l_{h}\}\subset\{1, \ldots, k\}$(w, \delta)\in\Pi_{S}^{k}\mathrm{x} S_{S}^{k}\}$

,

.

,

(3.6)

of constraints.

The existence of aPareto optimal pair of stationary policy and stopping time requiring randomization in at most states is given in the following.
$k$

Theorem 3.2. Suppose Assumption $(*)$ holds. Then a Pareto optimal pair, that is,in
VCOP$e$$\dot{m}ts$$(\pi^{*}, \tau^{*})$$e(\{\mathrm{E}_{\beta}^{\pi}r(x_{\tau})|(\pi, \tau)\in\Lambda^{k}(\alpha, \beta)\})\subset e(\{\mathrm{E}_{\beta}^{\pi}r(x_{\delta})|(w, \delta)\in(\square _{S}^{k}\cross S_{S}^{k})\cap\Lambda^{k}(\alpha, \beta)\})$

Proof. Let

for$\Pi_{S}^{k}\cross S_{S}^{k}$$(\pi^{*},\tau^{*})\in e(\{\mathrm{E}_{\beta}^{\pi}r(x_{\tau})|(\pi,\tau)\in\Lambda^{k}(\alpha, \beta)\})$. (3.7). Then, by Theorem 2.1, there

is aoptimal solution for (2.5) with $b=b^{*}$ . Here, fromsuch that
sexists, so that there
Theorem 3.1 and Corollary 3.2, we can assume that
. Applying Lemma 3.1,
withexists$b=b^{*}$. This means thatwhich is asolution of (2.5) withthere exists
is aPareto optimal for VCOP, as required. 1$b^{*}\in K^{*}$$(\pi^{*},\tau^{*})$$(\pi^{*},\tau^{*})\in\Pi_{S}\cross S_{S}$$\{l_{1}, l_{2}, \ldots, l_{h}\}\subset\{1,2, \ldots h\}$$(w^{*},\tau^{*})\in\Pi_{\mathrm{S}}^{k}\cross S_{S}^{k}$$(w^{*}, \tau^{*})$

Example 3.1$x(\beta, \pi^{*}, \tau^{*})\in \mathbb{Q}\{l_{1},l_{2},\ldots,l_{h}\}$49
Consider the following numerical example with $p=1$ .
$S=\{1,2,3,4\}$ , $A=\{1\}$ , $(\alpha_{1}, \alpha_{2})=(0.5,0.4)$ , $\beta=(0.25,0.25,0.25,0.25)$ ,$(p_{\dot{l}j}(1))=(\begin{array}{llll}0.3 0.4 0.1 0.20.4 0.1 0.2 0.30.2 0.3 0.4 0.10.3 0.3 0.1 0.3\end{array})$,$c^{1}(1,1)=0.6$ ,$c^{1}(2,1)=0.1$ ,$c^{1}(3.1)=0.6$ ,$c^{1}(4,1)=0.4$ ,$c^{2}(1,1)=0.6$ ,$c^{2}(2,1)=0.05$ ,$c^{2}(3.1)=0.1$ ,$c^{2}(4,1)=0.8$ ,$r(1)=4$ ,$r(2)=3$ ,$r(3)=2$ ,$r(4)=2$ .

Letting $x_{i}=x_{i1}(i\in S)$ , the mathematical programming problem (MMP(II)) for thecorresponding constrained optimization problem is given as follows:

Maximizesubject to$-x_{1}-0.1x_{2}+0.7x_{3}+0.9x_{4}+2.75$$x_{1}=(0.25+0.3x_{1}+0.4x_{2}+0.2x_{3}+0.3x_{4})(1-\delta(1))$ ,$x_{2}=(0.25+0.4x_{1}+0.1x_{2}+0.3x_{3}+0.3x_{4})(1-\delta(2))$ ,,$x_{4}=(0.25+0.2x_{1}+0.3x_{2}+0.1x_{3}+0.3x_{4})(1-\delta(4))$ ,$0.6x_{1}+0.1x_{2}+0.5x_{3}+0.4x_{4}\leqq 0.6$ ,$0.6x_{1}+0.05x_{2}+0.1x_{3}+0.8x_{4}\leqq 0.4$ ,$x_{i}\geqq 0,0\leqq\delta(i)\leqq 1$ , $i=1,2,3,4$ .
$x_{3}=(0.25+0.1\mathrm{x}2+0.2x_{2}+0.4x_{3}+0.1x_{4})(1-\delta(3))$

After asimple calculation, we find the optimal solution of the above is$26/71$ ,$x_{1}^{*}=0$,$x_{2}^{*}=$, $x_{4}^{*}=57/142$ , $\delta^{*}(1)=1$ , $\delta^{*}(2)=79/209$ , $\delta^{*}(3)=0$ , $\delta^{*}(4)=33/128$
and the optimal value is 1242/355 $(.=$. 3.49859 . Note that the value is 285/82(.=. 3.47561)
for $\delta(1)=\delta(2)=1$ and $\delta(3)=\delta(4)=0$ .
Thus, by Corollary 3.2, the pairwith $w^{*}(i)=1$ for all $i\in$
and $f^{\tau^{*}}(1)=\delta^{*}(1)=1$ , $f^{\tau^{*}}(2)=\delta^{*}(2)=79/209$ , $f^{\tau^{*}}(3)=\delta^{*}(3)=0$ , $f^{\tau^{*}}(4)=$$\delta^{*}(4)=33/128$ is optimal for the corresponding constrained optimization problem and.
the optimal reward 1242/355. Note that$x_{3}^{*}=43/71$$)$$(w^{*}, \tau^{*})\in\Pi_{S}^{2}\cross S_{S}^{2}$$S$$\tau^{*}\in S_{S}^{2}$

4Lagrange multiplier approaches
In this section, we define the Lagrangian associated with VCOP and the saddle-point
statement is given(cf. [13]). Consequently, by solving aparametric Mathematical PrOgramming problem defined in the sequel, aPareto optimal pair is obtained.
Let $b=$. The Lagrangian, , associated with VCOP is defined as$(b_{1}, \ldots, b_{p})\in K^{*}$$L^{b}((\pi, \tau)$,$\lambda):=\sum_{i=1}^{p}b_{i}\mathrm{E}_{\beta}(r^{i}(X_{\tau}))+\sum_{l=1}^{k}\neg\lambda_{l}(\alpha^{l}-\mathrm{E}_{\beta}(\sum_{t=1}^{\tau-1}\neg \mathrm{r}c^{l}(X_{t}, \Delta_{t})))$

for any $(\pi, \tau)\in\Pi\cross S$ and$\mathbb{R}^{k}$$L^{b}$$\lambda=(\lambda_{1}, \ldots, \lambda_{k})\in \mathbb{R}_{+}^{k}$, where$\mathbb{R}_{+}^{k}$is the positive orthant of.

Hereafter$\lambda=$$(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{k})\in \mathbb{R}_{+}^{k}$(4.1)

will be written simply by A$\geqq 0$.

50
For the Lagrangian approach we shall refer to ([14]). We have the following saddlepoint statement, whose proof is similar to (Theorem 2, p.221 in [14]) combined with theuse of the scalarization technique and omitted.
Theorem 4.1. (cf. [14]) For some $b\in K^{*}$ , suppose that the Lagrangian, $i.e.$ ,andpoint at$(\pi^{*}, \tau^{*})\in\Pi\cross S$$(\pi,\tau)\in\Pi\cross S$

has a saddle-$\lambda^{*}\in \mathbb{R}_{+}^{k}$$L^{b}((\pi, \tau)$

for all$L^{b}$

and,$\lambda^{*})\leqq L^{b}((\pi^{*}, \tau^{*}),$ $\lambda^{*})\leqq L^{b}((\pi^{*}, \tau^{*})$$\lambda\in \mathbb{R}_{+}^{k}$. Then,,(4.2)$\lambda)$

is a Pareto optimal for VCOP.

$(\pi^{*}, \tau^{*})$In order to have the existence of asaddle-point of the Lagrangian $L^{b}(b\in K^{*})$ weintroduce the set of $N\cross K$ matrices as follows:
For $M>0$ , let$\mathbb{Q}(M):=\{\begin{array}{llllll} (\mathrm{i})\sum_{a\in A}x_{\dot{l}a}=\beta(i)(1\cdot-(x_{ia})\in \mathbb{R}^{N}\cross \mathbb{R}^{K} \delta(i))+ \sum_{j\in S,a\in A}x_{ja}p_{j}..(a)(1- \delta(i))(i\in S)(\mathrm{i}\mathrm{i})\mathrm{o}\leqq \delta(i)\leqq 1(i\in S) (\mathrm{i}\mathrm{i}\mathrm{i}) \sum_{\dot{l}\in S,a\in A}x_{ia}\leqq M -1 (\mathrm{i}\mathrm{v})x_{\dot{\iota}a} \geqq 0(i\in S,a\in A) \end{array}\}$. (4.3)

is identical with the set of feasible solutions of the Mathematical
Note that
Programming problem introduced in [9] to solve stopped MDPs with aconstrained, where $w\in\Pi_{S}$ is constructed
stopping time and condition (iii) of (4.3)
through (3.4). Under Assumption $(*)$ , it clearly holds that for asufficientffomlarge $M>0$$\mathbb{Q}(M)$$\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{s}\overline{\mathrm{E}}_{\beta}^{w}\tau^{\delta}\leqq M$$(x_{ia})$$\mathbb{Q}^{k}\subset \mathbb{Q}(M)$

.

(4.4)

Henceforth, $M>0$ will be fixed such that (4.4) holds.
By using occupation measures defined in Section 2, the Lagrangian $L^{b}(b\in K^{*})$ canbe rewritten as follows:
$k$

$p$

$L^{b}$( $(x:a)$ , )$\lambda$$:= \sum\sum b_{[}r^{[}(i)y_{i}+\sum\lambda_{l}(\alpha^{l}-\sum_{j\in S,a\in A}c^{[}(j,$$i\in Sl=1$$=$$\sum$( $\sum p_{ij}(a)r^{b}(j)$ $-r^{b}(i)$where $y::= \beta(i)+\sum_{j\in S,a\in Aja}xpji(a)-\sum_{\acute{a}\in A}x_{ia}$ and.
and A
We need the following condition.

)

(4.6)

$- \sum\lambda_{l}c^{[}(ik,$$a)$$x_{ia}$$l=1$$+ \sum_{l=1}^{k}\lambda_{l}\alpha^{l}+\sum_{\dot{l}\in S}r^{b}(i)\beta(i)$$\in \mathbb{R}_{+}^{k}$

(4.5)

$l=1$

$:\in S,a\in Aj\in S$$\mathbb{Q}(M)$$a)x_{ja})$,$r^{b}(j):= \sum_{l=1}^{k}b_{l}r^{l}(j)$, for $(x_{ia})\in$51
Assumption $(**)$ . (Slater condition) There exists$(x_{ia})\in \mathbb{Q}(M)$such that(4.7)$\sum_{i\in S,a\in A}c^{l}(i, a)x:a<\alpha^{l}$, .
Then, applying (Theorem 1, p.217 in [14]) we have the following Lemma under Slater
condition.
has
Lemma 4.1. Under Assumption $(*)$ and $(**)$ , for any $b\in K^{*}$ , the Lagrangian$i.e.$,,
anda saddle-point at

for all $l=1$ ,$k$$\ldots$$L^{b}$$(x_{ia}^{*})\in \mathbb{Q}(M)$$\lambda^{*}\in \mathbb{R}_{+}^{k}$$L^{b}((x_{ia}), \lambda^{*})\leqq L^{b}((x_{ia}^{*}), \lambda^{*})\leqq L^{b}((x_{ia}^{*}), \lambda)$

for all$(x_{ia})\in \mathbb{Q}(M)$,A$\in \mathbb{R}_{+}^{k}$.

in Lemma 4.1 throughffom
If we construct astationary policy(3.4),
satisfies (4.2). Thus, we have the following from Lemma 4.1.
,
Corollary 4.1. Under Assumption $(*)$ and $(**)$ , for any $b\in K^{*}$ , the Lagrangian.
has a saddle-point
Applying the results above, we can present aparametric Mathematical Programming, letapproach to obtain aPareto optimal pair for VCOP. For any $b\in K^{*}$ and A$(x_{ia}^{*})\in \mathbb{Q}(M)$$w^{*}$$(w^{*}, \lambda^{*})$$L^{b}(\cdot$$(w^{*}, \lambda^{*})\in\Pi_{s}\mathrm{x}$$\cdot$$)$$\mathbb{R}_{+}^{k}$$\in \mathbb{R}_{+}^{k}$

.

(4.8)

$r(i, a|b, \lambda):=\sum_{j\in S}p_{ij}(a)r^{b}(j)-r^{b}(i)-\sum_{l=1}^{k}\lambda_{l}c^{l}(i, a)$, aparametric Mathematical Programming problem
For $b\in K^{*}$ andwill be given as follows:$\lambda\in \mathbb{R}_{+}^{k}$$\mathrm{M}\mathrm{P}(b, \lambda)$: Maximize
subject to$\mathrm{M}\mathrm{P}(b, \lambda)$$\sum_{i\in S,a\in A}r(i, a|b, \lambda)x_{ia}$$(x_{ia})\in \mathbb{Q}(M)$.

we have the optimal valueThen, by using aresult in [9], for eachsuch that. By (4.6) and Lemma 4.1, there exists$\lambda\geqq 0$$v(b, \lambda)$

for$\lambda^{*}\in \mathbb{R}_{+}^{k}$$\mathrm{M}\mathrm{P}(b, \lambda)$$v(b, \lambda^{*})+\sum_{l=1}^{k}\lambda_{l}^{*}\alpha^{l}=\min_{\lambda\geqq 0}(v(b, \lambda)+\sum_{l=1}^{k}\lambda_{l}\alpha^{l})$

.

(4.8)

.
. Let
be asolution of
From this multiplier , we solve
andis asaddle-point satisfying (4.2), andThen, from the discussion above,pair
optimalfor
VCOP and the value ofis aPareto
we can say that
, whereis ais the expected rewards corresponding the Pareto optimal pairthrough (3.4).
stationary policy determined by
Example 4.1
This is Example 3.1. By solving (4.9) with $b=1$ , we get $\lambda^{*}=(29/213,248/213)$ andthe value of the saddle-point is 1242/355. In order to obtain aoptimal pair for VCOP,
as follows: $w^{*}(i)=1$ forand get the optimal pair
we solve
all $i\in S$ and $f^{\tau^{*}}(1)=\delta^{*}(1)=1$ , $f^{\tau^{*}}(2)=\delta^{*}(2)=79/209$ , $f^{\tau^{*}}(3)=\delta^{*}(3)=0$,$\delta^{*}(4)=33/128$ and the corresponding optimal reward 1242/355, which is equal to thenumerical results in Example 3.1.
$\lambda^{*}$$(w^{*}, \delta^{*})$$\mathrm{M}\mathrm{P}(b, \lambda^{*})$$((x_{ia}^{*}), \delta^{*})$$\mathrm{M}\mathrm{P}(b, \lambda^{*})$$\lambda^{*}$$\mathrm{M}\mathrm{P}(b, \lambda^{*})$$(w^{*}, \delta^{*})$$(w^{*}, \delta^{*})$$w^{*}$$x_{ia}^{*}$$\mathrm{M}\mathrm{P}(1, \lambda^{*})$$(w^{*}, \tau^{*})\in\Pi_{S}^{2}\cross S_{S}^{2}$$f^{\tau^{*}}(4)=$52
5Proof of Lemma 3.1
In this section, we prove Lemma 3.1.
By argument similar to those used in (Theorem 3.8, P.34, in [1]) we can show that$\mathrm{e}\mathrm{x}\mathrm{t}(\mathbb{Q}_{\{l_{1\prime}l_{h}\}},\ldots)\subset\{x(\beta, w, \delta) :be such thatLet
exists $j_{n}(n=1, \ldots, h+1)$ with$(w^{*}, \delta^{*})\in\Pi_{S}^{k}\cross S_{S}$$0<\delta^{*}(j_{n})<1$

For simplicity, putLet$x^{*}=x(\beta, w^{*}, \delta^{*})$$L:=\{l_{1}, l_{2}, \ldots, l_{h}\}$(w, \delta)\in\Pi_{S}^{k}\mathrm{x} S_{S}\}$$x(\beta, w^{*}, \delta^{*})\in \mathbb{Q}_{\{l_{1},\ldots,l_{h}\}}$

for $n=1,2$ ,suppressing ,$\beta$$\ldots$

$h+1$

(5.1)

. Suppose that there

.

(5.2)

and 6*.

$w^{*}$,$\overline{L}:=\{1,2, \ldots, k\}-L$$\overline{J}:=S-J$, we can write
For any row vector $x=$$x_{J}=\{x_{i}
:
i\in
J\}$
and
of
and
subvectors
and x-j arewill be partitioned into submatrices as follows:$(x_{1}, x_{2}, \ldots, x_{N})\in \mathbb{R}^{n}$$P^{\delta}(w^{*})_{JJ}=(P_{\dot{|}j}(w^{*})(1-\delta(j)))$, where. Also,$x=(x_{J}, x_{\overline{J}})$$x_{\overline{J}}=\{x_{i} :$x$$P^{\delta}(w^{*})=(_{P^{\delta}(w^{*})_{\overline{J}J}}^{P^{\delta}(w^{*})_{JJ}}$

,

.

and

$J:=\{j_{1},j_{2}, \ldots,j_{h+1}\}$

wheredefined.
For simplicity, we write.

i\in\overline{J}\}$$x_{J}$$P^{\delta}(w^{*})$,$P^{\delta}(w^{*})_{\overline{JJ}}P^{\delta}(w^{*})_{\overline{JJ})}$, $i\in J;j\in J$ and other submatrices are similarly$P^{\delta}(w^{*})=(\begin{array}{ll}P_{\mathrm{l}} P_{2}P_{3} Q\end{array})$.

Let $c(w^{*})=(c_{tj}(w^{*}))$ , where $c_{ij}(w^{*})=\dot{d}(i, w^{*})$ for $i\in S$ and $j\in\{1,2, \ldots, k\}$ . $C(w^{*})$
will be partitioned as done in the above:$C(w^{*})=(\begin{array}{ll}C_{JL} C_{\overline{JL}}C_{\overline{J}L} C_{\overline{JL}}\end{array})$,

suppressing .
Here we consider the following inequality system (cf. (3.5)).
$w^{*}$,,$x_{J}=\beta_{J}(1-\delta_{J})+x_{J}P_{1}+x_{\overline{J}}P_{3}$$(\mathrm{i}\mathrm{i})(\mathrm{i})$$x_{\overline{J}}=\beta_{\overline{J}}(1-\succ_{J})+x_{J}P_{2}+x_{\overline{J}}Q$

(iii)
(iv)

$x_{J}C_{JL}+x_{\overline{J}}C_{\overline{J}L}=\alpha_{L}$$x_{J}C_{\overline{JL}}+x_{\overline{J}}C_{\overline{JL}}<\alpha_{\overline{L}}$where $\beta_{J}(1-\delta_{J})=(\beta(i)(1-\delta(i));i\in J)$ ,componentwise relations.
and
We note that$\theta_{\overline{J}}(1-\succ_{J})=(\beta(i)(1-\delta(i));i\in\overline{J})$$<\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}$$x^{*}=(x_{J}^{*}, x \frac{*}{J})$

(5.3)

,
,

$\delta^{*}=(\delta_{J}^{*}, \delta\frac{*}{J})$satisfy (5.3) obviously

and$=\mathrm{a}\mathrm{n}\mathrm{d}$53Prom Assumption $(=)$ , it clearly holds thatand by (ii) in (5.3) we get, so that (I $-Q)^{-1}$ exists$l\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT} m_{\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}=-Q^{n}\ovalbox{\tt\small REJECT}}0$$x_{\overline{J}}=(\beta_{\overline{J}}(1-\succ_{J})+x_{J}P_{2})(I-Q)^{-1}$

,

(5.4)

where I is an identity matrix with the same dimensions as .
Also, since (i) in (5.3) includes onlywith respect to , it uniquely determines
and if andif
and are given. Thus (i) and (ii) in (5.3) determine uniquely(5.3),
(iii)
(5.4)
in
we
have
that
into
are given. Inserting from$Q$$\delta$$\delta_{J}$$x_{J}$$\delta_{J}$$\delta_{J}$$\delta_{\overline{J}}$$x_{\overline{J}}$$x_{J}$$\delta_{\overline{J}}$

.

(5.5)

$x_{J}(C_{JL}+P_{2}(I-Q)^{-1})=\alpha_{L}-l\succ_{J}(1-\delta_{\overline{J}})(I-Q)^{-1}c_{\overline{J}L}$satisfying (5.3).
Now, we denote by the set of all pairs$D$$(x_{J}\geqq
0)$satisfying (5.5) withLet
be the set of all ,$\hat{D}$$(x_{J}, \succ_{J})$$\succ_{J}=\delta\frac{*}{J}$$x_{J}$$D=${$x_{J}|$($x_{J}$,$\delta\frac{*}{J})\in\hat{D}$and$x_{J}\geqq 0$, that is,

}.

(5.6)

equations and $h+1$ unknown elements, we findObserving that (5.5) withthat $D$ is apolyhedral convex set with at least one dimension. Since (5.2) means thatwithis arelative interior point in $D$ , there exists $0<\gamma<1$ and ,$\succ_{J}=\delta\frac{*}{J}\mathrm{h}\mathrm{a}\mathrm{s}$$h$$x_{J}^{*}\in D$$x_{J}^{1}$$x_{J}^{*}=\gamma x_{J}^{1}+(1-\gamma)x_{J}^{2}$

Let,$x_{J}^{1}$$x \frac{1}{J}$,$\delta_{J}^{1}$

and$x \frac{2}{J}$,andchoosing
and

(5.7)

in (5.3) with $x_{J}=$be those determined uniquely thorough
,
,
. Let
,
satisfying (iv) in (5.3) by. We can assume thatandsufficiently near to . Applying Lemma 2.1 we get$(\mathrm{i})-(\mathrm{i}\mathrm{i})$$x_{J}^{2}$$x^{2}=(x_{J}^{2}, x \frac{2}{J})$$x^{1}=(x_{J}^{1}, x \frac{1}{J})$$\delta_{\overline{J}}=\delta\frac{*}{J}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}1\mathrm{y}$$x^{1}$$\delta^{2}=(\delta_{J}^{2}, \delta\frac{*}{J})$$x_{J}^{1}$.

$\delta_{J}^{2}$$\delta_{\overline{J}}=\delta\frac{*}{J}\mathrm{a}\mathrm{n}\mathrm{d}x_{J}=x_{J}^{2}$$( \delta_{J}^{1}, \delta\frac{*}{J})$$\delta^{1}=$$x^{2}$$x_{J}^{*}$$x^{1}=x(\beta, w^{*}, \delta^{1})$and$x^{2}=x(\beta, w^{*}, \delta^{2})$.

Thus, we have that$x(\beta, w^{*}, \delta^{*})=\gamma x(\beta, w^{*}, \delta^{1})+(1-\gamma)x(\beta, w^{*}, \delta^{2})$which implies$x_{J}^{2}\in D$$x(\beta, w^{*}, \delta^{*})\not\in \mathrm{e}\mathrm{x}\mathrm{t}(\mathbb{Q}\{l_{1},l_{2},\ldots,l_{h}\})$,. This completes the proof.

.

References[1] E. Altman. Constrained Markov Decision Processes. Chapmann&Hall/CRC, 1999.
[2] D. Assaf and E. Samuel-Cahn.
Probab., 35:693-706, 1998.

Optimal multivariate stopping rules.

J. Appl.

[3] H. P. Benson. An improved definition of proper efficiency for vector maximization
with respect to cones. J. Math. Anal Appl, 71:232-241, 1979.
[4] V. S. Borkar. Topics in controlled Markov chains. Longman Scientific&Technical,
Harlow 1999.

54[5] Y. S. Chow, H. Robbins, and D. Siegmund. Great expectations: the theor y of
optimal stopping. Houghton Mifflin Co., Boston, Mass., 1976.
[6] N. Purukawa. Characterization of optimal policies in vector-valued markovian decision processes. Math. Oper. Res., 5:271-279, 1980.

[7] N. Furukawa and S. Iwamoto. Stopped decision processes on complete separable
metric spaces. J. Math. Anal. APPl, 31:615-658, 1970.
[8] A. Hordijk. Dynamic programming and Markov potential theory. MathematicalCentre Tracts, No. 51. Mathematisch Centrum, Amsterdam, 1974.

[9] M. Horiguchi. Markov decision processes with astopping time constraint. To appear
in Mathematical Methods of Operations Research, 53:issue2,2001.
[10] M. Horiguchi, M. Kurano, and M. Yasuda. Markov decision process with constrained stopping times. Proceedings of 39th IEEE Conference on Decision andControl(CDC2000). Markov Decision Processes, 1:706-710, 2000.

[11] A. Irle. Minimax results and randomization for certain stochastic games. In: Ricceri
B, Stephen S $(eds.)Minimax$ Theory and Applications., pages 91-103, 1998.
[12] D. P. Kennedy. On aconstrained optimal stopping problem. J. Appl Probab.,
19:631-641, 1982.
[13] M. Kurano, J. Nakagami, and Y. Huang. Constrained markov decision processes
with compact state and action spaces: The average case. Optimization, 48:255-269,

2000.
[14] D. G. Luenberger. Optimization by vector space methods. John Wiley&Sons, Inc.,New York, 1969.
[15] D. C. Nachman. Optimal stopping with ahorizon constraint. Math. Oper. Res.,
5:126-134, 1980.

[16] Ulrich Rieder. On stopped decision processes with discrete time parameter. Stochastic Processes Appl, $3(4):365-383,$ 1975.
[17] J. Stoer and C. Witzgall. Convexity and Optimization in Finite Dimensions I.
Springer-Verlag, Berlin and Newyork, 1970.
[18] K. Wakuta. Optimal stationary policies in the vector-valued markov decision pr0cesses. Stochastic Processes and their Applications, 42:149-156, 1992