数理解析研究所講究録
978 巻 1997 年 128-135

128

A minimum average-variance inMarkov decision processes
和歌山大教育$($門田良信

Yoshinobu KADOTA$)^{*}$$\mathrm{A}\mathrm{b}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}^{\uparrow}$

This paper is concerned with the average-variance of Markov decision processes with countable states and finite actions. Sufficientconditions will be given to assure that there is a stationary deterministic policy which minimizes the average-variance in a class ofthe mean-optimal policies. The class of the policies is deteterminedby the quantity of the actions which do not satisfy the mean-optimal
equation.

1. Introduction.

As well as mean ( . expected average) rewards, variances and their related criteriaof Markov decision processes (MDP’s) have been studied by many authors. Many of
their works are overviewed by White(1988) and seen also in Filar, Kallenberg andLee(1989).
But to our knowledge, there are a few papers which are concerned with the minimization of the average-variance in the class of mean-optimal policies. The averagevariance is the applied form to MDP’s of the variance given by Kemeny and Sne11(1976).
In finite state MDP’s, Mand1(1971) investigates the asymptotic behavior of the averagevariance in details. He contributes to construct MDP’s whose mean rewards are thevariances for the given MDP’s. Kurano(1987) shows in general state MDP’s that
there is a stationary deterministic policy which minimizes the average-variance in the
restricted class of policies whose actions satisfy the mean-optimal equation.
In this paper, the MDP’s have countable states and finite actions. We show theexistence of a stationary deterministic policy which minimizes the average-variance inthe larger class of mean-optimal policies. The class is determined in relation to themean-optimal equation. As a corollary, if the state space is finite, the class is givenby the set of all mean-optimal policies.
In section 2, the necessary notations and the problem to be examined is stated. Also,
under an ergodic condition, the properties of mean-optimal policies are reviewed. In$\mathrm{v}\mathrm{i}\mathrm{z}$*Faculty of Education, Wakayama University, Wakayama 640, Japan\dagger Keywords and phrases: average-variance, Markov decision process, mean-optimal, mean-optimal
equation.
$AMS(Mos)\mathit{8}ubjectclaS\mathit{8}ifi_{C}ation:90\mathrm{C}40,60\mathrm{J}10$.

129

section 3, applying the equality given by Kurano(1987), we obtain a lemma which
describes Mand1(1971)s idea more generally. Owing to the lemma, the main theorem
is proved.

2. Definitions and notation.

