数理解析研究所講究録
第 1857 巻 2013 年 84-94

84

マルコフ決定過程における統計的手法について(Statistical Methods in Markov Decision Processes)
神奈川大学・理学部

正之 (Masayuki HORIGUCHI)

堀口

Faculty of Science, Kanagawa University

1Introduction

本発表では，推移確率行列が未知であるマルコフ決定過程 (Uncertain Markov DecisionProcesses) において，推移確率行列の推定と行動 (action) の選択に関する考察を行う．

扱うモデルは，有限状態空間をもち状態観測は確実にできる場合である．また，停止問題に関しては，いつかは必ず停止する，すなわち有限期間内において停止の行動が取られるものとする．推移確率行列の推定は，古典的な問題として扱われる．
例えば，状態推移法則のマルコフ性を調べる (検定する) ために，初期分布と推移検定などを行う手法がある$(p_{i})$の十分統計量を使って，推移確率行列の(Billingsley(1961)). ひとたび，マルコフ連鎖であることが過程できれば，適切な条件下で状態の頻度$\chi^{2}$$(f_{ij})$

定常分布が求まり最適化問題を容易に解くことができる．
また，行動空間 (action space) が加わりマルコフ決定過程での同様の推移確率行列が未知の最適化問題については，適応政策 (adaptive policy) の構成について，最尤推定法によるもの (Kurano(1972), Mandl(1974) など) や reward-penalty type によるもの (Ku-rano(1987), Iki-Horiguchi-Yasuda-Kurano(2007)$)$などの先行研究がある．例えば，次のような統計量がある (Billingsley(1961)):$S=\{1,2, \ldots, s\},$$x_{t}=a_{t}:t$

期の状態，: $n+1$ 期までの状態推移の確率$p_{a_{1}}p_{a_{1}a_{2}}\cdots p_{a_{n}a_{n+1}}$$F=(f_{ij}):i$ から $j$ への推移の回数表す $s\cross s$ 行列

このとき，$p_{a_{1}}p_{a_{1}a_{2}}\cdots p_{a_{n}a_{n+1}}=\Pi_{ij}p_{ij}^{f_{1j}}$と表すことができ，$\sum_{j}\frac{(f_{ij}-f_{i}p_{lj}’)^{2}}{f_{i}p_{ij}}\sim\chi^{2}(d_{i}-1)$が成り立つ．ただし， は $p_{ij}>0$ を満たす状態 の個数である．
また、マルコフ決定過程においては，例えば，平均期待利得 (Average reward criterion)$d_{i}$$i$

85の場合には、 Bellman 方程式:$g+h(i)= \max_{a\in A}(r(i, a)+\sum_{j=0}^{\infty}p_{ij}(a)h(j)), i\geqq 0$を満たすような optimal value$g$と relative value $h(i)$ が推移確率行列 $p_{ij}(a)$ から求められる．ここで， は行動空間を表し， は の元で行動を表す．また，$r(i, a)$ は，状態 で行動 を選択したときの 1 期間での利得の期待値を表す．マルコフ決定過程における各種の評価関数に対する Bellman 方程式については，詳しくは [10] などを参照されたい．
$A$$a$$A$$i$$a$

推移確率行列が未知の場合には，状態観測からの頻度分布をもとに，推移法則や定常分布の推定と successive approximation によって評価関数値 (optimal value) の近似が行われる．また，推移法則の逐次推定としてベイズ推定を用いることも有効であり，そのときには，上記のような Bellman 方程式が導かれる (White(1969), Horiguchi-Piunovskiy([5],submitted)).

先行研究では，推移確率行列に対して，事前測度区間にょる区間ベイズ法 (De Robertisand Hartigan $1981[1])$ の考え方で，各成分が閉区間で表現される推移行列をもつ区間ベイズ MDPs(Interval Bayesian estimated MDPs) を構成した ([6]). さらに，逐次抜き取り問題について考察し，リスク関数の評価の区間表現を行った ([4]). 本報告では，論文 [4] での逐次抜き取り問題について，損失関数を特徴づけてぃる閾値を，感度解析的な観点で，ベイズリスクがある一定の値以下となる場合について調べる．

2Notation

