数理解析研究所講究録 1207 巻 2001 年 147-156147
偏差行列とマルコフ決定過程の精密割引最適化基準へのその応用
和歌山大学

概要:

門田良信 (Yoshinobu Kadota)

可算状態空間と有界利得系をもつマルコフ決定過程に対して, マル

コフ連鎖に関するある再帰条件を与える. そして, 定常政策に対する偏差行列の存在, ローラン展開の係数の連続性および Blackwell-最適定常政策の存在を導く. その条件のもとでは, マルコフ連鎖が周期的再帰クラスを可算個数もつことができる. また偏差行列の正確な表現を導く.

1. 導入
有限状態空間をもつマルコフ決定過程 (以後$\mathrm{M}\mathrm{D}\mathrm{P}$と略す) に対して, Miller andVeinott[13] および Veinott[14] は割引総期待利得のローラン展開を使って Blackwell-最適定常政策を導いている. その後, 可算状態空間をもつ場合の研究が進み, Dietz andNollau[7], Kadota[10], Mann[12] および Dekker and Hordijk $[5, 6]$ を含む多くの結果が得られている. Yushkevich[15] は一般の有限状態空間をもつ場合にもこの問題を考えている.

それらの多くは定常政策に対応したマルコフ連鎖 (以後 MC と略す) に関する再帰条件を与え, 有限個数の再帰クラスをもつ場合を研究している. [5] は可算個の非周期的クラスをもつ場合を考えているが, 彼等 $[5, 6]$ は作用素論的接近を試みており$\mathrm{M}\mathrm{C}$の再帰的構造に関して十分な議論をしていない.
ここでは可算状態空間と有界利得系をもつ MDP に対してある再帰的条件 (条件 (I)$)$

を仮定して, 定常政策に対応した MC に対する偏差行列の存在, ローラン展開の係数の連続性および Blackwell-最適定常政策の存在を導く. 解析方法としては MC のエル
ゴード分解を用いる.

この報告の特徴は (i) 条件 (I) によってマルコフ連鎖が周期的再帰クラスを可算個数もつ場合を考察していること, (ii) 偏差行列の具体的な表現が得られることにある.
第 1, 2 節では基本的な補助定理を与え, 主要な結果は第 3, 4 節で導く.
標準的な MDP を $(S, A, p, r)$ で表す. ここで, $S=\{1,2, \cdots\}$ は可算状態空間, $A(i)$は各状態 $i\in S$ に対応する距離空間 $A$ の部分集合, $p=(p(a)_{ij})$ は推移確率で任意の