Our MDP’s are specified by $(S, A, p, r)$ , where $S=\{0,1,2, \cdots\}$ is the set of states,
the subset $A(i)$ of is the set of actions available at each state $i\in S,$ $p=(p(a)_{i}j)$ isfor any $i\in S$ andthe matrix of transition probabilities satisfying that$a\in A(i)$ , and $r(i, a)$ is an immediate reward function defined on $\{(i, a);i\in S,$ $a\in$$A(i)\}$ . We assume thatis countable, each $A(i)$ is finite and that is uniformly
bounded, i.e., $|r(i, a)|\leq M$ for any $i\in S$ and $a\in A(i)$ .
The sample space is the product space $\Omega=(S\cross A)^{\infty}$ such that the projection
describes the state and the action at time of theto the n-th factor
process respectively for $n=0,1,2,$ .
such thatis a sequence of conditional probability
A policy) $=1$ for any history $(i_{0}, a_{0}, \cdots i_{n})\in(S\cross A)^{n}\mathrm{x}S$ . A( $A(i_{n})|i0,$ $a0,$ il,
policy is called Markov if $\pi_{n}(a|i0, a0, \cdots , i_{n})=\pi_{n}(a|i_{n})$ for any $a\in A(i),$ andoni)n. A Markov policy is called deterministic if there is a function(
with $f_{n}(i)\in A(i)$ for any such that $\pi_{n}(\{f_{n}(i)\}|i_{n}=i)=1$ for any $i\in S$ . A
deterministic policy is called stationary if $f_{n}=f$ for all $n=0,1,$ . The stationary
be the sets of all policies and stationary
policy is denoted by $\pi=f$ . Let anddeterministic policies, respectively.
Let $H_{n}=(X_{0}, \triangle_{0,1,n}\ldots, \triangle_{n-}x)$ for $n=0,1,2,$ . We assume for any $\pi\in\Pi$$j\in S$ and $a\in A(i)$ ,with $n=0,1,$$A$$\Sigma_{j\in \mathit{8}}p(a)_{ij}=1$

$S$

$r$

$S\cross A$$(X_{n}, \triangle_{n})$$n$$\cdots$$\pi=(\pi_{0}, \pi_{1}, \cdots)$$\pi_{n}$$\cdots,$$\pi_{n}$$i_{n}$

$n$

$\pi$

$i_{0},$$a_{0},$$\cdots$$f_{n}$

$\pi$

$S$

$n$

$\cdots$$\Pi$$\Pi_{S}$$\cdots$$\cdots,$$i,$$P^{\pi}(X_{n+1}=j|H_{n-1,n}\triangle-1, xn=i, \triangle_{n}=a)=p(a)_{ij}$.

determine the probability measure
An initial state $i\in S$ and a policy
on by the usual way. The expectation of a random variable with respect to.
is denoted by
For a policy , the long-run mean (or expected average) reward per unit time$\pi=(\pi_{0}, \pi_{1}, \cdots)$$P_{i}^{\pi}$$Y$$\Omega$$E_{i}^{\pi}(Y)$$P_{i}^{\pi}$$\pi$

starting from $i\in S$ is defined by(1)$x(i, \pi)=\lim_{narrow}\inf_{\infty}\frac{1}{n+1}E_{i}^{\pi}[_{k=}\sum_{0}^{n}r(x_{k}, \triangle k)]$.

The average-variance for the policy is defined, following to Kurano(1987), by$\psi(i, \pi)=\lim_{narrow}\sup_{\infty}\frac{1}{n+1}V_{i}\pi[_{k=0}\sum^{n}r(x_{k}, \triangle k)]$

,

130

where $V_{i}^{\pi}[Y]=E_{i}^{\pi}\{Y-Ei\pi(Y)\}^{2}$ for a random variable $Y$ . The average-variance isthe application to MDP’s of the variance given in Kemeney and Sne11(1976).
Let $x^{*}(i)= \sup\{x(i, \pi);\pi\in\Pi\}$ . If a policy
satisfies $x(i, \pi)*=x^{*}(i)$ for any$i\in S$ , we say
is mean-optimal. We denote by $\Pi(M)$ the set of mean-optimal
policies.
$\pi^{*}$$\pi^{*}$For any $f\in\Pi_{S}$ , let$m(f)_{ij}= \sum_{n=1}^{\infty}nP_{i}^{f}$( $x_{k}\neq j$ for$1\leq k<n,$ $X_{n}=j$ ),which is called the mean recurrence time to go from $i\in S$ to $j\in S$ . We shall set up

a condition.
Condition . There are a state $0\in S$ and a constant $b>0$ such that $m(f)_{i0}\leq b$
for all $i\in S$ and $f\in\Pi_{S}$ .
Remark 1. According to Ross(1970), if is finite and each stationary Markov
chain $\{p(f)ij;i,j\in S\}$ is irreducible, Condition I holds. Federgruen, Hordijk andTijms(1978) shows that Condition I holds if
exists independently of$i\in S$ and the limit is approached with exponential speed. Dekker and Hordijk(1992)
and Mann(1985) generalize Condition I to the multi-chain case.
Ross(1970) shows under Condition I that (i) $x(i, f)$ is independent of $i\in S,$
there exists a bounded vector $v=(v(i))$ satisfying
$I$

$S$

$\lim_{narrow\infty}p(f)_{ij}^{n}$$(\mathrm{i}\mathrm{i})$(2)$x^{*}+v(i)= \max_{a\in A(i)}\{r(i, a)+\sum_{j\in \mathit{8}}p(a)_{i}jv(j)\}$for any $i\in S$ ,where $x^{*}= \sup\{x(i, f);f\in\Pi_{S}\}$ , and (iii) If $f\in\Pi_{S}$ maximizes the term in thebrackets of (2) for any $i\in S$ , then $f\in\Pi(M)$ . Letting$v(i, f)= \lim_{\beta\nearrow 1}\sum\beta n\{E_{i}^{f}r(x_{n}, \triangle)n-n=\infty 0x(i, f)\}$Mann(1985) shows that there is$v(i)$ for $i\in S$ .

$f^{*}\in\Pi_{S}$for $f\in\Pi_{S}$ ,which satisfies the above (iii) with $v(i, f^{*})=$For the analysis of the mean-optimality, let(3)$\varphi(i, a)$(4)$K(i)$$=r(i, a)+ \sum_{j\in S}p(a)_{i}jv(j)-x^{*}-v(i)$$=$$\{a\in A(i);\varphi(i, a)=0\}$and

for any $i\in S$ .

Let $K=\mathrm{X}_{i\in s}K(i)$ . Let denote by $\Pi(K)$ the set of policies
that $\pi_{n}(K(i_{n})|i0, a0, i_{1}, \cdots, i_{n})=1$ for any history$\pi=(\pi_{0}, \pi_{1}, \cdots)$$(i_{0}, a0, \cdots i_{n})$

.

such

131

Let define a function$\overline{r}(i, a)$byfor any $i\in S$ and $a\in A(i)$ .

$\overline{r}(i, a)=\sum_{j\in S}p(a)_{i}j\{v(j)-hs\sum_{\in}p(a)_{i}hv(h)\}^{2}$is defined byofNotice that is uniformly bounded. Usingis defined by inf
limsup similarly as (1). For MDP’s specified byexists. Corresponding to (3), letsimilarly as . The bounded vector$r\mathrm{i}\sim \mathrm{n}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{a}\mathrm{d}$$\overline{r}$$r,\tilde{x}(i, \pi)$$(S, K, p, r)\sim,\overline{x}_{*}$$x^{*}$$\overline{v}=(\overline{v}(i))$$\overline{\varphi}(i, a)=\overline{r}(i, a)+\sum_{j\in \mathit{8}}p(a)_{i}j\overline{v}(j)-\overline{x}_{*}-\overline{v}(i)$for any $i\in S$ and $a\in A(i)$ .

for any $i\in S$ and $a\in K(i)$ . Corresponding to (4), let$\{a\in K(i);\overline{\varphi}(i, a)=0\}$ . Then,befor all $i\in S$ . Let a policy
for any $i\in S$ .
has the minimum averageKurano(1987) and Mand1(1971) show that.
variance within the class of policies satisfyingThen,$\overline{K}(i)=$$\tilde{\varphi}(i, a)\geq 0$$\tilde{f}\in\Pi(K)_{S}$$\overline{K}(i)\neq\emptyset$$\tilde{f}(i)\in\overline{K}(i)$$\tilde{f}\in\square (K)$$\Sigma_{k=0}^{\infty}P_{i}\pi(\triangle_{k}\not\in K(X_{k}))<\infty$

3. Class of policies to the minimum average-variance.
This section gives sufficient conditions to determine the class of policies wherein the previous section has the minimum average-variance. To the end,$\tilde{f}\in\Pi(K)_{\mathit{8}}$two lemmas are prepared.
Next Lemma 3.1 estimates the quantity of the actions which do not satisfy (2) forthe mean-optimal policies.
Lemma 3.1. Suppose that Condition I holds. If $\pi\in\Pi(M)$ , it follows that(5)$\lim_{narrow\infty}\frac{1}{n+1}\sum_{0k=}P^{\pi}(ix_{k}n=j, \triangle_{k}\not\in K(j))=0$

for any$i,$$j\in S$

Proof. We have from (3) that
(6)

Since
(7)

$\sum_{k=0}^{n}E^{\pi}i\varphi(xk, \triangle_{k})=\sum_{k=0}E\pi r(nix_{k}, \triangle_{k})-(n+1)x^{*}-v(i)+E^{\pi}iv(xn+1)$$\varphi(i, a)\leq 0$

for any $i\in S$ and $a\in A(i)$ , a policy$\lim_{narrow\infty}\frac{1}{n+1}\sum_{0k=}E\pi(i\varphi n(X_{k}, \triangle k))=0$

$\pi$

.

is mean-optimal if and only iffor $i\in S$ .

for any $j\in S$ since $A(j)$ is finite.
Let $\epsilon_{j}=\max\{\varphi(j, a);a\not\in K(j)\}$ . Then,
Take the terms $\varphi(j, a)=0$ away from (7), we get$\epsilon_{j}<0$(8)$\lim_{narrow\infty}\frac{1}{n+1}k=\sum_{0}\sum P\pi(ik=nj\in Sxj, \triangle_{k}\not\in K(j))\epsilon j=0$

.

132

(8) implies (5) immediately, completing the proof.

$\square$freely in all the proofs
For the sake of brevity, we shall omit the notationof the subsequent propositions if no confusion occurs. In paticular, the conditional
will be denoted by $E_{i}^{\pi}(v(X_{k1}+)|X_{k})$ .
expectation
In the proof of Lemma 3.2, we shall use the followig equality which is given by
Lemma 3.2 in Kurano(1987).
$\triangle_{k}$$E_{i}^{\pi}(v(Xk+1)|Xk, \triangle_{k})$(9)$E_{i}^{\pi} \{_{k=}\sum_{1}(v(x_{k})-E_{i}\pi(v(x_{k})|X_{k}-1))\}n2=\sum_{k=0}^{n-1}E_{i}\pi r\sim(x_{k}, \triangle_{k})$Lemma 3.2.
that
$n=0,1,2,$$Suppo\mathit{8}e$.

Condition I holds. Then, it holds for any policy $\pi\in\Pi$ and$\cdots$$| \{V_{i}^{\pi}(\sum r(Xk, \triangle k))-V\pi(\sum_{0k=}^{n}\varphi(xk, \triangle_{k}))k=n0i\}-\sum_{=0}E_{i}\pi\overline{r}k(xnk, \triangle_{k})|$(10)$\leq 2[\{_{k0}^{n-1}\sum_{=}E^{\pi}\overline{r}(ixk, \triangle k)\}^{\frac{1}{2}}+M_{1}]\{V_{i}^{\pi}(\sum_{0k=}\varphi(Xnk, \triangle_{k}))\}^{\frac{1}{2}}+o(n)$,and $o(n)$ is a number such that $\lim_{narrow\infty}o(n)/n=0$ .
is aProof. Let $\pi\in\Pi$ . For a random variable and a constant , it follows that
$E(Y-E(Y))2=E(Y-\mu)^{2}-(E(Y)-\mu)^{2}$ . Substitute $Y=\Sigma_{k=0^{r}}^{n}(X_{k})$ and $\mu=$
to the equality. Using (6), we havewhere$M_{1}$$Con\mathit{8}tant$

$Y$

$\mu$

$\Sigma_{k=0}^{n}(x*+E_{i}^{\pi}\varphi(X_{k}))$(11)$V_{i}^{\pi} \{\sum_{0k=}nr(x_{k})\}$$=E_{i}^{\pi} \{_{k=0}\sum^{n}(r(x_{k})-x-E^{\pi}*(i\varphi X_{k}))\}2$$-\{v(i)-Ei\pi v(xn+1)\}^{2}$

On the other-hand, we have from the definition of(12)$\overline{r}$.

and (9) that$\sum_{k=0}^{n}E^{\pi}(i\overline{r}(x_{k}))=E_{i}^{\pi}\{_{k=0}\sum^{n}(v(xk)-E\pi(iv(x_{k+1})|x_{k}))-(v(X_{0})-v(x_{n}+1))\}^{2}$

Expand (12) with the form $a^{2}-2ab+b^{2}$ . Substitute (3) toin $2ab$ following:(13)$a^{2}$. Rearrange the terms.

$E_{i}^{\pi} \{v(x+1)\sum_{1k=}^{n}(v(Xk)-E_{i}\pi(v(Xk)n|x_{k}-1))+v(x_{n+1})(v(X_{0})-E_{i}^{\pi}(v(Xn+1)|X)n)\}$, apply the Schwarz inequality to (13) and use (9). Since is bounded,
After sharing(13) is represented by $o(n)$ . Then, (12) turns out to be$v$$E_{i}^{\pi}$(14)$\sum_{k=0}^{n}E^{\pi}\overline{r}i(x_{k})=E_{i}^{\pi}\{\sum_{=k0}^{n}(r(Xk)-x^{*}-\varphi(X_{k}))\}^{2}+o(n)$

.

133

Comparing (14) with (11), we have$\sum_{k=0}^{n}E_{i}\pi\overline{r}(xk)=Vi\pi(k=\sum^{n}r(x0k))+V_{i}^{\pi}(\sum_{0k=}^{n}\varphi(x_{k}))$(15)$-2E_{i}^{\pi} \{_{k=0}\sum^{n}(r(Xk)-X-E_{i}^{\pi}*\varphi(Xk))\sum_{f=0}^{n}(\varphi(x_{\ell})-E_{i}^{\pi}\varphi(x\ell))\}+o(n)$.

Substitute (3) to $r(X_{k})-x^{*}$ in (15). In the same way as (13), apply the Schwarz
should be taken to satisfy
inequalities to both terms and use (9). The constant$M_{1}$

for all$M_{1}\geq\{E_{i}^{\pi}(v(X\mathrm{o})-E_{i}^{\pi}(v(x_{n+1})|Xn))^{2\frac{1}{2}}\}$

Since

$v$

is bounded, such

Theorem 3.3.

$Supp_{\mathit{0}\mathit{8}}e$

(16)

(18)

$\square$Condition I holds. Let $\pi\in\Pi$ satisfy$\lim_{narrow}\sup_{\infty}\frac{1}{n+1}\sum_{0k=}E\pi(i\overline{\varphi}n(X_{k}, \triangle k))\geq 0$$hold_{\mathit{8}}$.

exists. This completes the proof.

and$\lim_{narrow\infty}\frac{1}{n+1}V^{\pi}(i\sum_{0k=}(\varphi(Xnk, \triangle_{k}))=0$(17)
Then, it

$M_{1}$$n$for any $i\in S$.

that$\psi(i,\tilde{f})=\overline{x}(i,\tilde{f})\leq\overline{x}(i, \pi)=\psi(i, \pi)$Proof.

for any $i\in S$.

Dividing (10) by $n+1$ , let tend to infinity. We have from (16) that$\overline{x}(i, \pi)=\psi(i, \pi)$ for any $i\in S$ .
, since
In particular,$\varphi(j,\tilde{f}(j))=0$
for any $j\in S$ .
is given similarly as (6).
andThe relation between
Then (17) implies$n$$\overline{x}_{*}=\overline{x}(i,\overline{f})=\psi(i,\tilde{f})$$\sum_{k=0^{E_{i}}}^{n}\pi\overline{r}(x_{k})$$\Sigma_{k=0}^{n}E^{\pi}i\tilde{\varphi}(xk)$$\overline{x}(i, \pi)=\overline{x}_{*}+\lim_{narrow}\sup_{\infty}\frac{1}{n+1}\sum_{0k=}^{n}E^{\pi}(i\overline{\varphi}(x_{k}))\geq\overline{x}_{*}$.

Thus (18) is obtained, completing the proof.

$\square$Corollary 3.4. Suppose Condition I holds. If a policy(19)$\lim_{narrow\infty}\frac{1}{n+1}\sum_{0k=}^{n}P_{i}^{\pi}(\triangle_{k}\not\in K(X_{k}))=0$

then $\pi\in\Pi(M)$ and$\mathit{8}atisfieS(\mathit{1}\mathit{6})$and (17).

,$\pi\in\Pi \mathit{8}atisfieS$

for any $i\in S$,

134

Proof. The equality (19) is written by(20)$\lim_{narrow\infty}\frac{1}{n+1}\sum_{0k=}^{n}\sum\sum_{jj\in Sa\not\in K()}P^{\pi}i(X_{k}=j, \triangle_{k}=a)=0$.

Notice that $\varphi(j, a)=0$ for $a\in K(j)$ . By the bounded convergence theorem, (20)for $a\in K(j),$ (20) implies (17)implies (7), so that $\pi\in\Pi(M)$ . Since
similarly.
Let $|\varphi(i, a)|\leq M$ for some $M>0$ and for any $i\in S$ and $a\in A(i)$ . Notice that$\overline{\varphi}(j, a)\geq 0$$E_{i}^{\pi}( \sum_{0k=}n\varphi(x_{k}))^{2}=\sum_{k=0}^{n}E^{\pi}(i\varphi(x_{k})^{2})+2\sum_{k=1}^{n}\sum_{=\ell 0}^{1}E^{\pi}|i\varphi k-(x_{\ell})\varphi(x_{k})|$$E_{i}^{\pi}|\varphi(x_{\ell})\varphi(x_{k})|\leq M^{2}P_{i}^{\pi}$($\triangle\ell\not\in K(x_{l})$andfor $0\leq\ell\leq k$ and $k=0,1,2\cdots$ . Then, (19) implies$1)=0$ , so that (16) holds. The proof is complete.

$\triangle_{k}\not\in K(X_{k})$and)$\lim_{narrow\infty}E_{i}^{\pi}(\Sigma_{k}n\varphi=0(x_{k}))^{2}/(n+$$\square$Corollary 3.5. Suppwse Condition I holds. If is finite, (18) holds for any$\pi\in\Pi(M)$ .
Proof. By summing (5) in $j\in S$ , we see that $\pi\in\Pi(M)$ satisfies (19). Then,
Corollary 3.4 and Theorem 3.3 implies (18). The proof is complete.
$S$$\square$

References[1] R. Dekker and A. Hordijk(1992), Recurrence conditions for average and Blackwell optimality in denumerable state Markov decision chains, Mathematics ofReseach, 17, 2, 271-289.
$Operati_{\mathit{0}}n\mathit{8}$[2] A. Federgruen, A. Hordik and H. C. Tijms(1978), Recurrence conditions indenumerable state Markov decision processes, Dynamic Programming and Its
Applications, edited by M. L. Putterman, 3-22.
[3] J.A. Filar, L.C.M. Kallenberg and H.M. Lee(1989), Variance-penalized Markov
decision processes, Mathematics of Operations Reseach, 14, 1, 147-161.
[4] J.G. Kemeny and J.L. Sne11(1976), Finite Markov Chains, Springer-Verlag, NewYork.
[5] M. Kurano(1987), Markov decision processes with a minimum-variance criterion,
and Applications., 123, 572-583.
Journal of Mathematical$Analy_{\mathit{8}is}$135[6] P. Mand1(1971), On the variance in controlled Markov chains, Kybernetika, 7,
1, 1-12.

[7] E. Mann(1985), Optimality equations and sensitive optimality in bounded Markov
decision processes. Optimization, 16, 5, 767-781.
[8] S.M. Ross(1970), Applied Probability Models with Optimization Applications,
Holden-Day, Inc., San Francisco.
[9] D.J. White(1988), Mean, variance, and probabilistic criteria in finite Markov
decision processes: A review, Journal of Optimization Theory and Applications,56, 1, 1-29.