以下のような，逐次抜き取り検査問題について考える ([15]). 非常に多量な同製品のまとまり (製品群)からの抜き取り問題で，一回ごとーつの製品を抜き取り不良品 (defectiveitem) か良品 (non-defective item) かを検査する．一回あたりの検査費用はとする．ここでの目的は，不良品を含む製品群の出荷を回避し，また，良品を含む製品群を検査によっ$c$て不良品と判断することをできるだけ回避することである．そこで，製品群の不良率$p$にをそれぞれ以下のように定義する:
対して，損失関数未知の不良率 $p\in(O, 1)$ があり，$a(p),$ $r(p)$$\{\begin{array}{l}a(p) :不良率 p の製品群を accept する時の損失 r(p) :不良率 p の製品群を reject する時の損失\end{array}$とする $(p\cong O$ なら $a(p)=0,$ $p\cong 1$ なら $r(p)=0$ とする．一般には下に有界であれば良い$)$.

抜き取り検査問題としては，母不良率 の検定として検出カに対するサンプルサイズの決定問題も一つの手法といえるが，ここでは不良率 は非常に小さな値も取りえると
$P$

$P$

86
考えて逐次抜き取りによる検査費用とリスク評価での停止問題を考える．
を不良率 の事前分布，観測度数 $N$ において 個の不良品と $n=(N-m)$ 個今，$G_{0}(p)$$m$$p$の良品を観測しているとする． は二項分布に従うから，このときの の事後分布 $G_{m,n}(p)$
$m$

$p$

は次の (2.1) のようになる．
記号の説明:: 一回当たりの検査費用，$G_{0}(p)$ : 不良率の事前分布，
$c$

$p$

$\{x_{1}, x_{2}, \ldots, x_{N}\}$: $N$ 個の観測値，(2.1)$dG_{m,n}(p)= \frac{p^{m}(1-p)^{n}dG_{0}(p)}{\int_{0}^{1}p^{m}(1-p)^{n}dG_{0}(p)}.$$v(m, n)$のもとで$P$

回の検査で $m$ 個の不良品と 個の良品であったという結果の確率分布が $G_{m,n}(p)$ であり以後は最適政策を用いて得られる期待損失を表

は，これまでの$N$$n$すとする．このとき，簡単に $(m, n)$ が十分統計量であることがわかり，次の関数方程式が得られる．

(2.2)$v(m, n)= \min$$\{$Stop(Accept):$\int_{0}^{1}a(p)dG_{m,n}(p)$Stop(Reject):$\int_{0}^{1}r(p)dG_{m,n}(p)$,,Continue: $c+ \int_{0}^{1}(pv(m+1, n)+(1-p)v(m, n+1))dG_{m,n}(p)$$= \min\{\psi(m, n), c+b_{m,n}v(m+1, n)+(1-b_{m,n})_{1}\prime,(m, n+1)\}.$$\psi(m, n)=$ mm
ただし，$\{\int_{0}^{1}a(p)dG_{m,n}(p),$ $\int_{0}^{1}r(p)dG_{m,n}(p)\},$ $b_{m,n}= \int_{0}^{1}pdG_{m,n}(p)$であるとする．

以下の定理が成り立つことが知られている ([16]).

Theorem 2.1. 次の二つの条件(i) $\psi(m, n)\geqq 0$ for all $m,$ $n=0,1,2,$$\ldots,$(ii) $\psi(m, n)arrow 0$ as $m+narrow\infty$が成り立つならば，$(m, n)$ は関数方程式 (2.2) の唯一の解である．
$\tau$)

ここで，事前分布を事前測度区間 $I(L, U)$ に置き換えた場合を考える (cf. [6]). 簡単の$I(L, U)=[L, kL]$ であって， は [0,1] 上のルベーグ測度であるとする．
ため，
$L$

87
リスク関数について，簡単に以下のようにまとめておく:
危険関数 (risk function):$r( \theta, \delta)=\int_{X}\ell(\theta, \delta(x))f_{n}(x|\theta)dx.$

ただし，$\ell(\theta, \delta(x))$

は損失関数 (loss function) を表し， は母数パラメータ，$\theta$$\delta(x)$は決定関数を表す．

ベイズ危険 (Bayes risk): ( ( ):事前分布)$\pi$$\theta$$r_{\beta}( \delta)=\int_{\Theta}r(\theta, \delta)\pi(\theta)d\theta.$

事後危険 (posterior risk):$r( \delta(x)|x)=\int_{\Theta}l(\theta, \delta(x))\pi(\theta|x)d\theta.$

損失関数を$\ell(d,p)=\{\begin{array}{l}a(p) (d=d_{1}) ,r(p) (d=d_{2})\end{array}$とするときの，$Q\in I(L, U)$ に関するベイズリスクを(2.3)$\beta(\ell, Q)$と表して次のように定める:$\beta(\ell, Q)=\min_{d}\{\frac{Q(\ell(d,p))}{Q(1)}\}=\min\{\frac{Q(\ell(d_{1},p))}{Q(1)}, Q(\ell(d_{2},p))Q(1)\}.$

ただし，測度 $Q\in I(L, U)$ と可測関数$g$に対して $Q(g)= \int g(p)dQ(p)$ と表すことにす$-\infty<\lambda<\infty$
る．このとき，ベイズリスク (2.3) の区間表現は，に対して次の方程式の解$\lambda_{1},$$\lambda_{2}$として得られる．

Theorem 2.2. ([ )$1J$(i) $\min\{\beta(\ell, \theta)|Q\in I(L, U)\}$ の下限値
(2.4)$\lambda_{1}$は次の方程式の唯一の解である．

$\min_{d}\{U(\ell(d,p)-\lambda)^{-}+L(\ell(d,p)-\lambda)^{+}\}=0.$(ii) $\min\{\beta(\ell, \theta)|Q\in I(L, U)\}$ の上限値は次の方程式の唯一の解(2.5)$\cdot$$\lambda_{2}$を超えない:$\min_{d}\{L(\ell(d, p)-\lambda)^{-}+U(\ell(d, p)-\lambda)^{+}\}=0.$88$x^{+}= \max\{0, x\},$ $x^{-}=x-x^{+}= \min\{0, x\}$ とする．
ただし，ここで，事前測度を$G_{m,n}(\cdot)\in I(L_{m,n}, U_{m,n})$用すると，$G_{m,n}(\cdot)$$G_{0}()$$\in I(L, U)=[dp, kdp]$とし，そのときの事後区間測度に関して Theorem 2.2 を式 (2.2) で与えられている $\psi(m, n)$ に適に関する期待損失 (ベイズリスク) の区間表現$[\underline{\psi}(m, n),\overline{\psi}(m, n)]$を得る．さらに，区間推定マルコフ決定過程 (interval estimated MDPs(Horiguchi(preprint)))が以下の方程式の解として得らの結果から， についても区間表現$b_{m,n}$$[\underline{b}_{m,n},\overline{b}_{m,n}]$$\underline{\lambda},\overline{\lambda}$

れる :

(2.6)

$\underline{\lambda}=\frac{Be(m+2,n+1)+(k-1)Be(m+2,n+1,\underline{\lambda})}{Be(m+1,n+1)+(k-1)Be(m+1,n+1,\underline{\lambda})},$(2.7)$\overline{\lambda}=\frac{kBe(m+2,n+1)-(k-1)Be(m+2,n+1,\overline{\lambda})}{Be(m+1,n+1)-(k-1)Be(m+1,n+1,\overline{\lambda})}.$

ただし，Be $(m+1, n+1)= \int_{0}^{1}t^{m}(1-t)^{n}dt,$ $Be(m+1, n+1, x)= \int_{0}^{x}t^{m}(1-t)^{n}dt$ である．

具体的な数値例は，[4] を参照のこと．
次が成り立つ．

Theorem 2.3. 区間表現 $Lv(m, n),\overline{v}(m, n)]$ の各端点について次が成り立つ:(1) $\overline{v}(m, n)=\min\{Stop:\overline{\psi}(m, n)$ , Continue:
1 ,$)$$c+\underline{b}_{m,n}\overline{v}(m+1, n)+(1-\underline{b}_{m_{\}}n})\overline{v}(m, n+1)\}\}.$(2) $\underline{v}(m, n)=\min\{Stop:\underline{\psi}(m, n)$ , Continue:1 ,$)$

