数理解析研究所講究録 1263 巻 2002 年 51-71

51
部分観測可能なマルコフ過程での多段決定問題について
中井

達 (T\={o}ru Nakai)

九州大学大学院経済学研究院(Faculty of Economics, Kyushu University)1

不完備情報のシステム

部分観測可能なマルコフ過程における多段決定問題を解析することを青える。 そのために、部分観測可能なマルコフ過程の学習プロセスとその性質を 3 節で考える。
そのために 2 節では尤度比順序を 2.1 節で定義し、尤度比順序を多変量の場合を含めて一般化した$\mathrm{M}\mathrm{T}\mathrm{P}_{2}(\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2})$の定義とその性質を 22 節で解析する。 3 節で{ま、部分

観測可能なマルコフ過程について考えるが、はじめに部分観測可能な\nabla ’ レコフ連鎖を[こ、 3.3
3.1 節で定義し、その学習のプロセスを 32 節でまとめる。 これらの性質をもと(generalized
節で部分観測可能なマルコフ過程を定義し、その性質を 2.2 節の$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$multivariate total positivity of order two) の性質を用 ゝて解析する。
$\mathrm{A}$

つぎに、 部分観測可能なマルコフ過程における多段決定問題を、 最適選択問題や取り替え問題などいろいろな問題に応用できるが、 ジョブ・サーチと確率的逐次割り当て問題で考える。 そのため、 4.1 節ではジョブ・サーチを、 42 節で{ま確率的逐
次割り当て問題を簡単に説明する。 最後の 5 節では、 部分観測可能なマノレコフ過程
におけるジョブ・サーチ (5.1 節) と確率的逐次割り当て問題 (5.2 節) を考える。

2$\mathrm{T}\mathrm{P}_{2}$($\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}1$

positivity of order 2)

部分観測可能なマルコフ連鎖やマルコフ過程の状態に関する情報は、 状態空間上だ [ニ 1 頃序の確率分布で表すことができる。 これらの情報、 すなわち確率分布のあを入れることを考えるが、 ここでは尤度比順序を考える。 この順序関係 {ま、 最適政
策と事前情報との関係など重要な性質を求めるときに必要となる。 その他の確率的順序関係については Stoyan [27], Ross [26] などに詳しく、 待ち行列・取り替え問題$\mathrm{A}\mathrm{a}$など、 多くの確率的な多段決定問題で応用されている。

2.1 節では、尤度比を用いた順序を考えるが、 この順序は一般的な確率順序など [こ比べ強い順序関係ではあるが、 ベイズ学習を解析する上で重要な順序関係で、 不完

備情報の多段決定問題を含め、多くの問題で扱われている。ベイズの定理 [こ基づ ‘た$\mathrm{A}$

学習プロセスでの、事前情報 (prior information) と事後情報 (posterior information)の関係についての基本的な性質については、 3.1 節で詳しく述べる。 2.2 節で{ま、 部
分観測可能なマルコフ過程での学習を考えるために、 2.1 節の確率的順序関係を一般化し、 さらにそのために必要な性質を求める。 さらに、情報過程を表す確率変数や ‘
状態空間を一般化するため、 多変量確率変数にも対応できるようにする。

52
2.1

尤度比順序

確率変数 $X,$$\mathrm{Y}$の確率密度関数を、 それぞれ $f_{X}(x),$とし、 $x\geq y$ であれば、とする。 このとき、 $X$ は より尤度比の意味で大きいと$f_{\mathrm{Y}}(x)$$f_{X}(y)f_{\mathrm{Y}}(x)\leq f_{X}(x)f_{\mathrm{Y}}(y)$$\mathrm{Y}$

いい $X[succeq] \mathrm{Y}$ と表す。 この順序は、 尤度比

この順序は、 2 っの確率変数 $X,$とと、 尤度比$\frac{f_{X}(x)}{f_{\mathrm{Y}}(x)}$$\mathrm{Y}$を用いたもので尤度比順序という。

$\frac{f_{X}(x)}{f_{\mathrm{Y}}(x)}$に対して、 $X$ が$\mathrm{Y}$より尤度比の意味で大きいこが $x$ に関する増加関数となってぃることは等しい。 この順序関係は、 2 つの確率変数 $X,$$\mathrm{Y}$が確率密度関数を持っ場合だけでなく、離散型の確率変数のときも定義でき、 一般的には次のように定義できる。
定義 1 任意の半開区間 $(s, t]_{\text{、}}(u, v](s\leq u, t\leq v)$ に対し(1)$\frac{\mathrm{P}\mathrm{r}(X\in(u,v])}{\mathrm{P}\mathrm{r}(\mathrm{Y}\in(u,v])}\geq\frac{\mathrm{P}\mathrm{r}(X\in(s,t])}{\mathrm{P}\mathrm{r}(\mathrm{Y}\in(s,t])}$また’ ま、$|\begin{array}{llll}\mathrm{P}\mathrm{r}(X \in(u,v]) \mathrm{P}\mathrm{r}(\mathrm{Y} \in(s,t])\mathrm{P}\mathrm{r}(X \in(u,v]) \mathrm{P}\mathrm{r}(\mathrm{Y} \in(s,t])\end{array}|\geq 0\text{と}$比の意味で大きいといい$X[succeq] \mathrm{Y}$す 6。 このとき、 $X$ は$\mathrm{Y}$

より尤度

と表す。

この尤度比順序は確率過程を解析するとき$\mathrm{T}\mathrm{P}_{2}$(total positivity of order 2) といゎ

れ、 いろいろな性質が解析されてぃる (Karlin [7], Karlin and Taylor [8] など)。 このとき、 定義 1 で定義した順序は半順序となる。 このとき、 尤度比順序が成り立っ

簡単な例として、 っぎのようなものがある。
例 1 正整数全体 $\{0, 1, 2, \cdots\}$ の上での確率分布\mu =(崗,$\mu_{1},$$\mu_{2},$$\cdots$) を考える。 このとき、 正整数上の確率分布全体の集合を $S$ とおくと、{\mu =(崗,$S=$$\mu_{1},$$\mu_{2},$$\cdots$) $| \mu_{s}\geq 0(s=0,1,2, \cdots),\sum_{s=0}^{\infty}\mu_{s}=1\}$となる。 $S$ に含まれる 2 っの確率分布$s,$$\mu,$$\nu$(2)に対し、 $\mu\succ\nu$ とは、 定義より、 任意の$s’(s\leq s’, s, s’=0,1,2, \cdots)$ に対して、 $\mu_{s’}\nu_{s}\geq\mu_{s}\nu_{s’}$$s,$ $s’$が成立し、少なくとも 1 っのが成り立っことである。任意の $s=0,1,2,$のとき、 $\mu=\nu$ である。とは、 $\mu=\nu$ または $\mu\succ\nu$ が成り立の組み合わせに対しに対し$\mu_{s}=\nu_{l}$$\mu_{s’}\nu_{s}>\mu_{s}\nu_{s’}$$\cdots$$\mu[succeq]\nu$

つときである。
例 2 マルコフ連鎖で、 取りうる状態全体の集合を正整数全体 $\{0, 1, 2, 3, \cdots\}$とし、これらの状態のあいだの推移確率行列を $P=(p_{ss’})_{s,s’=0,1,2,3},\cdots$ とする。 このとき、任意の $s,$ $s’$ に対して $(s\geq s’, s, s’=0,1,2, \cdots)_{\text{、}}$$|_{p_{\hat{s}}}^{p_{\overline{s}}}$:$p_{\hat{s}s}p_{\overline{s}s’},|\geq 0$

これも$\text{尤^{}\backslash }$が、$\hat{s}\leq\overline{s}$となる任意の$\hat{s},\overline{s}$p$s^{\prime p_{\overline{S}S}}\geq p_{\overline{s}d}p_{\hat{S}S}$|こ対して成り立っ

すなゎち、$(\hat{s}, \overline{s}=0,1,2, \cdots)_{\text{。}}$

Rk を用いた性質であるが、 このような性質を推移確率行列に仮定したマルコフ連鎖は、取り替え問題などで劣化のある場合にょく用いられる。 すなゎち、53$|\begin{array}{ll}p_{\overline{s}s} p_{\overline{s}s’}p_{\hat{s}s} p_{\hat{s}s}\end{array}|\geq 0$だから、 このマルコフ連鎖の状態のあいだの推移に関して、 ある種の方向性が出てくる。 言い換えれば、 このマルコフ連鎖の状態が正整数で表されていることから、 状態を表す数が大きければ大きいほど、 つぎの状態は、 その状態を表す数が大きくなる可能性が高くなり、 状態を表す数が小さければ小さいほど、 つぎの状態は、 その状態を表す数が小さくなる可能性が高くなるという性質である。

2.2

一般化した

$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$とその性質

まず始めに、 前節で定義した$\mathrm{T}\mathrm{P}_{2}$(total positivity of order two) と$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$(multi-variate total positivity of order two) の 2 つを改めて定義する。
を絶対連続な確率変数で、 確率密度関数 $f(x),$ $g(y)$ を持つとす
定義 2
とする。
る。 このとき、 $f(x)g(y)\geq f(y)g(x)$ $(x\geq y)$ が成り立つとき、$(\mathrm{T}\mathrm{P}_{2})X,$$\mathrm{Y}$$X\succ \mathrm{Y}$を絶対連続な 次多変量確率変数で、確率密度関数 $f(x),$ $g(y)$定義 3とを持つとする。 このとき、 $f(x\wedge y)g(x\vee y)\geq f(y)g(x)$ が成り立つとき、$\min(x_{n}, y_{n}))$ および $x \vee y=(\max(x_{1}, y_{1})$ ,する。 ただし、 $x \wedge y=(\min(x_{1}, y_{1}),$$\max(x_{n}, y_{n}))$ とする $(x=(x_{1}, \cdots, x_{n}), y=(y_{1}, \cdots, y_{n})\in R1)$$(\mathrm{M}\mathrm{T}\mathrm{P}_{2})X,$$\mathrm{Y}$$k$$X\succ \mathrm{Y}$$\cdots,$。

$\ldots,$

これらの定義は、 2 つの確率変数 $X,$

が絶対連続の場合の定義である。 一般の部分観測可能なマルコフ連鎖では、 必ずしもこれらの確率変数の絶対$\mathrm{Y}$または、 $X,$$\mathrm{Y}$

連続性を仮定しない場合もあり、状態についての情報が絶対連続でない場合もある。
を定義し、 その性質を考える。
まず、 $S$ を完備で可分な全順序の入った距離空間とし、 集合 $P(S)$ を空間 $S$ 上の

ここでは、$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$の概念を一般化した$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$

確率測度全体とすれば、$P(S)= \{\mu|\int_{S}\mu(ds)=1,$ $\mu(B)\geq 0(B\in B)\}$(3)となる。 ここで、 $B$ を距離空間 $S$ におけるボレル (Borel) 集合族とする。 ここでは、確率測度 $\mu(s)$ が絶対連続であることは仮定しない。 また、 これらの確率測度のあい

だに、 定義 5 によって順序を入れる。 いま、 距離空間 $S$ には、 全順序が入っている
ので、 $S$ のボレル集合のあいだに、 つぎのような順序を導入する。
定義 4 距離空間 $S$ に含まれる 2 つのボレル集合を $A$ と $B$ とする。 $A\prec B$ とは、任意の $a\in A$ と $b\in B$ に対して、 $a\leq b$ が成り立つことである。
を $P(S)$ に含まれる 2 つの確率測度とする。 このとき、 2 つの互いに素と定義 5
なボレノレ集合 $A$ と $B$ に対して $(A, B\in B)_{\text{、}}A\prec B$ のとき $\mu(A)\nu(B)\leq\mu(B)\nu(A)$ が成り立ち、 少なくとも 1 つの $A$ と $B$ の組み合わせに対して $\mu(B)\nu(A)>\mu(A)\nu(B)$が成り立てば、 $\mu\succ\nu$ とする。 任意の $A\in B$ に対して、 確率 1 で $\mu(A)=\nu(A)$ であとする。
れば、 $\mu=\nu$ とする。 また、 $\mu=\nu$ または、 $\mu\succ\nu$ , のとき、
$\mu$

$\nu$

$\mu[succeq]\nu$54
定義 5 において、確率測度 と が絶対連続で、確率密度 $\mu(s)$ および $\nu(s)$ を持て
ば、 定義 5 は、 $\mu(t)\nu(s)\geq\mu(s)\nu(t)$ と同値となりの定義 (定2)義と等しい。 また、 2.1 節の尤度比順序と同じょうに、 定義 5 にょる順序が半順
$\nu$

$\mu$

$(s, t\in S, s<t)_{\text{、}}\mathrm{T}\mathrm{P}_{2}$序となる。 つぎに、 $P(S)$ で定義された関数 $u(\mu)$ が、
と

$\mu$

$\nu$

$\mu[succeq]\nu(\nu[succeq]\mu)$に対して、 $u(\mu)\geq u(\nu)(u(\mu)\leq u(\nu))$ のとき、 この関数を$\mu$となる任意のに関する非減少関数 (非増加関数) という。 このとき、 っぎの性質が成り立っ。

補題 1

$\mu$

と

$\nu$

$(S\cross S, B\cross B)$

を $P(S)$ に含まれる 2 っの確率測度で、 $\mu[succeq]\nu$ とする。 このとき、での確率測度$\delta$で次の性質を満たすものが存在する。すなゎち、任意の $A\in B$ に対して $\delta(A\cross S)=\mu(A)$であり、任意の $B\in B$ に対して $\delta(S\cross B)=\nu(B)$である。 また、 $\delta(\{(s, t)|(s, t)\in S\cross S, s\geq t\})=1$ である。
$\text{定理}1$$h$:\mu &\mbox{\boldmath $\nu$}$\text{を_{、}}P(S)$に含まれる 2 っの確率測度で、$\mu[succeq]\nu$とする。 いま、 関数

を、有界で -可測かっ非減少関数とすれば、 $\int_{S}h(s)d\mu(s)\geq\int_{\mathrm{S}}h(s)d\nu(s)$$Sarrow R_{+}$

$B$

である。

つぎに、距離空間 $S$ の直積空間$S^{n}=.

\prod_{1=1}^{n}S$と、直積ボレル集合族

える。 ただし、 $S^{1}=S$ およひ、 $B^{1}=B$ とする。っぎに、$\mu_{n}$$B^{n}=.

\prod_{1=1}^{n}B$

を考

(

, Bっ

を直積測度空$\mathrm{F}\ovalbox{\tt\small REJECT}$$S^{\iota}’$での確率測度とし、 $P(S^{||}.)$ を $(S^{n}, B^{n})$ での確率測度の集合とすれば、(4)$P(S^{n})$ $= \{\mu_{n}|\int_{S^{n}}\mu_{n}(ds^{n})=1,$ $\mu_{n}(B^{n})\geq 0,$ $(B^{n}\in B^{n})\}$

.

となる。

はじめに直積ボレル集合族
入する。
定義 6
$1,$

に含まれる直積ボレル集合のあいだに、 順序を導に含まれる 2 っの集合 $A^{n}= \prod_{1=1}^{n}.A$ : と $B^{n}= \prod_{1=1}^{n}.B$: で、 $A:,$ $B:\subset S,$ $i=$とする。 このとき、 $A^{n}\prec B^{n}$ とは、
であり
が任意の

$S^{n}$$\cdots,$ $n$$i=1,$$B^{n}$$A_{:}\cap B_{:}=\emptyset$$\cdots,$ $n$$A_{:}\prec B_{:}$

に対して成り立っときとする。

つぎに、 直積ボレル集合族に含まれる直積ボレル集合のあいだの演算として、
2 つの演算を定義する。 まず、に含まれる 2 っの集合
: と$B^{n}=\Pi_{1=1}^{n}.B$ を考える。 このとき、 ある$i=1,$
に対して、
:
であれば、
かっ
とする。
っぎに、
これらの
と
っの集合
2
:
で、
$\vee$と$\wedge$$B^{n}$の$S^{n}$$A^{n}=\Pi_{=1}^{n}.\cdot A$$\cdots,$ $n$$A_{i}\vee B_{i}=B_{\dot{l}}$$A_{:}\prec B_{i}$$A_{:}\wedge B_{\dot{l}}=A$$A^{n}$$B^{n}$

であり、 任意の $i=1,$
に対して
となる
と
に対
して、 演算 垢を、 $A^{n}\vee B^{n}=\Pi_{\dot{l}=1}^{n}A:\vee B_{:},$ $A^{n}\wedge B^{n}=\Pi_{\dot{l}=1}^{n}A:\wedge B_{:}$ と定義する。 このとき、
はっぎのように定義できる。

$A:,$ $B:\subset S$$\cdots,$ $n$$A_{:}\cap B_{\dot{l}}=\emptyset$$A^{n}$$B^{n}$$\wedge$$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$

定義 7$(\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2})\mu_{n}$とル集合 $A^{n}= \prod_{i=1}^{n}A_{i}$ と$B^{n},$$\nu_{n}$を $(S^{n}, B^{n})$ 上の 2 っの確率測度とする。 互いに素なボレ$B^{n}= \prod_{\dot{\iota}=1}^{n}B_{\dot{l}}$$A:,$ $B:\subset S,$ $A:\cap B_{:}=\emptyset$

で、 任意の $i=1,$$\cdots,$ $n$

に対して$A^{n},$ $B^{n}\in$であれば、$\mu_{n}(A^{n}\vee B^{n})\nu_{n}(A^{n}\wedge B^{n})-\mu_{n}(A^{n})\nu_{n}(B^{n})\geq 0$

,

(5)

55
が成り立ち、少なくとも 1 つの$B^{n})>\mu_{n}(A^{n})\nu_{n}(B^{n})$$\mu_{n}\succ\nu_{n}$と$B^{n}$の組み合わせに対して、とする。 任意の $A^{n}\in B^{n}$ (こ対して、$\mu_{n}(A^{n}\vee B^{n})\nu_{n}(A^{n}\wedge$のとき、 $\mu_{n}\succ\nu_{n}$が確率 1 で成り立つとき、 $\mu_{n}=\nu_{n}$ とする。 また、 $\mu_{n}=\nu_{n}$$\mu_{n}(A^{n})=\nu_{n}(A^{n})$また{ま$A^{n}$のときを、 \mu n\succeq \mbox{\boldmath $\nu$}。とする。

ここで、 $(S^{n}, B^{n})$ での確率測度のあいだに、 (5) 式によって、 順序を入れると半$|\mathrm{I}\ovalbox{\tt\small REJECT}$が絶対連続で確率密度関数を持てば、定義 3序となる。 また、確率変数とう。
と等しく、 この点から定義 7 で定義した順序を一般化した力\leq 絶対つの基本的な性質を持つ (補題 2 と 3)。 また、確率変数の$X_{s}$$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$$\mathrm{A}\mathrm{a}$$\mathrm{M}\mathrm{T}\mathrm{P}_{2}(\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2})$この$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$は2$X_{s}$

であれば、 FKG 不等式として知られて る性質力
連続で確率密度関数を持ち導かれることが知られている (Fortuin, Kasteleyn and Ginibre[5], Preston[24]etc)。
を仮定すれば、 同様の性質が成り立ち、 その 1 つの場合力 定
同じように、$\grave{\grave{1}}$$\mathrm{A}\mathrm{a}$$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$$\backslash \backslash \backslash$$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$

理 2 で示される。

補題 2$\mu_{n}$と$\nu_{n}$を、 $P(S^{n})$に含まれる確率測度で、$\mu_{n}[succeq]\nu_{n}\text{と}$し、 $\mu_{n-1},$

を、 $\mu_{n-1}(A^{n-1})=\mu_{n}(A^{n-1}\cross S)$ かつ $\nu_{n-1}(B^{h-1})=\nu_{n}(A^{n-1}\cross S)$と$\nu_{n}$の周辺確率測度とする ( $A^{n-1}\cross S,$ $B^{n-1}\cross S\in S^{n-1}$$\cross$$t,$ $s,$とする$\mu_{n}$S=S9。 このとき$\mu_{n-1}(A^{n-1}\vee B^{n-1})\nu_{n-1}(A^{n-1}\wedge B^{n-1})-\mu_{n-1}(A^{n-1})\nu_{n-1}(B^{n-1})\geq 0$

証明$\nu_{n-1}$となる。

最初に、 直積空間 $S\cross S$ を、 $D=\{(s, t)|s<t, s, t\in S\},$ $E=\{(s, t)|s=$$t\in S\}$と $F=\{(s, t)|s>t, s, t\in S\}$ の 3 つ [こ分害#する。

$\mu_{n-1}(A^{n-1})\nu_{n-1}(B^{n-1})=\int_{\mathrm{S}\mathrm{x}\mathrm{S}}\mu_{n}(A^{n-1}, ds)\nu_{n}(B^{n-1}, dt)$$=$$\int_{D}\{\mu_{n}(A^{n-1}, ds)\nu_{n}(B^{n-1}, dt)+\mu_{n}(A^{n-1}, dt)\nu_{n}(B^{n-1}, ds)\}$$+ \int_{E}\mu_{n}(A^{n-1}., ds)\nu_{n}(B^{n-1}, dt)$および$\mu_{n-1}(A^{n-1}\vee B^{n-1})\nu_{n-1}(A^{n-1}\wedge B^{n-1})$$=$$\int_{D}\{\mu_{n}(A^{n-1}\vee B^{n-1}, ds)\nu_{n}(A^{n-1}\wedge B^{n-1}, dt)$$+\mu_{n}(A^{n-1}\vee B^{n-1}, dt)\nu_{n}(A^{n-1}\wedge B^{n-1}, ds)\}$$+ \int_{E}\mu_{n}(A^{n-1}\vee B^{n-1}, ds)\nu_{n}(A^{n-1}\wedge B^{n-1}, dt)$

より、 2 つの領域 $D$ と $E$ での値を比較することで、 この補題力\leq 求まる。
$(A^{n-1}\wedge B^{n-1}, t)\in B^{n}$ だ力 1 ら$(s, t)\in E$ のとき、 $s=t$ および $(A^{n-1}\vee B^{n-1}, s),$の定$\text{義}$$E$$\text{、}$と (5) 式より $\mu_{n}(A^{n-1}\vee B^{n-1}, s)\nu_{n}(A^{n-1}\wedge B^{n-1}, t)\geq\mu_{n}(A^{n-1}, s)\nu_{n}(B^{n-1}, t)$が簡単に導ける。
$S\cross T\subset D=\{(s, t)|s<t, s, t\in S\}$ のとき、$\mu_{n}(A^{n-1}\vee B^{n-1}, S)\nu_{n}(A^{n-1}\wedge B^{n-1}, T)$$+$$\mu_{n}(A^{n-1}\vee B^{n-1}, T)\nu_{n}(A^{n-1}\wedge B^{n-1}, S)$$\geq\mu_{n}(A^{n-1}, S)\nu_{n}(B^{n-1}, T)+\mu_{n}(A^{n-1}, T)\nu_{n}(B^{n-1}, S)$

(6)

56
を求める。 まず、 $S\cross T\subset D$ より、 仮定から$\mu_{n}(A^{n-1}\vee B^{n-1}, T)\nu_{n}(A^{n-1}\wedge B^{n-1}, S)$$\geq$$\mu_{n}(A^{n-1}, S)\nu_{n}(B^{n-1}, T)$,$\mu_{n}(A^{n-1}\vee B^{n-1}, T)\nu_{n}(A^{n-1}\wedge B^{n-1}, T)$$\geq$$\mu_{n}(A^{n-1},T)\nu_{n}(B^{n-1}, T)$.

$\mu_{n}(A^{n-1}\vee B^{n-1}, S)\nu_{n}(A^{n-1}\wedge B^{n-1}, S)$$\geq$$\mu_{n}(A^{n-1}, S)\nu_{n}(B^{n-1}, S)$$\mu_{n}(A^{n-1}\vee B^{n-1},T)\nu_{n}(A^{n-1}\wedge B^{n-1}, S)$$\geq$$\mu_{n}(A^{n-1}, T)\nu_{n}(B^{n-1}, S)$となる。 一方 ‘から$\mu_{n}(A^{n-1}\vee B^{n-1}, S)\nu_{n}(A^{n-1}\wedge B^{n-1},T)\mu_{n}(A^{n-1}\vee B^{n-1}, T)\nu_{n}(A^{n-1}\wedge B^{n-1}, S)$$\geq\mu_{n}(A^{n-1}, S)\nu_{n}(B^{n-1},T)\mu_{n}(A^{n-1}, T)\nu_{n}(B^{n-1}, S)$となり、 Preston[24] の補題 2 より (6) 式が導かれる。 口
補題 3$\mu_{n}$と$\nu_{n}$を、 $P(S^{n})$ に含まれる確率測度で、$\mu_{n}(A^{n})$({($s^{\mathrm{n}}$とする。 このとき、での確率測度 で、 任意のに対して $\delta(A^{n}\cross S^{n})=$$B^{n}\inB^{n}$
およひ、 任意のに対して $\delta(S^{n}\cross B^{n})=\nu_{n}(B^{n})$ であり、 がっ$(S^{n}\cross S^{n}, B^{n}\cross B^{n})$$\delta$$\mu_{n}[succeq]\nu_{n}$, tn)|(sn 劃 7)

証明

$A^{n}\in B^{n}$$\delta$$\in S^{n}\cross S^{n},$ $s^{n}[succeq] t^{n}\}$) $=1$ となるものが存在する。

に関する帰納法を用いる。 これらの性質が $n-1$ より小さい値に対して成り立つとする。 いま、ととを、の周辺確率測度とする。 補題 2$n$$\mu_{n-1}$$\nu_{n-1}$$\mu_{n}$$\nu_{n}$と帰納法の仮定より次のことが成り立っ。 $(S^{n-1}, B^{n-1})$ 上の確率測度$\mu_{n-1},$ $\nu_{n-1}$に対して、$\tilde{\delta}_{n-1}(A^{n-1}\cross S^{n-1})$$=$$\mu_{n-1}(A^{n-1})$$A^{n-1}\in B^{n-1}$$\tilde{\delta}_{n-1}(S^{n-1}\cross B^{n-1})$$=$$\nu_{n-1}(A^{n-1})$$B^{n-1}\in B^{\mathrm{n}-1}$(7),$\tilde{\delta}_{n-1}(\{(s^{n-1}, t^{\mathrm{n}-1})|(s^{n-1}, t^{n-1})\in S^{n-1}\cross S^{n-1}, s^{n-1}\succ t^{n-1}\})=1$となる $(S^{n-1}\cross S^{n-1}, ?^{-\sim}\cross?^{-1})$ 上の確率測度
ここで、$\Pi_{\dot{\iota}=1}^{n-1}B$$B^{n-1}$: かつの

2 つの部分集合$A^{n-1}$と$\tilde{\delta}_{n-1}$$B^{n-1}$

(8)

.

(9)

が存在する。

で、 $A^{n-1}=\Pi_{1=1}^{n-1}.A:,$ $B^{n-1}=$. $(i=1, \cdots, n-1)$ とする。 このとき、 $\mu_{n-1}(A^{n-1})\neq 0$ が$A_{:}\prec B_{1}$

つ $\mu_{n-1}(B^{n-1})\neq 0$ならば、 任意の $A,$ $B\in B$ に対して$\hat{\mu}_{A^{n-1}}$$=$$\frac{\mu_{n}(A^{n-1}\cross A)}{\mu_{n-1}(A^{n-1})}$

,

(10)

$\hat{\nu}_{B^{n-1}}$$=$$\frac{\nu_{n}(B^{n-1}\cross B)}{\nu_{n-1}(B^{n-1})}$

,

(11)

$\mu_{n}(A^{n-1}\cross A)$$=$$\hat{\mu}_{A^{n-1}}(A)\mu_{n-1}(A^{n-1})$

,

(12)

$\nu_{n}(B^{n-1}\cross B)$$=$$\hat{\nu}_{B^{n-1}}(B)\nu_{n-1}(B^{n-1})$

,

(13)

とおけば、

57
となる。 ここで、
つぎに、$\hat{\mu}_{A^{n-1}’}\hat{\nu}_{B^{n-1}}$$\hat{\mu}_{A^{n-1}}[succeq]\hat{\nu}_{B^{n-1}}$

は $(S^{1}, B^{1})=(S, B)$ 上の確率測度となる。

すなわち、 $A\prec B$ となる任意の $A,$ $B\in B$ に対して

(14)$\hat{\mu}_{A^{n-1}}(A)\hat{\nu}_{B^{n-1}}(B)-\hat{\mu}_{A^{n-1}}(B)\hat{\nu}_{B^{n-1}}(A)\leq 0$となることを示す。 (10) 式と (11) 式を (14) 式に代入し、 整理すれば$\mu_{n}(A^{n-1}\cross A)\nu_{n}(B^{n-1}\cross B)-\mu_{n}(A^{n-1}\cross B)\nu_{n}(B^{n-1}\cross A)\leq 0$となる。 一方、 $A\prec B,$ $(A^{n-1}\cross B)\vee(B^{n-1}\cross A)=A^{n-1}\cross A$ であり $(A^{n-1}\cross B)\wedge$より$(B^{n-1}\cross A)=B^{n-1}\cross B$ である。 さらに、$\hat{\mu}_{n}[succeq]\hat{\nu}_{n}$$\mu_{n}(A^{n-1}\cross A)\nu_{n}(B^{n-1}\cross B)-\mu_{n}(A^{n-1}\cross B)\nu_{n}(B^{n-1}\cross A)\leq 0$となる。 したがって、 補題 1 より、$\hat{\delta}_{A^{n-1},B^{n-1}}(A\cross S)$$=$$\hat{\mu}_{A^{n-1}}(A)$$A\in B$$\hat{\delta}_{A^{n-1},B^{n-1}}(S\cross B)$$=$$\hat{\nu}_{B^{n-1}}(B)$$B\in B$

(15)
(16)

,

$\hat{\delta}_{A^{n-1},B^{n-1}}(\{(s, t)|(s, t)\in S\cross S, s\geq t\})=1$となる $(S\cross S, B\cross B)$ 上の確率測度$\hat{\delta}A^{n-1},B^{n-1}$

ここで、 $(S^{n}\cross S^{n}, B^{n}\cross B^{n})$ 上の確率測度が存在する。

を $\delta_{n}((A^{n-1}, A)\cross(B^{n-1}, B))=$
が補題を満足する。 (7) 式$\tilde{\delta}_{n-1}(A^{n-1}\cross B^{n-1})\hat{\delta}(A^{n-1},B^{n-1}A\cross B)$ とすれば、 この$\delta_{n}$$\delta_{n}$より $\tilde{\delta}_{n-1}(A^{n-1}\cross S^{n-1})=\mu_{n-1}(A^{n-1})$ , であり、 (15) 式より $\hat{\delta}(A^{\mathfrak{n}-1},B^{n-1}A\cross S)=$だから、 $\delta_{n}(A^{n}\cross S^{n})=\delta_{n}((A^{n-1}, A)\cross(S^{n-1}, S))=\mu_{n}(A^{n})$ となる。の意味で順序がつけば、 それらの周辺のあいだにと
補題 2 では、に対しても同様の順序関係が保たれることを示している。 また、 補
密度 $\mu_{n-1},$$\square$$\hat{\mu}A^{n-1}(A)$$\mu_{n}$$\nu_{n}$$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$$\nu_{n-1}$

では、 非減少関数の期待値に関して、順序関係を保存するという性質が成り立った (補題 4 など) 。この性

題 3 は補題 1 を一般化したものである。 また、$\mathrm{T}\mathrm{P}_{2}$や$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$

質は、 期待値を最大化する多段決定問題を解析する上で基本的な性質であり、 特にに部分観測可能な確率過程で考える場合にも必要となる。 ここで定義した$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$

ついても、 同様の性質が成り立つ。
いま、 k-変数関数: $R_{+}^{k}arrow R+$ が、 $x\prec y$ となる $x,$ $y$ [こ対して、 $\varphi(X)\leq\varphi(y)$(非増加) 関数というこ。 こ$(\varphi(X)\geq\varphi(y))$ のとき、 この関数は $x$ に関する非減少$\varphi$

こで、 $x$ , y\in Rk+{こ対して、 $x\prec y$ と (ま、 任意の $i=1,2,$$\cdots,$$k$[こ対して、 $x_{i}\leq y$: が成り立つことをいう。 ただし、 $x=(x_{1}, \cdots, x_{k})$ および $y=(y_{1}, \cdots, y_{k})$ とする。
定理 2
$h$

$\mu n$と$\nu_{n}$を、 $P(S^{n})$ に含まれる確率測度で、: Sn\rightarrow R。が有界で可測な非減少関数ならば、$\mu n[succeq]\nu_{n}$とする。 また、 関数$\int_{S^{n}}h(s)d\mu_{n}(s)\geq\int_{\mathrm{S}^{n}}h(s)d\nu_{n}(s)$

である。
証明

$E^{n}=\{(s, t)|(s, t)\in S^{n}\cross S^{n}, s[succeq] t\}$$\int_{\mathrm{S}^{n}}h(s)d\mu_{n}(s)-\int_{\mathrm{S}^{n}}h(t)d\nu_{n}(t)$とお$\#\mathrm{e}$

IJ、

$=$

$\int\int_{\mathrm{S}^{n}\mathrm{x}S^{n}}(h(s)-h(t))d\delta_{n}(s, t)$$=$$\int\int_{E^{n}}(h(s)-h(t))d\delta_{n}(s, t)\geq 0$58となる。 ここで、 $(s, t)CE^{n}$ のとき、 $h(s)$ の定義がら用いた。 口3$h(s)-h(t)\ovalbox{\tt\small REJECT} 0$となることを

不完備情報のシステム
まず、 3.1 節では部分観測可能なマルコフ連鎖を考える。 たとえば、経済の状態を良い状態から悪い状態まで幾っがに分け、 現在の状態がそれらのどれがを直接には知ることができない。 しかし、 おがれてぃる経済状態としてどのような状態が可能かについて、 何らかの情報を持ってぃる場合である。 っぎに、 このような部分観測可能なマルコフ連鎖の状態につぃて、 事前情報と情報過程がら得られる情報に対して、 学習プロセスとしてベイズ学習を考え、 いくっがの条件のもとで、この学習プ
ロセスの性質を考える。 第 33 節で部分観測可能なマルコフ過程につぃて考える。

3.1

部分観測可能なマルコフ連鎖

有限個または可算無限個の状態のマルコフ連鎖
このマルコフ連鎖の状態は番号づけられ、正整数の集合

を考える。
で表す。
にあるという。 このマルコフ連鎖で、 その$\{\mathrm{Y}_{n}|n=0,1,2,3, \cdots\}$のとき、 このプロセスは時点

$n$

で状態

$s$

$\{0, 1, 2, \cdots\}$$\mathrm{Y}_{n}=s$

状態を直接に知ることはできないが、 ある情報過程を通して、情報が得られるとき、これを部分観測可能なマルコフ連鎖という。 このような部分観測可能なマルコフ連
鎖の基本的な性質は、 Nakai[13] などで解析され、 Nakai[15] などでは部分観測可能なマルコフ連鎖のもとでの確率的な多段決定問題が扱ゎれてぃる。
いま、 このマルコフ連鎖の状態空間を簡単のため有限集合とし、 $\{0, 1, 2, \cdots, S\}$ とおく。 $P=(p_{ss’})_{s,s’=0,1,2,\cdots,S}$ を推移確率行列とする。っぎに、

このマルコフ連鎖の状態に依存する確率変数を考え、 この確率変数を観測することにょり、 状態につぃての情報を得る。 このプロセスを情報過程という。 いま、 マルコフ連鎖の状態が のとき、 この状態で定まる非負確率変数をとおけば、 この確率変数の分布関数を$s$$X_{s}$$\mathrm{P}\mathrm{r}(X_{s}\leq x|\mathrm{Y}_{n}=s)=F_{s}(x)(x\in R, s\in\{0,1,2, \cdots, S\}, n\in\{0,1,2, \cdot..\})$

、確率密度
状態空間
上の確率分布 で表され、 それら確率分布全体の集合は、 (2) 式の $S$ となる。 さらに、 この集合に例 1 で考えた順序を考える。
関数を $f_{s}(x)$ とする。 また、 このマルコフ連鎖の状態につぃての情報は、
$\mu$

3.2

ベイズ学習

前節の部分観測可能なマルコフ連鎖の状態に関して、 ベイズの定理を用いて学習を行う。 このマルコフ連鎖の状態につぃての事前情報は、 状態空間上の確率分
布 で表せる。 このマルコフ連鎖の状態につぃての事前情報がのとき、 標本値
$\mu$

$\mu$

が得られたとする。 このとき、 状態に依存する確率変数がらのと事前分布 に対し事後分布が存在し、 この事後情報をとする。 こ$x(\in R_{+}=(0, \infty))$

標本値

$x$

$\mu$

$\overline{\mu}(x)$こでは、 部分観測可能なマルコフ連鎖の状態につぃての事前情報が$\mu$のとき、 ます59
始めに状態の推移が起こり、 そのあとで、 推移した状態に依存した確率変数を観測して標本値を得て、 そこで状態について学習を行うことにする。 もちろん、 順序を逆に考えることもできるが、 その場合もここでの議論と同様となる。 このとき、 状態についての事前情報と事後情報の関係について、 基本的な性質力\leq 成り立つ。
のとき、 このマルコフ連鎖は推移確率行列 $P$ にしたがって状態力
事前情報が$>\backslash \backslash$$\mu$

推移するから、 状態についての情報は$\overline{\mu}_{s’}=\sum_{s=0}^{S}\mu_{s}p_{ss’}$

状態に$’\supset$となる。 ただし、$\overline{\mu}=(\overline{\mu}_{0}, \overline{\mu}_{1}, \overline{\mu}_{2}, \cdots, \overline{\mu}_{S})$である。 つぎに、 状態に依存する確率変数から標本値

いての情報をベイズの定理を用いてを考えるた\sim -b.\leftar ow \leftar ow }\brev \acute \che k ‘C ‘\acute \sup et - \mu g(‘ x\emptyset )s’2

$x$

を観

$\overline{\mu}(x)=(\overline{\mu}(x)_{0},\overline{\mu}(x)_{1},$ $\cdots,$

し、$\Re^{1}\mathrm{I}$と$\overline{\mu}(x)s)$

このような、ベイズ学習の性質学習する。

$= \frac{\overline{\mu}_{s’}f_{s’}(x)}{\sum s0\overline{\mu}_{s}f(X),\text{の}f\overline{\overline{fi}}\text{定を^{}\frac{-s}{\Rightarrow}}\alpha^{n}\#\mathrm{e}s}\vee\supset$$\text{て^{}\backslash }\backslash \text{ある_{。}}\backslash \mathrm{R}^{\backslash }\text{態_{}\backslash \text{、}}|_{\mathrm{c}}^{}$

関する事

、

$arrow \mathrm{R}^{1}\mathrm{J}$

情報と事後情報の関係を求める。

仮定 1 確率変数 $\{X_{s}\}_{s=0,1,2,\cdots,S}$ に対し、 $s\leq s’(s, s’=0,1,2, \cdots, S)$ ならとする。

$X_{s’}[succeq] X_{s}$仮. 定 2 推移確率行列 $P$ に例 2 の性質を仮定する。
は、状
仮定 1 から、部分観測可能なマルコフ連鎖の状態に依存する確率変数
態を表す値 が大きくなればなるほど、確率変数の取る値は小さくなりがちである。
仮定 2 から、状態を表す値 が大きくなればなるほど、大きな値をもつ状態へ推移しやすく、 状態を表す値 が小さくなれぱなるほど、 小さな値をもつ状態へ推移しやすい。 また、 {0, 1} の 2 つの状態をとるマルコフ連鎖では、仮定 2 は不等式 $p00\geq p_{10}$2[まと等しい。 この仮定は Ross [25], Monahan [12] などで用いられたもので、 仮定
この一般化である。
つぎに、 情報全体の集合 $S$ で定義された関数 $u(\mu)$ に対して、 関数 $u(\mu)$ 力瓢
の[こ対し $u(\mu)\geq u(\nu)(u(\mu)\leq u(\nu))$ のとき、 この関数となるに関する非減少関数 (非増加関数) という。 集合 $S$ で定義されたこのようことを$\{X_{s}\}$

$s$

$s$

$s$

$\mu[succeq]$$u(\cdot)$$\nu(\nu[succeq]\mu)$$\mu,$

$\nu$

$\mu$

な関数 $u(\mu)$ としては、 状態空間上の確率分布 に関する期待値などを考えれい。 これらの仮定のもとで、 事後情報の性質を求める。
$\mu$

定理 3 $x\leq y$ となる $x,$

$y$

}こ対し、

定理 4 $S$ に含まれる任意の
と
{こ対し、
含まれる
$\mu$

$\nu$

$\mu,$$\nu$$\mu[succeq]\nu$$\overline{\mu}(y)[succeq]\overline{\mu}(x)$

に対し、

ならば、

となる

$\mu[succeq]\nu$$(\mu\in S)_{\text{。}}$

ならば一$\overline{\mu}(x)[succeq]\overline{\nu}(x)$.よ$|\mathrm{h}$$[succeq]\overline{\nu}$となる。 また、 $S$ にとなる (x\in R)。

定理 3 から、 状態に関する事前情報が同じであれば、観測値の値が大きくなればなるほど、 状態に関する事後情報は尤度比順序の意味で良いものとなる。 また、 定
理 4 から、 同じ値を観測しても、 事前情報が尤度比順序の意味で良ければ、 事後情報もまた尤度比順序の意味で良くなる。
補題 4 $\{f_{s}(x)\}_{s=0,1,2,\cdots,S}$ を、 $S$ 個の絶対連続な確率変数とたす確率密度関数の列とする。 また、 $S$ に含まれる$\mu$の仮定 1 を満とし、に対して

$X_{1},$$\nu$$\cdots,$$X_{S}$$\mu[succeq]\nu$60$a_{s}=\mu_{s}-\nu_{S}$

とおく ( $s=0,1,2,$$\cdots$, S)。 このとき、 $g(x)= \sum_{s=0}^{s}a_{s}f_{s}(x)$ とすれば、任意の非減少関数 $h(x)$ [こ対して、 $\int_{0}^{\infty}h(x)g(x)dx\geq 0$ となる。
いま、 関数 $h(x)$ に対して、 $E_{\nu}[h(X)]= \int_{0}^{\infty}h(x)\sum_{s=0}^{s}\mu_{s}f_{s}(x)dx$ だから、より \not\in 意の非 a 少関数 $h(x)$ に対して、$\mu[succeq]\nu$

この補題

なら $1\mathrm{f}E_{\nu}[h(X)]\geq E_{\mu}[h(X)]$ とな

り、 この性質が部分観測可能なマルコフ連鎖での多段決定問題を解析する上で必要

となる。

3.3

部分観測可能なマルコフ過程

つぎに、 3.1 節の部分観測可能なマルコフ連鎖を、一般の部分観測可能なマルコフ過程に拡張し、 多変量確率変数がら情報を得る場合にも対応できるように考える。
このような問題としては、 最適選択問題などがあり (Nakai[16, 17]) 、部分観測可能なマルコフ連鎖における最適選択問題は Nakai[17] などで考察され、 この節の部分観測可能なマルコフ過程のモデルにつぃては、 Nakai $[20, 21]$ などで詳しく説明されているので、 ここでは主要な結果につぃて触れる。
を完備で可分な全順序の入った距離空間とし、 部分観測可能なマルコフ過程の状態空間とする。 この可測空間における全順序を、 で表す。 この状態空間 に対
$S$

$S$

$\leq$

し\mbox{\boldmath $\tau$}、 $B$ を可測空間 $S$ のボレル集合族とする。 さらに、 $P(\cdot|s)(s\in S)$ でこのマルコフ過程の推移法則を表し、 状態空間 $S$ がら $S$ への推移を表す。 すなゎち、任意の状
態 $s\in S$ に対して、
は上の確率測度であり、 任意の可測集合 $B\in B$ に対し$p(\cdot|s)$$S$て、 $P(B|s)= \int_{B}dp(t|s)$ とする。

次に、 このマルコフ過程の任意の状態 に対して、 それぞれ非負k-次の多変量確率変数が対応し、 それぞれの期待値は有限で、$s$$X_{s}$

この部分観測可能なマルコフ過程の状態についての観測過程とする。 いま、 これらの確率変数の確率分布を、任意$\mathcal{O}2s\in S$とボレノレ集合 $C\subset R_{+}^{k}=(0, \infty)^{k}$ に対して、 $\mathrm{P}\mathrm{r}(X_{s}\in C)=\int_{C}dF_{k}(oe|s)$ とする。 このとき、 3.1 節で考尺たような部分観測可能なマルコフ連鎖の\Re 態に関する

学習プロセスを、 このような部分観測可能なマルコフ過程で考える。
前節と同様に、 このマルコフ過程の状態につぃての情報は、 $S$ 上の確率測度にょって表され、 $P(S)$ を状態空間上の確率測度の集合とし、 (3) 式で定義する。

任意の観測値 $x=(x_{1}, \cdots, x_{k})(\in R_{+}^{k})$ と事前情報

ベイズの定理を用いて学習する。

$\mu$

さらに、

に対して、 事後情報は存在し、事前情報が のとき、 このマルコフ過程は推移法則にしたがって状態が推移し、 マルコフ過程の状態に関する情報となる。 すなゎち、任意の可測集合 $B\in B$ に対して、確率測度 は–\mu (B) $= \int_{S}P(B|s)d\mu(s)$ となる。
っぎに、情報過程から、 標本値 $x$ を観測し、 任意の $x\in R_{+}^{k}$ と $\mu\in P(S)$ に対して、 ベイズの定理を用いてとなる。
$\mu$$P(\cdot|\cdot)$$1\mathrm{h}\mathrm{o}\mathrm{e}\text{率}\backslash \mathrm{f}\mathrm{f}\mathrm{i}|\mathrm{J}\text{度}\overline{\mu}$$\overline{\mu}$$\overline{\mu(oe)}$

61
3.4

$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$のベイズ学習への応用

33 節で定義した部分観測可能なマルコフ過程と、その学習プロセスに対して、 2.2
節で定義した
まず始めに、$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$$R_{+}$の性質を応用して、 いくつかの仮定の下で考える。

を標本値の取る値の集合、 すなわち正数全体とし、ボレル集合族とする。 このとき、 $R_{+}^{1}=R_{+}$ およびを、 それぞれ$\mathcal{X}^{k}=\prod_{i=1}^{k}\mathcal{X}$$R_{+}$

および$\mathcal{X}$$\mathcal{X}^{1}=\mathcal{X}$とし、$\mathcal{X}$を $R_{+}$ の$R_{+}^{k}= \prod_{i=1}^{k}R_{+}$の直積空問および直積ボレル集$. \bigwedge_{\mathrm{D}}$

と

族とする。

上の確率測度とし、 この(.\mapsto を部分観測可能なマルコフ過程の情報過程とする。 このとき、 つぎの 2 つの仮定を考
ここで、 任意の状態 $s\in S$ に対して、$F_{k}$$(R_{+}^{k}, \mathcal{X}^{k})$える。
を考える $(X^{k},$仮定 3 互いに素なボレル集合 $X^{k}=\Pi_{i=1}^{k}X_{i}$ と$k)$ 。このとき、 任意の状態 $s,$ $t\in S$ に対$i=1,$$\mathrm{Y}^{k}\in$$\mathrm{Y}^{k}=\Pi_{i=1}^{k}\mathrm{Y}_{i}$$\mathcal{X}^{n},$$X_{i},$ $\mathrm{Y}_{i}\subset R_{+},$ $X_{i}\cap \mathrm{Y}_{i}=\emptyset,$$\cdots,$

して、

(17)

$F_{k}(X^{k}\vee \mathrm{Y}^{k}|s\vee t)F_{k}(X^{k}\wedge \mathrm{Y}^{k}|s\wedge t)\geq F_{k}(X^{k}|s)F_{k}(\mathrm{Y}^{k}|t)$である。

仮定 4 任意の状態 $s\in S$ に対して、 この状態からの推移法則を $P(\cdot|s)(s\in S)$ とする。 このとき、 任意の状態 と に対して $(s<t)_{\text{、}}A\prec B$ ならば
$s$

$t$

(18)

$P(A|t)P(B|s)\leq P(B|t)P(A|s)$である。
ここで、 これらの確率測度と推移法則が絶対連続で、 確率密度関数がそれぞれあれば、 (17) 式と (18) 式は、 $u<v$ であれば ( , v\in S)、 $f_{k}(x\wedge y|s\wedge$$t)f_{k}(x\vee y|s\vee t)\geq f_{k}(y|s)f_{k}(x|t)$ および、 $p(u|s)p(v|t)\geq p(v|s)p(u|t)$ と等しく、 ことなることを示している。 このとき、 これらの仮定のもとで、 事前情
れらは報と事後情報の関係が、 次の定理 5 と定理 6 で示される。 これらの性質は、 3.1 節で$u$$f_{k}(\cdot|\cdot),p(\cdot|\cdot)$$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$求めた性質の一般化となっている。 すなわち、 すべての確率変数が絶対連続で確率密度関数を持つ場合に Nakai [13, 15, 17] などで示されているが、 これらの性質についても同じように求められる (Nakai[20, 21])。
$\nu\in P(S)$ に対して、
定理 5 $S$ 上の 2 つの確率測度ならば、る。 さらに、 任意の $x\in R_{+}^{k}$ に対して、$\mu[succeq]\nu$$\mu,$$\mu[succeq]\nu$

ならば、$\overline{\mu(x)}[succeq]\overline{\nu(x)}$定理 6 任意の確率測度 $\mu\in P(S)$ に対して、 $x\succ y$ ならば、$\overline{\mu}[succeq]\overline{\nu}$

であ

である。

$\overline{\mu(x)}[succeq]\overline{\mu(y)}$である。

定理 5 より、 状態に関する事前情報が同じであれば、 観測値の値が大きくなればの意味で良いものとなる。 また、 定理
なるほど、 状態に関する事後情報は$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$

6 より、 たとえ同じ値を観測したとしても、 事前情報が事後情報も$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$の意味で良くなる。

$\mathrm{G}\mathrm{M}\mathrm{T}\mathrm{P}_{2}$の意味で良ければ、

62
注 1

確率変数が絶対連続で、確率密度を持っ場合には、事後情報となることが示される。すなわち、任意の $x,$
である (Nakai[17])。

$y$$\mu(x)$もまた$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$[こ対して、 $\mu(x\mathrm{V}y)(s\vee t)\mu(x\triangle y)(s\triangle$$t)\ovalbox{\tt\small REJECT}\mu(y)(s)\mu(x)(t)$定理 1 と定理 2 から、 っぎの系が導がれる。 この性質は、 部分観測可能なマルコフ過程での多段決定過程を解析する上で基本的なものである。
系 1$\mu_{k}$と$\nu_{k}$を、$(R_{+}^{k}, \mathcal{X}^{k})$での 2っの確率測度とする。いま、 $C^{k}= \prod_{1=1}^{k}.C_{1}$. と $D^{k}=$: を、 2 つの互いに素なボレル集合とし$\Pi_{i=1}^{k}D$$\emptyset,$$i=1,$$\cdots,$$(C^{k},$$D^{k}\in \mathcal{X}^{k},$ $C_{1}.,$$D_{\dot{*}}\subset R_{+},$ $C_{\dot{\iota}}\cap D:=$$k)_{\text{、}}\mu_{k}(C^{k}\vee D^{k})\nu_{k}(C^{k}\wedge D^{k})-\mu_{k}(C^{k})\nu_{k}(D^{k})\geq 0$

R+k\rightarrow R。が有界で可測な非減少関数ならば、とする。 もし、$h$:$\int_{R_{+}^{k}}h(x)d\mu_{k}(x)\geq\int_{R_{+}^{k}}h(x)d\nu_{k}(oe)$となる。
もし、 関数もまた$s$$\varphi(x)$が $x$ の非減少関数ならば、 仮定 3 と系 1 より、 $\Phi(s)=\mathrm{E}[\varphi(X_{s})]$の非減少関数だから、 定理 1 上り次の性質が導かれる。

系 2 $S$ 上の 2 っの確率測度

る任意の非減少関数$\varphi(\cdot)$$\mu,$$\nu\in P(S)$ に対して、 $\mu[succeq]\nu$ であれば、 $x$ に関すに対して、 $\mathrm{E}_{\mu}[\varphi(X)]=\int_{S}\{\int_{R_{+}^{k}}\varphi(x)f(dx\mapsto\}\mu(ds)\geq$$\int_{S}\{\int_{R_{+}^{k}}\varphi(oe)f(dx|s)\}\nu(ds)=\mathrm{E}_{\nu}[\varphi(X)]$となる。

これらの性質を用いて、 部分観測可能なマルコフ過程における多段決定過程の最適政策や、 最適政策にしたがって得られる総期待利得の性質などにつぃて、 同じょ
うに解析できる。

4

期待値最大化問題について

4.1

ジョブ・サーチ (Job Search)

ある人が仕事を探しているが、 現れる仕事の総数 la あらかじめ決められてぃて、
それらのいずれかの仕事にっくとする。 一方、仕事は一度に 1 っずっ現れ、 これらの仕事が現れる回数を期間と考える。 これらの仕事の大きさは、 独立で同一の分布にしたがう確率変数 $X$ で表され、 現れるごとに、 その仕事の大きさを知ることができる。 これらの確率変数 $X$ の共通の分布関数を F(x)、 密度関数を $f(x)$ とし、 期待値
は有界とする。 また、 いったん見送った仕事は選べない (このとき 「リコールはない」 という)。 また、 現れたすべての仕事を最後まで見送ったときには、仕事の大きさにかかわらず、 最後の仕事に就くものとし、 選択の余地はない。 このとき、 定められた期間内に仕事を 1 っ選んで、期待利得を最大にする。 これは、 ジョブ・サー
チの簡単な場合である。
いま、 計画期間が で、 直面してぃる仕事の大きさが のとき、 最適に振る舞って得られる期待利得を $v_{n}(x)$ とすれば、 最適性の原理よりっぎの最適方程式を満足$n$$\mu_{F}$

$n$

$x$

63
(19)

$v_{n}(x)= \max\{x,$ $\int_{0}^{\infty}v_{n-1}(y)dF(y)\}$ここで、 $T_{F}(z)= \int_{z}^{\infty}(x-z)f(x)dx$ とおけば、 この関数{まいを持つ (DeGroot [3], 中井 [18] など)。 この関数を利用して、$\text{く}$つ力>の基本的な性質$\{a_{n}\}$を $n$ の増加正数列

により帰納的に定義すれば (a0=\mu F)、 直面している仕のとき、 $x\geq a_{n}$ ならばこの仕事を選び、 そうでなければ見送ることで、 $a_{n}=a_{n-1}+T_{F}(a_{n-1})$

事の大きさが$x$となる。
が最適政策であり、 その政策にしたがったときに得られる総期待利得は
このように、 ジョブ・サーチの最適政策は、 ‘しきい値’ (threshold value) あるいは
$a_{n}$

reservation wage と呼ばれる値によって定まることが多 ‘。
つぎに、 計画期間が無限のときには、 新たな仕事の大きさを知るための探索費用を導入する。 このとき、 Lippman and McCa11[9] では、 ジョブ
c、 あるいは割引率の大きさが経済状態に依存し、 その経済状態がダイナミツクに変動する場合を次の$\mathrm{A}$$\beta$を推移確率行列とするマルコフ連鎖で、状態を $\{1, 2, 3, \cdots, S\}$ とし、 これらの状態が経済を表す。 このとき経済の状態力 でにしたがう確率変数で表されあれば、 提示されるジョブの大きさは分布関数
る。 $v_{n}(i, x)$ を経済の状態が で、 提示されたジョブの大きさが とするとき最適に振る舞って得られる総期待利得とすれば、 次の最適方程式を満たす。
ようにモデル化している。 いま、$\mathrm{P}=(P_{ij})$$\grave{\grave{\backslash }}$$i$$F_{i}(x)$

$x$

$i$

$v_{n+1}(i, x)=\mathrm{I}\mathrm{n}\mathrm{a}\mathrm{x}\{x,$$-c+ \beta\sum_{j=1}^{s}p_{ij}\int_{0}^{\infty}v_{n}(j, y)dF_{j}(y)\}$このとき、 (1) $F_{i}(x)$ は確率的に増加、 すなわち、 任意の$\ldots\geq F_{n}(x)$であり、 (2) 任意の

$k$

に対して、

$\sum_{j=k}^{K}p_{ij}$$x$に対して $F_{1}(x)\geq F_{2}(x)\geq$

は H こ関して非減少である、 と$\mathrm{A}\mathrm{a}$う 2 つの仮定のもとで解析している。 3 節のモデルはこれを一般化したものである。
このようなジョブ・サーチに関して、 Lippman and McCall による論文集 [11] や、
サーベイ論文 [10] などがある。 また、 このジョブ・サーチでは仕事の大きさを知ることが出来たが、 このような問題は、 いろいろな形で一般化でき、 そのようなものとして、 確率的逐次割り当て問題や最適選択問題 (Nakai[16, 19]) などがある。

4.2

確率的逐次割り当て問題.

確率的逐次割り当て問題は Derman, Lieberman and Ross[4] 以来、 Albright[l, 2]
Nakai[14, 15, 19] などの研究があり、 次のようなものである。
ある企業が持っている人材などを、 逐次に現れる仕事に割り当てる。 ここで、 人
材の総数とそれらの能力は既知とする。 仕事は一度に 1 つずつ現れ、 それらの大きさは確率変数で表され、 仕事が現れたときに、 その大きさを知る。 一般的には、 大
きい仕事には、 有能な人材を投入するのがよいと思われる。 このような問題を確率的逐次割り当て問題という。
いま、 大きさ の仕事に、 十分な (perfect) 能力を持った人材を投入すれば そのものが得られ、 不十分ならば そのものではなく、 投入量により変化し $px$ としよ
$x$

$x$

$x$

64
う。 この

が人材によって異なり、 $0\leq p\leq 1$ ならば、 この人材にょって仕事から得られる割合と考える。 このとき、 割り当てる人材を 人とし、 その能 ] は数値化さ
$p$

$;$

$n$

れ、 それらを$p_{1},p_{2},$ $\cdots,p_{n}$とする。 ここで、 一般性を失うことなく大きさの順に並べかえられ $p_{1}\geq p_{2}\geq\cdots\geq p_{n}$ と仮定する。

また、計画期間$n$と割り当てる人材の数が等しいとしても一般性を失ゎない。 もし割り当てる人材の数 $m$ が より大きければ、利得が $px$ だがら、大きい方がら 人の人材を割り当てることが最適であり、残りの $m-n$ 人の人材は割り当てられない。 また、割り当てる人材の数 $m$ が より小さければ、 $n-m$ 人の を $p_{m+1}=\cdots=p_{n}=0$として付け加えればよい。
このように、 個の仕事の大きさは、 独立がっ同一の分布にしたがう確率変数列で表され、 分布関数 $F(x)$ と確率密度関数 $f(x)$ を持ち、 その期待値は有界とする。 いったん割り当てた人材は、 ほかの仕事には割り当てられない。 このとき、 人の人材を 個の仕事に、 どのように割り当てれば、 総期待利得を最大にできるだろうか。 この問題では、とは独立な、 仕事の大きさを表す確率変数の分布関数のみで定まる ‘しきい値’ で最適政策などが定まる。
まず、 良く知られたっぎの性質 ある (Hardy, Littlewood and Polya [6])。
$n$

$n$

$n$

$p$

$n$

$\{X_{1}.\}:=1,2,\cdots,n$

$n$

$n$

$p_{1},p_{2},$ $\cdots,p_{n}$$\mathrm{B}.\mathrm{i}$

補題 5(Hardy の補題) $a_{1}\geq a_{2}\geq\cdots\geq a\text{、}\geq 0,$ $b_{1}\geq b_{Z}\geq\cdots\geq.b_{n}\geq 0$ のとき、を$n$次対称群とすれば、$\max_{\sigma\in s_{n}}\sum_{\dot{|}=1}^{n}$a:b\sigma 。)$S_{n}$. である。

$=. \sum_{1=1}^{n}a:b_{1}$

この補題から、 個の仕事の大きさを一度に知ることができれば、 1 番大きい仕事には 1 番大きな角を、 2 番目に大きい仕事には $n$ を、
番小さい仕事にはを割り当てればよい。 しかし、 ここで考えてぃる問題では 個の仕事が 1 っずっ現れ、リコールがな
さらに、 その大きさが確率変数で表される不確実な量であり、 現$n$$\ldots\text{、}$$1$$p_{n}$$n$$\mathrm{A}\mathrm{a}_{\text{。}}$

れるまでその大きさを知ることができない。 このことから、 この問題は Hardy の補
題の確率的一般化と考えられる。
計画期間が

$n$

で、 $n$ 個の仕事に$p_{1},$$\cdots,p_{n}$を割り当てるとき、$(p_{1}, \cdots,p_{n})$をこの確率的逐次割り当て問題の状態とする。 このとき、 最適政策にしたがって得られる総期待利得を $v(p_{1}, \cdots,p_{n})$ とおけば、 最適性の原理より、 っぎの最適方程式が成り
立つ。

(20)

$v(p_{1}, \cdots,p_{n})=\int_{0}^{\infty}\max_{1\leq k\leq n}\{p_{k}x+v(p_{1}, \cdots,p_{k-1},p_{k+1}, \cdots,p_{n})\}dF(x)$

.
.
として数列
を
$=S_{F}(a_{n-1}^{1}.)-T_{F}(a_{n-1}^{1-1}.)$ で帰納的$..,n$[こ定義する。 たたし、 $S_{F}(z)=z+T_{F}(z)$ とする。 このとき、 数夕
は に.
関する減少 p リであり、となり ($\forall n=1,2,3,$$\forall i=1,2,$
, n)、
この数列
を用いて次の性質が成り立っ。
$–\text{で_{、}}a_{n}^{0}=\infty$$\{a_{n}^{1}$ $\}_{i=0},\cdot$$a_{n}^{1}$$\{a_{n}.\cdot\}:=0,\cdots,n$$\mathrm{I}\mathrm{J}$$a_{n}^{1-1}.\geq a_{n-1}^{1-1}.\geq a_{n}^{1}$$i$$\cdots$$\cdots,$$\{a_{n}^{\dot{l}}\}_{\dot{*}=0,\cdots,n}$定理 7 状態が $(p_{1}, \cdots,p_{n})$ の確率的逐次割り当て問題で、 大きさとする。

$a_{n}^{k}<x\leq a_{n}^{k-1}$

ならば、 この仕事 [こ

$k$

番目の

あり、最適政策にしたがって得られる総期待利得$p_{k}$$x$の仕事が現れたを割り当てることが最適で
ま、$v(p_{1}, \cdots,p_{n})\}$$. \sum_{1=1}^{n}p_{\dot{l}}a_{n}.\cdot$

である。

65
これらの

$a_{n}^{i}$は、 定義から分布関数 $F(x)$ のみで定まり、 $\{p_{1}, p_{2}, \cdots,p_{n}\}$ とは無関係である。 この$\{a_{n}^{i}\}_{i=1,2,\cdots,n}$が、 この確率的逐次割り当て問題の最適政策を定める‘しきい値’ である。 この確率的逐次割り当て問題で、 $p_{1}=p_{2}=\cdots=p_{k}=1,p_{k+1}=$
個の仕事から 個を選択することに等しいか$\ldots=p_{n}=0$ とおけば、 この問題は
$k$

$n$

ら、最適政策にしたがって得られる総期待利得は$\sum_{i=1}^{k}a_{n}^{i}$となる。 このことから、$n$個の仕事の中から $k-1$ 個を選択するとき、 最適政策にしたがって得られる総期待利はだけ減少する。 言い換えれば、 この
得は、 個を選択できるときと比べて$k$$a_{n}^{k}$$a_{n}^{k}$$k-1$ 個選択できる場合に対し、選択する機会が 1 回増えたことによる期待利得の増は 番目に付け加えられた選択の機会の価値とみることができる。
加分となり、
この節の確率的逐次割り当て問題をはじめ、 最適選択問題などにおいて、 仕事の大きさが、 3.1 節のような部分観測可能なマルコフ連鎖の状態に依存する場合にも同じように議論することができる (Nakai[13, 15] など) 52 節では、 このような不完備$a_{n}^{k}$$k$$\text{。}$モデルとして部分観測可能なマルコフ連鎖での確率的逐次割り当て問題を考える。
もちろん、 部分観測可能なマルコフ連鎖での最適選択問題については Nakai $[17, 21]$などに詳しい。

5

不完備情報の多段決定問題

4 節で触れた問題などでは、 不完備情報の多段決定問題を考えることが多く、 この節では、 部分観測可能なマルコフ連鎖や部分観測可能なマルコフ過程における問題を考える。 5.1 節ではジョブ・サーチを、 3.1 節では確率的逐次割り当て問題を考える。 このような部分観測可能なマルコフ連鎖や部分観測可能なマルコフ過程における多段決定問題は数多く、 最適停止問題 (Monahan[12]) や取り替え問題 (Ohnishi,
Kawai and Mine[22] など、 応用範囲は広い。
$)$

5.1

不完備情報のジョブ・サーチ

この節では、 3.1 節で定義した、状態の数が有限または加算無限の場合の部分観測可能なマルコフ過程でのジョブ・サーチを考える。
4.1 節で触れた Lippman and McCa11[9] と同じように、仕事の大きさがマルコフ過程の状態に依存する確率変数で表されているとする。 このとき、 現れた仕事を知って、 状態に関する情報を改良するとともに、 この仕事に就くかどうかを決定する。
マルコフ過程の状態を、 経済の状態などを表すとすれば、 仕事の大きさはこれらの状態により変化し、 経済の状態が良くなれば良い仕事が多く現れ、 そうでなければ良い仕事が現れにくくなる。 この状態についての情報は、 状態空間上の確率分布で表され、 情報全体は $S$ であり、 $S$ の要素のあいだに尤度比順序を考える。 また、 推移確率に関して Lippman and McCa11[9] での仮定 (4.1 節の (2)) より強い仮定 (仮定2) のもとで解析するが、 これはベイズの定理を用いて学習を行うためである。
期間のあいだに、一度に仕事が 1 つずつ現れ、 それらの中から 1 つを選び、選ん$n$

66だ仕事から得られる期待利得を最大にする。 また、 リコールはないものとする。 このとき、 状態についての事前情報を $\mu(\in S)$ とすれば、 仕事の大きさ

$x$

を知ったと

きの事後情報はとなる。
ここで、 事前情報がのとき、 最適政策を用いて得られる期待利得をとする。現れたが のとき、 この仕事を選べば を得、見送ればっぎに現れる仕事に直面$\overline{\mu}(x)$$v_{n}(\mu)$

$\mu$

$x$

$x$

し、 それ以降最適に振る舞うから、最適性の原理よりっぎの最適方程式を満足する。

(21)$v_{n}( \mu)=\int_{0}^{\infty}\max\{x, v_{n-1}(\overline{\mu}(x))\}dF_{\mu}(x)$ここで、 $F_{\mu}(x)= \sum_{s=0}^{S}\mu_{s}F_{s}(x)$ であり、 $v_{1}( \mu)=\int_{0}^{\infty}xdF_{\mu}(x)$ である。

まず、 非負 (可濱 ) 関数 $u(x),$ $v(x)$ [こ対し $U_{F}(u(x), g(x))$ と $V_{F}(u(x),g(x))$ を、$|\mathrm{J}$$U_{F}(u(x),g(x))$$= \int_{0}^{\infty}(u(x)-g(x))^{+}dF(x)$(22)$V_{F}(u(x),g(x))$$= \int_{0}^{\infty}g(x)dF(x)+U_{F}(u(x),g(x))$(23)とすれば $(h(x)^{+}= \max\{h(x), 0\})$$T_{F}(z),$ $S_{F}(z)=z+T_{F}(z)$、これらの $U_{F}(u(x), g(x)),$ $V_{F}(u(x),g(x))$ は、の一般化となってぃる。 したがって、 これらの関数を用いて、 $v_{n}(\mu)$ は帰納的に$v_{n}( \mu)=\int_{0}^{\infty}\{(x-v_{n-1}(\overline{\mu}(x)))^{+}+v_{n-1}(\overline{\mu}(x))\}dF_{\mu}(x)=V_{F}(\mu x, v_{n-1}(\overline{\mu}(x)))$(24)と求めることにより、非負関数の列のとき、$v_{1}( \mu)=\sum_{s=0}^{s}\mu_{s}\int_{0}^{\infty}xdF_{s}(x)$$\{v_{n}(\mu)\}_{\{n=1,2,\cdots\}}$として生成できる (\mu \in S)。 こ

だがら、 (24) 式で生成した関数列は、帰納的に定義可能である。 また、 $S_{n}(\mu)=\{x|v_{n-1}(\overline{\mu}(x))\leq x\}$ とし、 Cn(\mu )=R ヤーとすれば、は残りの計画期間が で、 部分観測可能なマルコフ過程の状態に$S_{n}(\mu)$$S_{n}(\mu)$

ついての情報が$C_{n}(\mu)$

定理 8

$n$

$\mu$

のとき、 現れた仕事に就くことが最適となる仕事の集合であり、は、 見送る方がよい仕事の集合である。 このとき、 っぎの性質が成り立っ。

を任意の正整数とすれば、は の増加関数である。
すれば、
$n$

$v_{n}(\mu)$$v_{n}(\mu)$

は

$\mu$

の増加関数である。 また、 $\mu\in S$ と$n$

すなわち、状態についての情報

が、尤度比の意味で良くなればなるほど、最適に振る舞って得られる期待収益は大きくなる。 また、 最適に振る舞って得られる期待収益は、計画期間が長くなればなるほど、大きくなる。 また、
と
に
$\mu$

$v_{n}(\mu)$$v_{n+1}(\mu)$

は、 つぎの関係がある。

系 3 $h_{n+1}(\mu|x)$ を $h_{n+1}(\mu|x)=xIs_{\pi+1}(\mu)(x)+v_{n}(\overline{\mu}(x))I_{C_{n+1}(\mu)}(x)$ とすれば、$v_{n+1}( \mu)=\int_{0}^{\infty}h_{n+1}(\mu|x)dF_{\mu}(x)$となる。

つぎの定理 9 は、 最適政策と部分観測可能なマルコフ過程の状態につぃての情報$\mu$との関係を示すものである。

67
定理 9 $\mu[succeq]\nu(\mu, \nu\in S)$ とすれば
し $S_{n+1}(\mu)\subset S_{n}(\mu)$ となる。
すなわち、 状態についての情報$S\text{。}+1$$\mu$$(\mu)\subset S_{n+1}(\nu)$となる。 任意の $\mu\in S$ [こ対が、 尤度比の意味で良くなればなるほど、 現れた仕事に就くことが最適となる仕事の集合$S_{n}(\mu)$が小さくなる。 また、 状態につ$\mathrm{a}$$\mathrm{A}$ての情報が同じであれば、 計画期間が長くなればなるほど、 現れた仕事に就くことが最適となる仕事の集合が大きくなる。 これらの定理 8 と定理 9 の性質の証明は省略するが (詳しくは中井 [18] 参照) 、以上の性質をまとめれぱつぎのようになる。

定理 10 部分観測可能なマルコフ過程の状態についての事前情報が のとき、 現れた仕事の大きさが とする。 もし、 $x\in S_{n}(\mu)$ ならば、 この仕事を選ぶことが最適であり、 $x\in C_{n}(\mu)$ ならば見送ることが最適となる。 この最適政策によって得られ
$\mu$

$x$

る期待収益 $v_{n}(\mu)$ は、 (24) 式によって帰納的に求められる。

以上述べてきたことをまとめれば、 つぎのようになる。 部分観測可能なマノレコフ
はこのジョブ・サーチモデ
過程の状態についての事前情報が のとき、集合$S_{n}(\mu)$$\mu$

ルの停止領域になる。 すなわち、 現れた仕事から得られる収益がこの集合に含まれればこの仕事を選び、 そうでなければ見送ることが最適となる。 したがって、 この集合がこのジョブ・サーチの問題の最適政策を決定する。 定理 9 の後半よりこの集合は残りの決定期間が、 長くなればなるほど小さくなる。 また、 定理 9 の前半より状態についての事前情報が、 尤度比の意味で良くなればなるほどこの集合は小さくなることがわかる。 すなわちこれら 2 つの定理が、 このジョブ・サーチの問題の最がこのジョブ.
適政策の性質を決定することになる。 また、 (24) 式で定義したサーチの問題で最適政策によって得られる期待収益だから、 定理 8 がこの値の性質$v_{n}(\mu)$を表している。

5.2

不完備情報の確率的逐次割り当て問題

42 節の確率的逐次割り当て問題を、 これまで考えてきた部分観測可能なマノレコフ
過程で考える。 ここでの部分観測可能なマルコフ過程の状態に関する情報過程、 学
習方法などは、 すべてこれまでと同様とする。
いま、 それぞれの期に現れる投資対象から得られる収益を表す確率変数は、 互$\mathrm{a}$$\mathrm{A}$に独立とするが、 部分観測可能なマルコフ過程の状態に依存し、 それらの状態についての事前情報を、 $\mu(\in S)$ とする。 残り計画期間 のあいだに現れる投資対象に、個に分けられた資本 $\{p_{1}, \cdots,p_{n}\}$ を割り当てるとき $1\geq p_{1}\geq\cdots$ \geq Pn\geq 0、 この
確率的逐次割り当て問題の状態を $(p_{1}, \cdots,p_{n};\mu)$ と表す。
このとき、 大きさが の仕事が現れたとする。 このとき、 この仕事の大きさから状態についての情報を得るとともに、 人なかから 1 人を割り当てる。 番目の人
$n$

$n$

$x$

$k$

$n$

を大きさが

$x$

のとき、 このを得て、 つぎの仕事に直面する。 ことなを用いてベイズの定理によって情報を改良して事後情報はの仕事に割り当てれば、 利得$p_{k}x$$\overline{\mu}(x)$$x$るから、 この確率的逐次害リリ当て問題の状態{ま、 $(p_{1}, \cdots,p_{k-1},p_{k+1}, \cdots,p_{n};\overline{\mu}(x))$ と

68
状態が $(p_{1}, \cdots,p_{n};\mu)$ の確率的逐次割り当て問題で、 最適政策にしたがって得られる総期待利得を $v(p_{1}, \cdots,p_{n};\mu)$ とすれば、 最適性の原理がら、 っぎの最適方程式を満足する。
$v(p_{1}, \cdots,p_{n};\mu)=\int_{0}^{\infty}\max_{1\leq k\leq n}\{p_{k}x+v(p_{1}, \cdots,p_{k-1},p_{k+1}, \cdots,p_{n};\overline{\mu}(x))\}dF_{\mu}(x)(25)$

また、 $n=1$ のときは $v(p_{1}; \mu)=p_{1}\int_{0}^{\infty}xdF_{\mu}(x)$ となる o

つぎに、 (22) 式と (23) 式を用いて、非負関数列 $\{g_{n,:}(\mu)\}$ を帰納的に定義する $(\mu\in$$i=1,2,$, n)。 まず、 $g_{n,:}(\mu)=V_{p}(\mu x, gn-1,:\varpi(x)))-U_{F}(x, g_{n-1,\dot{*}-1}(\mu\overline{\mu}(x)))$とし、 $g_{n,0}(\mu)=\infty,$ $g_{n,n+1}(\mu)=0$ とする $(n=0,1,2, \cdot. .)$ また、$S,$$\cdots$。

$S_{n},:(\mu)=\{x|g_{n-1,:}(\overline{\mu}(x))\leq x<g_{n-1,:-1}(\overline{\mu}(x))\}$とし、 $U_{n,:}( \mu)=.\bigcup_{k=1}^{1-1}S_{n,k}(\mu),L_{n},:(\mu)=R_{+}-U_{n,:+1}(\mu)$ とする。 ただし、 $U_{n,1}(\mu)=$$L_{n,n}(\mu)=\emptyset\text{、}U_{n,n+1}(\mu)=R_{+}$

とおく。 また、$g_{1,1}( \mu)=\sum_{s=0}^{S}\phi_{s}\int_{0}^{\infty}xdF_{s}(x)$がら、 これらの関数列が定義可能である。 このとき、 非負関数の列 $\{g_{n,:}(\mu)\}$ は $(\mu\in S,$ $i=$
$1,2,$, n)、 次のような性質を持っ (Nakai[15] 中井 [18]).

$\cdots$。

定理 11 $n,$ を任意の正整数とすれば、 $g_{n},:(\mu)$ は 増加関数である。 を任意の正整数とし $\mu\in S$ とすれば、 $g_{n},:(\mu)$ は の減少関数である。 また、 を任意の正整数とし $\mu\in S$ とすれば、 $g_{n},:(\mu)$ は の増加関数である。
$i$

$n$

$\mu$

$i$

$i$

$n$

また、 非負関数列 $\{g_{n},:(\mu)\}$ を用いて定義した、 3 っの集合 $S_{n+1,:}(\mu),$ $U_{n+1,:}(\mu)$と $L_{n+1,:}(\mu)$ の関係について、っぎの系が成り立ち、系 5 にょって、 $v_{n}(\mu)$ と $v_{n+1}(\mu)$の関係が示される。
系 4 集合 $S_{n+1,:}(\mu),$ $U_{n+1,:}(\mu)$ と $L_{n+1,:}(\mu)$ は互い [こ素で $S_{n+1,:}(\mu)\cup U_{n+1,:}(\mu)\cup$$L_{n+1,:}(\mu)=R_{+}$となる。

系 5 $h_{n+1,:}(\mu|x)$ を$h_{n+1,:}(\mu|x)=g_{n},:-1(\overline{\mu}(x))I_{U_{n+1,:}(\mu)}(x)+xI_{S_{\mathfrak{n}+1,:}(\mu)}(x)+g_{n,:}(\overline{\mu}(x))I_{L_{\mathfrak{n}+1,:}(\mu)(X)}$とすれば、 $g_{n+1,:}(\mu)$ は $g_{n+1},|$. $( \mu)=\int_{0}^{\infty}h_{n+1,:}(\mu|x)dF_{\mu}(x)$ となる o
ここで、 2 つの領域 $U_{n,k+1}(\mu),$ $L_{n,k}(\mu)$ は、一般には連結な領域となるとは限らない。

このような例は Monahan [12]. Ohnishi, Kawai and Mine [22] などの取り替え問題などではよく現れる現象である。
このとき、 $S_{n+1,:}(\mu)$ は大きい方から 番目の乃を割り当てることが最適となるの領域であり、 $U_{n+1,:}(\mu)$ が、 : より大きい p、 すなゎち大きさががら $p:-1$ まで
$i$

$x$

$p$

$p_{1}$のどれかを割り当てることが最適となる の領域を示してぃる。 反対に、 $L_{n+1,:}(\mu)$は、乃より小さい p、 すなわち乃 からまでのどれかを割り当てることが最適となる の領域を示している。 したがって、 次の 2 っの定理は最適政策の性質を間接的に示している。
$x$

$+1$

$x$

$p_{n}$

69
定理 12 任意の $\mu\in S$ と $i(i=1,2, \cdots, n)$ に対し $U_{n+1,i}(\mu)\subset U_{n,i}(\mu)$ となる。 ま$n+1$ のとき $U_{n+1,i}(\mu)\subset U_{n+1,i}(\nu)$ ととすれば ( , \mbox{\boldmath $\nu$}\in S)、 $i=1,2,$
た、$\mu[succeq]\nu$$\cdots,$

$\mu$

なる。

これら定理 11 と定理 12 の性質をもとに、 部分観測可能なマルコフ過程での確率

的逐次割り当て問題の最適政策と $v(p_{1}, \cdots,p_{n};\mu)$ は、 次の定理のようになる。 これら定理 11 と定理 12 の証明は中井 [18] の付録に詳しく、 定理 13 の証明につ ても同$\mathrm{a}$$\mathrm{A}$

書に詳しい。

定理 13 確率的逐次割り当て問題で状態が $(p_{1}, \cdots,p_{n};\mu)$ のとき、 現れた投資対象から得られる収益を とする。 $x\in S_{n,k}(\mu)$ ならば、 この投資対象に 番目の大きさ
$k$

$x$

の資本

$p_{k}$

を割り当てることが最適となる。 また、最適政策によって得られる総期待

利得 $v(p_{1}, \cdots,p_{n};\mu)$ は $v(p_{1}, \cdots,p_{n};\mu)=\sum_{i=1}^{n}p_{i}g_{n,i}(\mu)$ となる。
定理 11 の非負関数列 $\{g_{n,i}(\mu)\}$ の性質から、最適政策を用いたときの総期待収益の性質が示される。すなわち、 $v(p_{1}, \cdots,p_{n};\mu)=\sum_{i=1}^{n}p_{i}g_{n,i}(\mu)$ だから、 $v(p_{1}, \cdots,p_{n};\mu)$

は状態についての情報が尤度比の意味で良くなれば大きくなる。また、$v(p_{1}, \cdots,p_{n};\mu)$と計画期間 との関係も求められる。 また、 最適政策が集合 $\{S_{n,k}(\mu)\}$ により定まるから、 定理 12 がその性質を表している。
$n$の投資対象に割り当てたときに そのものではなく、一般の利得関数$u(\mu, x)=u(\mu)\cdot x$ とし、 $u(\mu)$$u(\mu, x)$ でも考えることができる。 いま、禾|」得関数をに関する非減少凸関数で、 非負で有限な値をとる関数とすれば、 同様の議論力]\mbox{\boldmath $\theta$}
をできる (Nakai[15])。
たとえば、 $u(\mu, x)=\mu_{1}$ とすればよい。 このとき、 次のようなモデノレを考える。
注 2 収益が

$x$

$x$

$\mu$

いま、 $S$ 個の箱があり、 これらの箱の中のどれかに、 1 つの目的物が隠されて るとし、 この目的物を探す。 一方、 目的物は $S$ 個の箱のあいだを、 部分観測可能なマノレ
コフ連鎖にしたがって移動する。 このとき、 事前情報は $S$ 個の箱の中の目的物の存$\mathrm{A}\mathrm{a}$在確率ベクトルとして与えられ、 情報は箱を探索することで目的物の$\mathrm{A}\mathrm{a}$る場所 [こついての情報を得る。 すなわち、 箱の中を探索して発見すれば探索は終了する力瓢 発
見しなくても目的物の存在確率を学習し更新する。 また、 見逃し確率がある場合も考えられる。 このような探索モデルも、 部分観測が可能なマルコフ連鎖の上での多段決定問題といえる (Pollock[23])。
状態が $(p_{1}, \cdots,p_{n};\mu)$ の確率的逐次割り当て問題において、 42 節と同じよう [こ、$p_{1}=\cdots=p_{k}=1$ とし $p_{k+1}=\cdots=p_{n}=0$ とする。 このとき、 この確率的逐次割り当て問題は、 逐次に現れる 個の投資対象から 個を選んで、 総期待利得を最大にすることになり、 定理 13 より、 最適政策にしたがって得られる総期待収益 {ま
$k$

$n$

$\sum_{i=1}^{k}g_{n,i}(\mu)$となる。 このとき、 $g_{n,i}(\mu)$ は、 この選択モデルで $k-1$ 個の投資対象力$\grave{\grave{>}}$

1‘ R できるとき、 この選択できる機会が 1 回増えることによる総期待収益の増カ D 分を表している。すなわち、 個の投資対象から
$n$

$k$

個を選択するモデルで、 番目 [こ付け加えられた選択の機会で増加する期待収益を表している。

$k$

70
参考文献
[1] S. C. Albright, Optimal Sequential Assignments with Random Arriving Time,Management Science, vol. 21, 60-67, 1974.

[2] S. C. Albright, A Markov-Decision-Chain Approach to aStochastic Assignment
Problem, Operations Research, vol. 22, 61-64, 1974.
[3] M. H. DeGroot, Optimal Statistical Decisions, McGraw-Hill, New York, New
Yor.k, 1970.

[4] C. Derman, G. J. Lieberman and S. M. Ross, ASequential Stochastic Assignment Problem, Management Science, vol. 18, 349-355, 1972.
[5] C. M. Fortuin, P. W. Kasteleyn and J. Ginibre, Correlation Inequalities on
Some Partailly Ordered Sets, Communications on Mathematical Physics, vol.
22, 89-103, 1971.
[6] G. H. Hardy, J. E. Littlewood and G. Polya, Inequality, Cambridge University
Press, 1934.

[7] S. Karlin, Total Positivity, Stanford University Press, Stanford, California,

1968.

[8] S. Karlin and H. M. Taylor, A Second Course in Stochastic Processes: Second
Edition, Academic Press, New York, 1981.
[9] S. A. Lippman and J. J. McCall, Job Search in a Dynamic Economy, Journalof Economic Theory, vol. 12, 365-390, 1976.
[10] S. A. Lippman and J. J. McCall, The Economics of Job Search :ASurvey,
Economic Inquiry,. 14, 347-368, 1976.
$\mathrm{v}\mathrm{o}\mathrm{l}$[11] S. A. Lippman and J. J. McCall (ed), Studies in the Economics of Search,
North-Holland, Amsterdam, 1979.
[12] G. Monahan, Optimal Stopping in aPartially Observable Markov Processes
with Costly Information, O.perations Research, vol. 28, 1319-1334,1980.
[13] T. Nakai, The Problem of Optimal Stopping in aPartially Observable Markov
Chain, Journal of Optimization Theory and Applications, vol. 45, 425-442,
1985.
[14] T. Nakai, Optimal Assignment for aRandom Sequence with an Unknown Number of Jobs, Journal of the Operations Research Society of Japan, vol. 28, 179194, 1985.

71[15] T. Nakai, ASequential Stochastic Assignment Problem in aPartially Observ. $11,230-240$ ,able Markov Chain, Mathematics of Operations Research,$\mathrm{v}\mathrm{o}\mathrm{l}$1986.
[16] T. Nakai, An Optimal Selection Problem with aRandom Number of Applicants. $34,478-485,1986$ .
per Period, Operations Research,$\mathrm{v}\mathrm{o}\mathrm{l}$[17] T. Nakai, An Optimal Selection Problem on aPartially Observable Markov
Chain, Stochastic Modelling in Innovahve Manufacturing (Eds. A. H. Christer,
S. Osaki and L. C. Thomas), Lecture Notes in Economics and Mathematical
Systems, vol. 445, Springer-Verlag, Berlin, 140-154, 1996.

[18] 中井達不完備情報の動的決定モデル, 九州大学出版会, 福岡, 1996.

[19] T. Nakai, An Optimal Assignment Problem for Multiple Objects per Period-Case of aPartially Observable Markov Chain, Bulletin of Informatics andCybernetics, vol. 31, 23-34, 1999.
and aSequential Stochastic Model on aPar[20] T. Nakai, AGeneralized
tially Observable Markov Process, Proceedings of the First Westem Pacific andThird Australia-Japan Workshop on Stochastic Models in Engineering, Technology and Management, (Eds. R. J. Wilson, S. Osaki and M. J. Faddy), The
University of Queensland, Australia, 387-396, 1999.
$\mathrm{M}\mathrm{T}\mathrm{P}_{2}$[21] T. Nakai, Learning Procedure for aPartially Observable Markov Process andits Applications, Discussion Paper Series, No. 2001-5, Kyushu University, 1-30,

2001.
[22] M. Ohnishi, H. Kawai and H. Mine, An Optimal Inspection and Replacement
Journal of Operations RePolicy under Incomplete State
search, vol. 27, 117-128, 1986.
$\mathrm{I}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n},European$[23] S. M. Pollock, ASimple Model of Search for aMoving Target, Operations
Research, vol. 18, 883-903, 1970.
[24] C. J. Preston, AGeneralization of the FKG Inequaliteis, Communications onMathematical Physics, vol. 36, 233-241, 1974.
[25] S. M. Ross, Quality Control under Markovian Deterioration, Management Science, vol. 17, 587-596, 1971.
[26] S. M. Ross, Stochastic Processes, John Wiley and Sons, New York, New York,1983.
[27] D. Stoyan, Comparison Methods for Queues and Other Stochastic Models, John
Wiley&Sons, New York, New York, 1983.