148$i\in S,$ $a\in A(i)$[こ対してを満たし, $r(i, a)$ は $\{(i, a);i\in S, a\in A(i)\}$$\Sigma_{j\in S}p(a)_{ij}=1$上で有界な $(|r(i, a)|\leqq M)$ 直接禾|」得とする.
時刻$\ldots,$

ま,での決定は, 履歴 $(i_{0}, a_{0}, \cdots, i_{n})\in(S\cross A)^{n}\cross S$ に対して$n$$i_{n})=1$$S$を満たす条件付確率$\pi_{n}$であり, 政策上の関数 $f$ があって任意の $i\in S$ と$i)=1$となるとき,$\pi$$n$$\pi=(\pi_{0}, \pi_{1}, \cdots)$$\Delta_{n}$は, それぞれ時刻決定を表すものとする. このとき, 初期状態 $i_{0}\in S$ と政策が定まり, 任意の $n=0,1,$$\cdots$, ( , 勾, .
$i_{0}$$\cdot$., )$i_{n}$$\pi$,$i_{1}$$\pi_{n}(\{f(i)\}|i_{n}=$を定常政策とよび $\pi=f$ と表す. 定常政策の全体を$X_{n},$$a_{0},$

は決定の列とする. い[こついて $f(i)\in A(i)$ かつ標本空間を $\Omega=(S\cross A)^{\infty}$ とする. 確率変数

$P_{i_{0}}^{\pi}$$\pi_{n}(A(i_{n})|i_{0},$によって$\Omega$$\mathcal{F}$

$n$

で表す.

での状態と

上の確率測度$\in(S\cross A)\cross S,$ $a_{n}\in A(i_{n}),$$j\in S$とボレル集合 $B\subset A(i_{n})$ に対して,$P_{1}^{\pi_{0}}.(\Delta_{n}\in B|i_{0}, a_{0}, \cdots, i_{n})=\pi_{n}(B|i_{0}, a_{0}, \cdots, i_{n})$および$P_{i_{0}}^{\pi}(X_{n+1}=j|i_{0}, a_{0}, \cdots, i_{n}, a_{n})=p(a_{n})_{i_{\hslash}j}$が成立する.
$\rho>0$$P_{i}^{\pi}$による $Y$ の期待値を$E_{i}^{\pi}(Y)$で表す.

とし, 割引率を $\beta=1/(1+\rho)$ とする. 政策$\pi$を使ったときの各初期状態に対応した割引総期待利得のベクトルは,$V_{\rho}( \pi)=(E^{\pi}\dot{.}\{\sum_{n=0}^{\infty}\beta^{n+1}r(X_{n}, \triangle_{n})\};i\in S)$

によって与えられる. 政策$\pi^{*}$

は, 任意の

$\pi$

に対して

$V_{\rho}(\pi^{*})\geqq V_{\rho}(\pi)$であるという. (ただし, 不等式は成分毎にとるものとする. ) 政策

ならば k 割引最適$\pi^{*}$

は, 任意の

$\pi$

に

対して

(1)

$\lim_{\rhoarrow 0}\inf_{+}\rho^{-n}(V_{\rho}(\pi^{*})-V_{\rho}(\pi))\geqq 0$

ならば -割引最適であるという. また, 任意の
$n$

$n$

に対して -割引最適ならば, Blackwell$n$

最適とよぶ.

推移行列は任意の$f\in \mathcal{F}$に対して $P(f)=(p(f(i))_{ij})$ によって与えられる. 以下においては記号 (f) は適宜省略して $P,$
$E_{a},$$\mathrm{I},$$Q,$ $H$$P^{0}=I$(単位行タリ ) とし, $P$ のP*=(p わ;

して,

$i,$

$j\in S$ )$i,$$j\in S$

,

$n$

個の積を

[こ対して

とすると,

$P^{n}(i, E)= \sum_{j\in E}p_{\dot{\iota}j}^{n}$$P^{*}(i, S)=1$等と表し, また後に定義されるものも$P^{*},$

$R,$

$T$

,

等と表す.

エノレゴード定理 [こより,る.

.

$p_{1j}$$P^{n}=(p_{\dot{\iota}j}^{n}; i,j\in S)$とする. MC の平均$p_{\dot{\iota}j}^{*}= \lim_{narrow\infty}(n+1)^{-1}\sum_{k=0}^{n}p_{ij}^{k}$$PP^{*}=P^{*}P=P^{*}$$P^{*}(i, E)= \sum_{j\in E}$が存在すとなる. 部分集合 $E\subset S$ に対

p わと表す. いま, 任意の $i\in S$ に対して

ならば, $P$ を non-dissipative とよぶ.

149
空間 $\{P(f);f\in \mathcal{F}\}$ に次の再帰条件を定義する.

条件 (I). 任意の $i\in S,$ $E\subset S,$ $n=1,2,$$\ldots,$$f\in \mathcal{F}$に対して, 次を満たす定数 $B$ が

存在する.

(2)

$| \sum_{k=0}^{n}\{P(f)^{k}(i, E)-P(f)^{*}(i, E)\}|\leqq B$.

$P(f)$ が Doeblin 条件を満たすかあるいは偏差行列をもてば,

各$f\in \mathcal{F}$に対して (2)を満たす $B$ は存在する. (前者については [7], Hordijk[9] および [10] を参照. 後者については第 3 節の等式 (10) を参照. )$\mathcal{F}$上での一有界性は後の第 4 節で偏差行列の連続性を導く. 条件 (I) &こ関する 2, 3 の性質は Kadota[ll] 1 こ見られる.
$f\in \mathcal{F}$に対して, $R(f)$ ,$\{E(f)_{a}; a\in \mathrm{I}(f)\}$$T(f)$

をそれぞれ再帰的状態, 過渡的状態の集合とする.

を再帰クラスの族とする. d(f)。を各再帰クラス E(f)。の周期,${}_{a}C(f)_{0},{}_{a}C(f)_{1},$ $\ldots,{}_{a}C(f)_{d_{a}-1}$をその周期的クラスとする. 次の補助定理は以後の議論において基本的である.
補助定理 1. 条件 (I) を仮定する. 各 $P(f)$ は non-dissipative であり,
$a\in \mathrm{I}(f),$ $f\in \mathcal{F}\}$$d=1.\mathrm{c}.\mathrm{m}.\{d(f)_{a}$;は有限である.

正明. (2) を $n+1$ で害リリ $narrow\infty$ とすると, $i\in S$ and $E\subset S$ (こ関して一

(3)

(こ

$\lim_{narrow\infty}\frac{1}{n+1}\sum_{k=0}^{n}P(f)^{k}(i, E)=P(f)^{*}(i, E)$が存在する. (3) で $E=S$ とすること (こより, $P(f)$ {ま non-dissipative となる.

最小公倍数が存在しないと仮定すると,よび limn\rightarrow \sim d(fn)a、 $=\infty$ を満たす

と表す.

を周期

$E_{n}(f_{n})$帰クラスとする.

$k_{n}$となる自然数とする.
て$d_{n}$$\{f_{n}\}\subset \mathcal{F},$$\cdots,$$k_{n}$

を任意の$G_{n}(f_{n})$に対して,$<\ldots$$a_{n}\in \mathrm{I}(f_{n})$と周期的クラス $\{C(f_{n})_{r} ; r=0,1, \ldots, d_{n}-1\}$ をもつ再$n$

{こ対して $k_{n}+1\leqq d_{n}/2$ かつ$=U_{r=0}^{k_{n}}C(f_{n})_{r}$$P(f_{n})^{*}(i_{n}, G_{n}(f_{n}))=(k_{n}+1)/d_{n}\leqq 1/2$

$r=0,1,$

お<d(五)anが存在する. $d_{n}=d(f_{n})_{a}$,$2\leqq d(f_{0})_{a_{\mathit{0}}}<d(f_{1})_{a_{1}}<\ldots$$P(f_{n})^{r}On$’$\lim_{narrow\infty}k_{n}=\infty$とすると, 任意の $i_{n}\in C(f_{n})_{0}$ に対しである.

$G_{n}(f_{n}))=1$

一方, 任意の $i_{n}\in C(f_{n})_{0}$ ととなる. 従って, 任意の

$n$

に対して

$| \sum_{r=0}^{k_{n}}\{P(f_{n})^{r}(i_{n}, G_{n}(f_{n}))-P(f_{n})^{*}(i_{n}, G_{n}(f_{n}))\}|\geqq(k_{n}+1)/2$. となる. これは (2) に反する. よって示された.

口150
2. 周期の最小公倍数に関する補助定理
この節では補助定理 1 から得られる -段階 MC に関するエルゴード的性質につい$d$て》 2 つの補助定理を準備する.
$f\in \mathcal{F}$を固定しておく. 1 単位時間の推移確率が

階 MC とよびを定義する.
$n$$P^{d}$

で表す.

$(_{R}p^{d})_{ij}^{n}$を,$p_{ij}^{*},$$P^{d}$$P^{*}(i, E)$$p_{ij}^{d}$によって与えられる MC を d-段の定義と同様にして,に対して$P^{d}$$p_{ij}^{d*},$$P^{d*}(i, E)$

によって $i\in S$ を出発して途中 $R$ を通ることなく時刻に $j\in S$ に到達する確率とする.

$({}_{R}P^{d})^{+}(i, E)= \sum_{n=1}^{\infty}({}_{R}P^{d})^{n}(i, E)$$E\subset S$に対して,$({}_{R}P^{d})^{n}(i, E)= \sum_{j\in E}(_{R}p^{d})_{ij}^{n}$

,

と表す.

行タリ $A=(a_{ij};i,j\in S)$ に対して, $||A||= \sup_{i\in S}\{\Sigma_{j\in S}|a_{ij}|\}$ とする. $N(S)$ を$||A||<\infty$となる $A$ のノノレム空間とする. このとき $A,$ $B\in N(S)$ について,$||A||||B||$ が成り立つ.

以後省略して,$\Sigma_{j\in S}a_{ij}b(j, E)$

$||$

AB

$||\leqq$

を AB(i, $E$ ) で, $A(i, E)-B(i, E)$

を $(A-B)(i, E)$ で表すことがある.

次の補助定理 2 の (5) は Chung[4, \S I6, pp32] の定理 4 の系の修正であり, (6) はDoob[8, pp208] (5.14) の修正である.
補助定理 2.

$\mathrm{M}\mathrm{C}P$(ま non-dissipative であり, $d=1.\mathrm{c}.\mathrm{m}.\{d_{a};a\in \mathrm{I}\}$は有限と仮定する. このとき任意の $i\in S,$ $E\subset S$ に対して次の等式が成立する.

(4)$\sum_{r=0}^{d-1}P^{r}(P^{nd}-P^{*})(i, E)=\sum_{r=0}^{d-1}P^{r}(P^{nd}-P^{d*})(i, E)$,$n=0,1,$$\cdots$

.

.

(5)

$P^{d*}(i, E)= \sum_{j\in R}\sum_{n=1}^{\infty}(_{R}p^{d})_{ij}^{n}P^{d*}(j, E\cap R)$

証明.

$P$

が non-dissipative より$P^{d}$

もそうなる.

Scheff\’e の定理 (Hordijk[9]のLemma 4.11 または Billingsley[2, pp224] を使って $P^{nd+r}(i, E)$ は $E\subset S$ に関して一様に $P^{r}P^{d*}(i, E)$ に収束する. このことと (3) より,
$)$

(6)

$P^{*}(i, E)= \frac{1}{d}\sum_{r=0}^{d-1}P^{r}P^{d*}(i, E)$が成立し, 従って (4) が成立する.
$i\in T$

各

(7)

$n$

と仮定して (5) を示せば十分である. $R$ への到達時刻に関する分解定理により,{こついて$P^{nd}(i, E)= \sum_{j\in R}\sum_{k=1}^{n}(_{R}p^{d})_{ij}^{k}P^{(n-k)d}(j, E\cap R)+P^{nd}(i, E\cap T)$

151が成立する. $narrow\infty$ とすると, (7) の右辺の第 1 項について極限と和に関する交換ができる. [4, \S I.5,

] の Lemma$\mathrm{p}\mathrm{p}20$$\mathrm{A}$を$\sum_{k=1}^{\infty}(_{R}p^{d})_{ij}^{k}>0$となる各 $j\in R$ [こ適用すれば,(5) が導かれる.

口

表記として, $Q_{n}(i, E)=\Sigma_{k=0}^{n}\Sigma_{r=0}^{d-1}P^{r}(P^{kd}-P^{*})(i, E)$ および $Q(i, E)= \lim_{narrow\infty}Q_{n}(i$ ,$E)$としておく.

[4] の意味での状態の閉集合に対して, 制限された MC’s を$P_{(a,r)}^{d}=(p_{ij}^{d};i,j\in {}_{ar}C)$と定義する.

とくに i\in E。と$a\in \mathrm{I}$

補助定理 3. 条件 (I) を仮定する. 任意のやに対して。$Q(i, E)=$$a\in \mathrm{I}$に対して, $||aQ||\leqq 2B$ を満たすが存在する.

$aQ(i, E)$

証明.

の存在をいうために,$aQ(i, E)$$\nu=0,1,$ $\ldots,$ $d_{a}-1$ (こついて$\sum_{n=0}^{\infty}||\sum_{r=0}^{d-1}P_{a}^{r}(P_{a}^{nd}-P_{a}^{*})||<\infty$$(p_{ij}^{d_{a}}; i,j\in {}_{a\nu}C)$

を考える.

このとき,

(3) G こおいて $n=md_{a}$ ,を満たす自然数$|N_{0}^{-1}\Sigma_{l=1}^{N_{0}}(p_{ik}^{\ell d_{a}}-p_{ik}^{d*})|<\epsilon_{0}$(こ対して,$p_{ik}^{n(i)d_{a}}>\epsilon_{0}$が存在する. またについて,d。の代りに$d$とおくと,$E=\{k\}$$\epsilon_{0}=p_{0}/2$$N_{0}$$\delta\leqq p_{ik}^{nd_{a}},$である.

$p_{ik}^{d*}\leqq 1$$N_{2}=N_{0}+N_{1},$だから,$\langle$

で. (4) より,

$i\in {}_{a\nu}C$(こ対してが存在する. 従って, ある $1\leqq n(i)\leqq N_{0}$が成立する. 一方, $n\geqq N_{1}$ ならば$p_{ik}^{d*}=p_{kk}^{d*}$

と任意の

を示す.

$P_{a}^{d*}=P_{a}^{d_{a}*}$と表してお$p_{0}= \max\{p_{jj}^{d*} ; j\in {}_{a\nu}C\}=p_{kk}^{d*}>0(k\in {}_{a\nu}C)$$i\in {}_{\alpha\nu}C$$=(p_{ij};i,j\in E_{a})$と表す.

$Q(i, E\cap E_{a})$ある.

$P_{a}$$|p_{kk^{a}}^{nd}-p_{kk}^{d*}|<\epsilon_{0}$$\delta=\epsilon_{0}^{2}$となる$N_{1}$(ことる. 任意の $n\geqq N_{2}$ ,$|p_{ik}^{nd_{a}}-p_{ik}^{d*}|\leqq 1-\delta$を得る. この不等式 (まとしても成り立つ.

任意の $0<\epsilon<1$ に対して, $(1-\delta)^{m}<\epsilon$ となる $m$ をとり, $N_{\nu}=mN_{2}$ とおく.

Doob[8, pp197] の Case(b) により,
く.

$n$と $r=0,1,$(8)を得る. (8) を$\cdots,$$N_{a}-1$$||P_{(a,\nu)}^{N_{\nu}d}-P_{(a,\nu)}^{d*}||<\epsilon$(こ対して,となる. $N_{a}= \max\{N_{\nu}\}$ とお$||P_{a}^{N_{a}d}-P_{a}^{d*}||<\in$

かつ$||P_{a}^{(nN_{a}+r)d}-P_{a}^{d*}||\leqq||P_{a}^{nN_{a}d}-P_{a}^{d*}||\leqq||P_{a}^{N_{a}d}-P_{a}^{d*}||^{n}$$r$と $n$ について加えると, 求める結果を得る. (2) 上り $||Q_{n}(\cdot, \cdot\cap E_{a})||\leq 2Barrow$

だから $||aQ||\leqq 2B$ となって有界性も示される.

3. 偏差行列の存在
この節では偏差行列の存在およびその表現と性質について考察する.
割引率 $\beta=1/(1+\rho)(\rho>0)$ に対して,(9)$H_{\rho}(i, E)= \sum_{n=0}^{\infty}\beta^{n}\{(P^{n}-P^{*})(i, E)\}$口152
とおく. いま, $H(i, E)= \lim_{\rhoarrow 0+}H_{\rho}(i, E)$ が存在して, $H=(H_{ij})\in N(S)$ と $H(i, E)=$$\sum {}_{j\in Eij}H$(ただしを満たすとき, $H$ を偏差行列とよぶ.

$H_{ij}=H(i,$ $\{j\})$ )定理 4. 条件 (I) を仮定する. このとき任意の $P$ に対して,(i) $||H||\leqq 2B$ を満たす偏差行列 $H$ が存在し, 次の式が成立する.
(10)$H(i, E)= \sum_{n=0}^{\infty}\sum_{r=0}^{d-1}P^{r}(P^{nd}-P^{d*})(i, E)+\frac{1}{d}\sum_{r=0}^{d-1}(\frac{d-1}{2}-r)P^{r}P^{d*}(i, E)$(ii) 便宜上 $H$ をえられた$H_{\rho}$.

と表す. このとき, $0\leqq\rho<\infty$ に対して (9) and (10) にょって与$H_{0}$

は $N(S)$ のなかで一意に定まり, $(I-\beta P)H_{\rho}=H_{\rho}(I-\beta P)=\beta(I-P^{*})$

かつ $P^{*}H_{\rho}=H_{\rho}P^{*}=O$ を満たす. ここで $O$ は零行列のこととする.

証明. 一般性を失うことなくため [こは, $Q(i, E)$ のそれを$\mathrm{A}\mathrm{a}$$i\in T$であり I は可算としてよい. (10) の存在をいう

えばよ. $b(j)= \sum_{r=0}^{d-1}P^{r}(j, E)$ とお 1 ‘て, 式 (4), (5),$\mathrm{A}\mathrm{a}$(7) を $Q_{n}(i, E)$ に代入すると,$Q_{n}(i, E)= \sum_{s\in R}\sum_{k=1}^{n}\sum_{\ell=1}^{k}(_{R}p^{d})_{is}^{\ell}\{\sum_{j\in S}(p^{(k-\ell)d}-p^{d*})_{sj}b(j)\}+\sum_{j\in T}\sum_{k=1}^{n}p_{ij}^{kd}b(j)$(11)$+ \sum_{j\in S}(\delta_{ij}-p_{\dot{\iota}j}^{d*})b(j)-\sum_{s\in R}\sum_{k=1}^{n}\sum_{\ell=k+1}^{\infty}(_{R}p^{d})_{is}^{\ell}(\sum_{j\in S}p_{sj}^{d*}b(j))$

が得られる. ここで,$\delta_{ij}$はクロネッカーのデノレタである.

$P^{d}$

は non-dissipative だから,$\sum_{\ell=k+1}^{\infty}({}_{R}P^{d})^{\ell}(i, R)=P^{kd}(i, T)$が成立する.

(2) より, $0 \leqq\sum_{k=0}^{\infty}P^{kd}(i, T)\leqq B$ である. よって, (11) の最後の 3 っの

項は $narrow\infty$ のときに絶対収束する.

任意の$\epsilon>0$に対して,$K\subset \mathrm{I}$を$(_{R}p^{d})^{+}(i, \bigcup_{a\in K}E_{a})\geqq 1-\epsilon/(3B)$を満たす有限集合とする. 補助定理 3 より, すべての $j\in E_{a},$ $a\in K,$ $E\subset S$ に対して,$Q_{n})(j, E\cap R)|<\epsilon/3$

(12)

となる

$n$

$|(_{a}Q-$をとる. このとき$\lim_{narrow\infty}\mathrm{I}\mathrm{I}_{0}(\sum_{k=1}^{n}(_{R}p^{d})_{s}^{k}\dot{.})Q_{n}(s, E)=\mathrm{I}\mathrm{I}(\sum_{ka=1}^{\infty}(_{R}p^{d})_{is}^{k})_{a}Q(s, E)$が成り立つ. コーシーの級数積の定理より, (11) の右辺の初項は (12) に収束する. よって $Q(i, E)$ は存在する.

式 (12) を $D(i, E)$ で表す. 補助定理 3 上り, $||D||\leqq 2B$ を得る. 従って $D(i, E)=$$\sum_{j\in E}D_{ij}$となり, (11) より $Q(i, \cdot)$ もそして $H(i, \cdot)$ も同じ性質をもつことが解る.

153$H_{\rho}$

が $H$ に収束することを示す. (4) を使$\mathfrak{U}$$\mathrm{a},$(9) の項を$\Sigma_{n=0}^{\infty}\beta^{nd}\{\sum_{r=0}^{d-1}\beta^{r}P^{r}P^{d*}\}$と比較することにより, 次式を得る.

.

(13)$\beta$$H_{\rho}= \sum_{n=0}^{\infty}\sum_{r=0}^{d-1}(\beta P)^{r}\{\mathcal{B}^{nd}(P^{nd}-P^{d*})\}+\frac{1}{1-\beta^{d}}\{\sum_{r=0}^{d-1}\beta^{r}(P^{r}-\frac{1}{d}\sum_{k=0}^{d-1}P^{k})P^{d*}\}$

を 1 に近づけると, アーベルの定理より (13) の右辺の初項は $Q$ に収束する. (13) の最後の項にロピタルの定理を適用する.

において $j\in E$ について和をとると (10)$H_{ij}$が導かれる.

(2) より$|H_{\rho}(i, E)|\leqq B$だから, $||H||\leqq 2B$ となることは明らかである. (ii) は容易にを示される. よって定理は示された.

口系 5. 条件 (I) を仮定すると, 次式が成立して,$i\in S,$

$E\subset S,$$f\in \mathcal{F}$に関して一様

収束する.

(14)

$H(i, E)= \lim_{Narrow\infty}\frac{1}{N+1}\sum_{n=0}^{N}\sum_{k=0}^{n}\{P^{k}(i, E)-P^{*}(i, E)\}$

証明. 定理$P^{*}H=O$

(15)
定理

$4(\mathrm{i}\mathrm{i})$,の $H=I-P^{*}+PH$ を $n$ 回反復代入して $n$ について平均をとる.

上り, 任意の $i\in S,$ $E\subset S$ に対して次式を得る.
$H(i, E)= \frac{1}{N+1}\sum_{n=0}^{N}\sum_{k=0}^{n}(P^{k}-P^{*})(i, E)+\frac{1}{N+1}\sum_{n=1}^{N+1}(P^{n}-P^{*})H(i, E)$$4(\mathrm{i})$と (2) より,$|| \sum_{n=1}^{N+1}(P^{n}-P^{*})H||\leqq(2B)^{2}$とすると, (15) の最後の項は $i\in S,$ $E\subset S,$$f\in \mathcal{F}$である. (15) において $Narrow\infty$

に関して一様に 0 に収束する. よって (14) が成立する.

Arapostathis ({$\mathfrak{g}[1]$

収束が $i\in S,$ $E\subset S,$$\square$の Theorem A2$f\in \mathcal{F}$により, 系 5 は定理$4(\mathrm{i})$における $H_{\rho}(i, E)$ のに関して一様であることを示している.

4. Blackwell-最適定常政策の存在
この節では連続な係数をもつローラン展開を求め, さらに Blackwell-最適な定常政策の存在を示す.
$y_{-1}(f)=P^{*}(f)r(f),$ $y_{n}(f)=H(f)^{n+1}r(f)$は列ベクトノレとする.

$n=-1,0,1,$$\cdots$

定理 4 を使$|_{\sqrt}\mathrm{a}$$x=(x_{i})$(こ対して,

とおく. ただし $r(f)=(r(i, f(i));i\in S)$$||x||= \sup_{i\in S}|x_{i}|$に対して, $||y_{n}(f)||\leqq(2B)^{n+1}M$ が成り立つ.
, 次の定理は [13] と同様にして示される.

とすると, 任意の

154
定理 6. (Laurent 級数展開)$0<\rho\leqq\rho_{0},$$f\in \mathcal{F}$

条件 (I) を仮定する.

とすると,$0<\rho_{0}<1/(2B)$

に対して次式が成立する.

(16)$V_{\rho}(f)= \rho^{-1}y_{-1}(f)+\sum_{n=0}^{\infty}(-\rho)^{n}y_{n}(f)$.

条件 (II). (i) 任意の $i\in S$ に対して, $A(i)$ は完備可分距離空間 $A$ のコンパクト集合とする.

(ii) 任意の $i,j\in S$ [こ対して, $p(a)_{ij}$ と $r(i, a)$ (ま $a\in A(i)\}$ こつ 4 ‘て連続である.
条件 (I), (II) のもとでは Scheffe’ の定理により, 任意の $i\in S,$ $n=1,2,$$P(f)^{n}(i, E)$

は上で $E\subset S$ に関して一$\mathcal{F}$$\ldots$に対して連続である.

定理 7. 条件 (I), (II) を仮定する. このとき, 任意の $i\in S$ と $n=-1,0,1,$
して, $y_{n}(f)$ の第 -成分$i$$y_{n}(f)_{i}$は$\mathcal{F}$$i$$y_{-1}(f)_{i}$$\mathcal{F}$上で連続で,$f\in \mathcal{F}$

は減少列で

定常政策を
列

$\{f_{n_{k}}\}$$f_{n}\in \mathcal{F}$$\lim_{narrow\infty}\rho_{n}=0$とする.

がある. このような$f^{*}$を$\rho_{k}$$Y_{n}(f)=(y_{-1}(f), y_{0}(f),$ $\cdots,$ $y_{n}(f))$

で 0$\mathcal{F}$

とする.

$A,$

となる部分

$B\in N(S)$ について $A-B$ の各行$A[succeq] B$と表すことにする.

;

任意の g\in F について $Y_{n}(f)[succeq] Y_{n}(g)\}$ と定義する.

$g,$$f\in \mathcal{F}$$\cdots$$f_{n_{k}}\in \mathcal{F}$-割引最適 (定常) 政策の極限点とよぶ.

とならない最初の成分が正となるとき,と $n=-1,0,1,$

口とする. Blackwell[3] によって得られる \rho n-割引最適

はコンパクトだから, f*=lim7\rightarrow 。

$\mathcal{F}$に関して一は連続である. $y_{-1}(f)$ : の場合と同様にして,(14) より, $y_{0}(f)$ : は連続となる. 残りの証明は容易であるので省略する.
$\{\rho_{n}\}$に対上で連続である.

証明. (3) より, $n^{-1} \sum_{k=1}^{n-1}P(f)^{k}r(f)$ の第 -成分は様に $y_{-1}(f)$ : に収束する. 従って,$\ldots$$D_{n}=\{f\in$} こ対して, $r_{0}(g)=r(g),$ $n\neq 0$ のとき $r_{n}(g)=0$ (零ベク

トノレ), $y_{-2}(f)=0$ かつ$\psi_{n}(g, f)=r_{n}(g)+P(g)y_{n}(f)-y_{n-1}(f)-y_{n}(f)$と定義する.

$\Psi_{n}(g, f)_{i}$は $\Psi_{n}(g, f)=(\psi_{-1}(g,f\lambda\psi_{0}(g,f),\cdots,\psi_{n}(g,f))$ の第$i$行を表すものとする. 次の補助定理は (16) と定理 7 から容易に示される.

補助定理 8. 条件 (I), (II) を仮定する.
$f^{(n+1)}\in D_{n+1}$

定理 9.

$D_{n}\subset \mathcal{F}\subset D_{n-1}$が成り立っているとすれば,となる. ただし, $f^{(n+1)}$ は \rho k-割引最適政策の極限点とする.

条件 (I), (II) を仮定する.

Blackwell-最適定常政策が存在する.

\rho k-割引最適政策の極限点によって得られる

155
証明.

$n$

に関する帰納法によって, -害 IJ 引最適で $Y_{n}(f^{(n)})=Y_{n}(f^{*})$ を満たす $f^{(n)}\in D_{n}$$n$の存在をいえばよい. $n=0$ のとき, $f^{*}=f^{(0)}$ が帰納法の仮定を満たすことは容易に示される. (例えば [10] の Theorem 3 参照と仮定する.

$f^{(n)}\in D_{n}$$\ovalbox{\tt\small REJECT}$$A_{n}(i)=\{a\in A(i);a=g(i), \Psi_{n}(g, f^{(n)})_{i}=0, g\in \mathcal{F}\}$とおく. 制限された MDP $(S, A_{n}(i),$ $p,$ $r)$ において, $f^{(n+1)}$ が \rho k-割引最適政策の極限点であるとする.

$\mathcal{F}_{n}=\cross_{i\in S}A_{n}(i)$と表しておく.

ら, $Y_{n-1}(g)=Y_{n-1}(f^{(n)})$ を得る. 従って,$f^{(n+1)}\in D_{n+1}$$g\in \mathcal{F}_{n}$ならば $\Psi_{n}(g, f^{(n)})=0$ だか$D_{n}\subset \mathcal{F}_{n}\subset D_{n-1}$となる. 補助定理 8 上となることが解る. このこと (ま, $Y_{n+1}(f^{(n+1)})$ の値が$\{\rho_{k}\}$,$\text{り}$のとり方 [こ無関係に定まることも示している.
式 (1) が $\pi^{*}=f^{(n)}$ としてある行で等号によって成立していると仮定する. 補助定理

8 と同様 (こして, (1) は $n=n+1,$ $\pi^{*}=f^{(n+1)}$ として成立する. $Y_{n}(f^{(0)})=Y_{n}(f^{(n)})$ と仮定すると,$V_{\rho k}(f^{(0)})\geqq V_{\rho k}(f^{(n+1)})$だから $Y_{n+1}(f^{(0)})=Y_{n+1}(f^{(n+1)})$ となって帰納法が

示される.

口

References[1] Arapostathis, A., Borkar, V. S., Ferdenandez-Gaucherand, E., Ghosh, M. K. andMarcus, S. I. (1993). Discrete-time controlled Markov processes with average costcriterion: Asurvey, SIAM J. Control Optim .31, 282-344.
[2] Billingsley, P. (1968). Convergence of Probability Measures, John Wiley& Sons,

Inc.
[3] Blackwell, D. (1965). Discounted dynamic programming, Ann. Math.

Statist.

36 , 226-235.
[4] Chung, K. L. (1960). Markov Chains with Stationary hansition Probabilities,

Springer-Verlag, Berlin.
[5] Dekker, R. and Hordijk, A. (1988). Average, sensitive and Blackwell optimal

policies in denumerable Markov decision chains with unbounded rewards, Math.
Oper.

${\rm Res}$. $13$ ,783-809.

[6] Dekker, R. and Hordijk, A. (1992). Recurrence conditions for average and Black-well optimality in denumerable state Markov decision chains, Math. Oper.
17,271-289.

${\rm Res}$.

156[7] Dietz, H. M. and Nollau, V. (1983). Markov Decision Problems with Countable

State Spaces, Akademie-Verlag, Berlin.
[8] Doob, J. L. (1953). Stochastic Processes, John Wiley&Sons, Inc.

[9] Hordijk, A. (1974). Dynamic Programming and Potential Theory, Math. Centre$7\}act51$ (Mathematisch Centrum, Amsterdam).

[10] Kadota, Y. (1979). Countable state Markovian decision processes under the Doe-blin Conditions, Bull. Math. Statist. 19, 85-94.
[11] Kadota, Y. (1996). Simultaneous recurrent conditions on countable state Markov
chains, J. Infom. Optim. Sci. 17, 397-407.

[12] Mann, E. (1985). Optimality equations and sensitive optimality in bound-ed

Markov decision processes, Optimization 16, 767-781.
[13] Miller, B. L. and Veinott, A. F. Jr. (1969). Discrete dynamic programming withasmall interest rate, Ann. Math. Statist. 40, 366-370.

On discrete dynamic programming with sensitive
discount optimality criteria, Ann. Math. Statist. 40, 1635-1660.

[14] Veinott, A. F. Jr.

(1969).

[15] Yushkevich, A. A. (1994). Blackwell optimal policies in aMarkov decision process. $40,253-288$ .
with aBorel state space, $ZOR-Math.$ Meth. Oper.
${\rm Res}$