(3)$\max\{c+\overline{b}_{m,n}\overline{v}(m+1, n)+(1-\overline{b}_{m,n})\overline{v}(m,$ $n+$$\min\{c+\underline{b}_{m,n}\underline{v}(m+1, n)+(1-\underline{b}_{m,n})\underline{v}(m,$$n+$$c+\overline{b}_{m,n}\underline{v}(m+1, n)+(1-\overline{b}_{m,n})\underline{v}(m, n+1)\}\}.$$\underline{v}(m, n),\overline{v}(m, n)$のそれぞれに対する最適政策は，それぞれの関数方程式を満たす決定政策である．

3Examples[4] では，[11] の例題に沿って次のように条件設定をして，区間ベイズ推定を適用した場合の数値例を考えた．損失関数 $a(p),$ $b(p)$ を$a(p)=\{\begin{array}{l}0, 0\leqq p\leqq\frac{3}{4},1, \frac{3}{4}<p\leqq 1,\end{array}$とし，Go(P)$=$$r(p)=\{\begin{array}{l}1, 0\leqq p\leqq\frac{1}{4},0, \frac{1}{4}<p\leqq 1,\end{array}$p(一様), $I(L, U)=[L, kL]=[dp, kdp],$ $c=0.04$ とする．

89$r(p)$

Figure 3.1: loss functions $a(p),$ $r(p)$ベイズリスクの区間表現
riskに関しては，まず と$[\lambda_{1}, \lambda_{2}]$$(\lambda_{1})$$d_{1}$$d_{2}$

に関して，その下限値と上限値を求めると Lower Bayesのそれぞれについて期待損失に関する解として，(3.1)$\lambda_{1}^{d_{1}}=\frac{1-Be(m+1,n+1,\frac{3}{4})}{1+(k-1)Be(m+1,n+1,\frac{3}{4})})$(3.2)$\lambda_{1}^{d_{2}}=\frac{Be(m+1,n+1,\frac{1}{4})}{k+(1-k)Be(m+1,n+1,\frac{1}{4})},$

90が得られ，Upper Bayes risk$(\lambda_{2})$に関しては，(3.3)$\lambda_{2}^{d_{1}}=\frac{k(1-Be(m+1,n+1,\frac{3}{4}))}{k+(1-k)Be(m+1,n+1,\frac{3}{4})},$(3.4)$\lambda_{2}^{d_{2}}=\frac{kBe(m+1,n+1,\frac{1}{4})}{1+(k-1)Be(m+1,n+1,\frac{1}{4})}$を得る．従って，$\lambda_{1}=\min\{\lambda_{1}^{d_{1}}, \lambda_{1}^{d_{2}}\}$と$\lambda_{2}=\min\{\lambda_{2}^{d_{1}}, \lambda_{2}^{d_{2}}\}$とからベイズリスクの下限値と上限値をそれぞれ具体的に求めることができる．また，最適政策の期待損失に関する区間表現 $Lv(m, n),\overline{v}(m, n)]$ も Theorem 2.3 によって求めることができる．

ここで，$a(p),$ $r(p)$ を次のように変えて区間表現を調べてみる．
$0,$(3.5)$a(p)=\{$

1,$0\leqq p\leqq a_{1}$’$r(p)=\{$$a_{1}<p\leqq 1$

1,$0\leqq p\leqq r_{1}$$0,$$r_{1}<p\leqq 1$

すなわち，$a(p),$ $r(p)$ のグラフにおけるジャンプの点 (不連続点) を$a_{1},$$r_{1}$とする．上の式(3.1), (3.2), (3.3), (3.4) と同様に，ベイズリスクの下限値と上限値が以下のように得られる．

Lower Bayes risk$(\lambda_{1})$

:

(3.6)

$\lambda_{1}^{d_{1}}=\frac{1-Be(m+1,n+1,a_{1})}{1+(k-1)Be(m+1,n+1,a_{1})},$(3.7)$\lambda_{1}^{d_{2}}=\frac{Be(m+1,n+1,r_{1})}{k+(1-k)Be(m+1,n+1,r_{1})}.$

Upper Bayes risk$(\lambda_{2})$

:

(3.8)

$\lambda_{2}^{d_{1}}=\frac{k(1-Be(m+1,n+1,a_{1}))}{k+(1-k)Be(m+1,n+1,a_{1})},$(3.9)$\lambda_{2}^{d_{2}}=\frac{kBe(m+1,n+1,r_{1})}{1+(k-1)Be(m+1,n+1,r_{1})}.$$\lambda_{1}^{d_{1}},$$\lambda_{2}^{d_{1}}$をについての関数，$\lambda_{1}^{d_{2}},$$a_{1}$$\lambda_{2}^{d_{2}}$をとで，それぞれの関数の単調性が示される．

$r_{1}$についての関数とするとき，次の補題のも91
Lemma 3.1. $0<x<x’$ となる実数 , 〆と実数 $k>0$ に対して次が成り立っ．
$x$$\frac{x}{k+(1-k)x}<\frac{x’}{k+(1-k)x’}$

不完全ベータ関数 Be $(m, n, x)$ はら次を得る．

Theorem 3.1.

$\lambda_{1}^{d_{1}},$$\lambda_{2}^{d_{1}}$は$a_{1}$$x$に関して単調増加であるので，上の Lemma 3.1 かに関して単調減少関数，$\lambda_{1}^{d_{2}},$$\lambda_{2}^{d_{2}}$は$r_{1}$に関して単調増加関数である．
Remark;$a_{1},$$r_{1}$の値を行動空間の値と考えて，Bayes riskの抜き取り費用を表す) となるような最小のTable 3.2).

損失関数の$a_{1},$$r_{1}$$a_{1}$(ただし は一回当たりの値を調べる (Table 3.1,$\lambda 1^{j}\leqq c$の値と最大の$r_{1}$$c$を変化させたときのベイズリスクの下限値，上限値のグラフは以下$m=1,$ $n=2$ のときの図内 (Figure 3.2) のそれぞれの単調関数は，単調減のようになる．

少関数はそれぞれ$\lambda_{1}^{d_{1}},$$\lambda_{2}^{d_{1}}$を表し，単調増加関数はそれぞれ$\lambda_{1}^{d_{2}},$$\lambda_{2}^{d_{2}}$を表す．例えば，縦軸の値に一回当たりの抜き取り検査費用 の値を取ったときの横軸に相当する値が Table
3.1,3.2 の表内に示されている値である．
$c$92
Lower bayes risk, (m,n) $=(1,2)$

Upper bayes risk, (m,n) $=(1,2)$

Lower and Upper bayes risk, (m,n) $=(1,2)$

Figure 3.2: Lower and Upper bounds for $\psi(m, n)\leqq c=0.04$

93

References[1] L. De Robertis and J. A. Hartigan. Bayesian inference using intervals of measures.
Ann. Statist., $9(2):235-244$ , 1981.

[2] M. H. DeGroot. Optimal Statistical Decisions. Wiley Classics Library, reprint of
the 1970 original, John Wiley & Sons, 2004.
[3] D. J. Hartfiel. Markov set-chains, volume 1695 of Lecture Notes in Mathematics.
Springer-Verlag, Berlin, 1998.

[4] 堀口正之．区間ベイズ手法と逐次抜き取り問題について．RIMS 講究録 1802「不確実不確定環境下における数理的意思決定とその周辺」 , pages 85-91, 2012.
[5] M. Horiguchi and A.B. Piunovskiy. Optimal stopping model with unknown transition probabilities. submitted, 2013.

[6] 伊喜哲一郎，堀口正之，安田正實，蔵野正美．不確実性の下でのマルコフ決定過程に対する区間ベイズ手法 (An interval bayesian method for uncertain MDPs), RIMS
講究録 1636 「不確実性と意思決定の数理」 , p. l-p.8, 2009/04.
[7] M. Kurano, J. Song, M. Hosaka, and Y. Huang. Controlled Markov set-chains withdiscounting. J. Appl. Probab., $35(2):293-302$ , 1998.
[8] M. Kurano, M. Yasuda, and J. Nakagami. Interval methods for uncertain Markovdecision processes. In Markov processes and controlled Markov chains (Changsha,1999), pages 223-232. Kluwer, 2002.

[9] J. J. Martin. Bayesian decision problems and Markov chains. Publications in Operations Research, No. 13. John Wiley & Sons Inc., 1967.
[10] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons Inc., 1994.
[11] 坂口実．経済分析と動的計画．東洋経済新報社，1970.
[12] K. $M$ . van Hee. Bayesian control of Markov chains, volume 95 of MathematicalCentre Tracts. Mathematisch Centrum, 1978.
[13] G. B. Wetherill. Bayesian sequential analysis. Biometrika, $48(3):281-292$ , 1961.

[14] S. S. Wilks. Mathematical statistics. A Wiley Publication in Mathematical Statistics.
John Wiley &Sons Inc., 1962. 田中英之，岩本誠一 (訳), 「数理統計学・増訂新版
1,2 , 1971,1972 年，東京図書．
$\rfloor$

94[15] A. Wald. Statistical Decision Functions. John Wiley&Sons Inc., New York, N.
1950.
[16] D. J. White. Dynamic programming.
Mathematical Economic Texts, 1.

$Y$.,

Oliver&Boyd, Edinburgh-London, 1969.