数理解析研究所講究録
第 1802 巻 2012 年 193-199

193

多段決定問題と Stochastic Convexity について

千葉大学教育学部

中井

達 (T\={o}ru Nakai)

Faculty of Education, Chiba University

1

はじめに[6] において、評価と関連する状態に関する状態をもとに、支出を決定する逐次決定問題を扱った。 また、 状態は支出によって変えることが出来た。 ここでは、 [6] などで扱った問題を費用最小化 (利得最大化) 問題に応用することを考える。
いま、 自動車や電化製品などに関して問題が生じたとき、 どのように対応するかを決定するモデルを考える。 ここでは、 製品の状態を $(0, \infty)$ によって表し、 状態を表す値が大きくなれば状態が良くなるとする。 また、 この状態は決定にかかわらず、 マルコフ過程にしたがって状態が推移する。 このとき、 計画期間内で費用 (利得) を最小化 (最大化 する最適政策と最適政策にしたがったときに得られる最適値について考える。 また、$s$$)$[6] などと同様に、 問題が生じたときに取った決定により状態は変化するとする。

2多段決定問題
状態空間を $(0, \infty)$ とし、 状態を表す値が大きくなれば状態が良くなるとする。 状態のとき、 決定を取れば、 新しい状態をとできる $(\alpha\geq 1)$ 。このときの費用をとする。 $u(s)$ を最後の期の状態が のときの終端費用 (終端利得) とする。 また、状態が確率的に推移する場合を考えるときには、 状態は推移法則を $P=(p_{s}(t))_{s,t\in(0,\infty)}$とするマルコフ過程にしたがって推移するとする。と $0<\lambda<1$ となるで定義された関数 $u(s)$ が、 任意のに対してが$s$$\alpha$$\mathcal{S}$$\alpha s$$C(\alpha)$$s$$\mathcal{S}\in(0, \infty)$$\hat{s}<\overline{s}$$\lambda$(1)$u(\hat{s}^{\lambda}\overline{s}^{1-\lambda})\geq(\leq)\lambda u(\hat{s})+(1-\lambda)u(\overline{s})$となるとき、 この関数 $u(s)$ をここでは簡単のために $P$ -concave( $P$ -convex) と言う。

補題 1 $u(s)$ を $P$ -concave( $P$ -convex) とする。
$u($$\hat{s}<\overline{s},\hat{s}’<\overline{s}’$となる$\hat{s}^{\frac{-}{s}},$$7,$$\overline{s}’$に対して、ず $)-u(\hat{s}’)\leq(\geq)u(\overline{s})-u(\hat{s})$ .

(2)である。
$v(s)= \min_{\alpha\geq 1}\{C(\alpha)+u(\alpha s)\}$$v(s)$とするとき、 $u(s)$ が$s$の増加 (減少) 関数であれば、も増加 (減少) 関数であることは明らかである。

補題 2 $v(s)= \min_{\alpha\geq 1}\{C(\alpha)+u(\alpha s)\}$ とする。

$C(\alpha)$

は $P$ -concave のとき、$u(\mathcal{S})$が $P$-concave ならば、 $v(s)$ も -concave である。 また、 $u(s)$ が -convex ならば、 $v(s)$ もは増加関数とする。
-convex である。 ただし、
$P$

$P$

$P$$C(\alpha)$194
補題 3 $v(s)= \max_{\alpha\geq 1}\{-C(\alpha)+u(\alpha \mathcal{S})\}$ とする。 このとき、 $u(s)$ が $P$-concave ならば、が $P$ -convex のとき、 $u(s)$ が $P$ -convex ならば、また、$v(s)$ も $P$ -concave である$C(\alpha)$$\circ$$v(s)$2.1

も $P$ -convex である。 ただし、 $C(\alpha)$ は増加関数とする$\circ$Partial Maintenance を考慮した多段決定問題 I

状態空間を $(0, \infty)$ とし、 状態が$s$のとき、 決定$\alpha$を取れば、 新しい状態を$\alpha s$とできる $(\alpha\geq 1)$ 。このときの費用を $C(\alpha)$ とし、 最小化問題 (最大化問題) では、 $u(s)$ を最後は増加の期の状態が のときの終端費用 (利得) とする。 また、 $C(O)=0$ であり、関数とする。このとき計画期間内の総費用 (総利得) を最小化 (最大化) する問題を考える。 始めに、 状態が確率的に推移しないとする。
状態が のとき、 期間にわたって決定を行い総費用 (総利得) を最小 (最大) にする問題で、 最適政策にしたがったときに得られる総費用 (総利得) を $w_{n}(s)$ とすれば、 最$C(\alpha)$

$s$

$n$

$s$

適性の原理よりつぎの最適方程式が得られる。
(I) 最小化問題$w_{n}(s)= \min_{\alpha\geq 1}\{C(\alpha)+w_{n-1}(\alpha s)\}$(3),

ここで $w_{1}(s)= \min_{\alpha\geq 1}\{C(\alpha)+u(\alpha s)\}$ とする。ただし、 $u(s)$ はは$P$$\alpha$の増加関数とする。 また、 $u(s)$ が$P$$s$の減少関数とし、-concave となる問題を考えるときは、$C(\alpha)$$C(\alpha)$

は-concave とする。
(II) 最大化問題$w_{n}(s)= \max_{\alpha\geq 1}\{-C(\alpha)+w_{n-1}(\alpha s)\}$の増加関数とし、の増加関数とする。 また、 $u(s)$ が -convex となる問題を考えるときは、ここで $w_{1}(s)= \max_{\alpha\geq 1}\{-C(\alpha)+u(\alpha s)\}$ とする。 ただし、 $u(s)$ は$C(\alpha)$は$\alpha$$C(\alpha)$$\circ$を選択しのとき、 つぎの性質が成り立つ。
$s$のとき、$(\alpha\geq 1)$ 、$\alpha$費用$C(\alpha)$を支払って状態

補題 4(最小化問題) $w_{n}(s)$ は、$s$に関する減少関数である。

補題 5(最大化問題) $w_{n}(s)$ は、$s$に関する増加関数である。

補題 6 (最小化問題)
$P$

$s$

$P$

は $P$ -convex とする状態が(4),-concave である$\circ$$C(\alpha)$$s$を$\alpha s$できる。 こは $P-con\omega ve$ のとき、 $u(s)$ が $P$-concave ならば、$u(s)$ が $P$-convex ならば、

$w_{n}(s)$は $P$-convex である$w_{n}(\mathcal{S})$は$\circ$補題 7 (最大化問題) $u(s)$ が $P$ -concave ならば、 $w_{n}(s)$ は $P$ -concave である。 また、は $P$ -convex のとき、 $u(s)$ が $P$-convex ならば、 $w_{n}(s)$ は $P$ -convex である。

$C(\alpha)$

このように、 以下の議論では、 最小化問題で、 $u(s)$ が $P$ -concave となる問題を考える

ときは、 $C(\alpha)$ は $P$ -concave とし、 最大化問題で $u(s)$ が $P$ -concave となる問題を考える
ときは、 $C(\alpha)$ は $P$ -concave とする。
は補題 8 (最小化問題) $u(s)$ が $P$-concave ならば、は に関して減少する。
$u(s)$ が $P$ -convex ならば、$\alpha_{n}(s)$$\alpha_{n}(s)$$s$$s$に関して増加する。 また、

195
補題 9(最大化問題) $u(s)$ が -concave ならば、
$P$$u(s)$ が $P$-convex ならば、$\alpha_{n}(s)$は$s$$\alpha_{n}(s)$-convex ならば、$\alpha_{n}(s)$3-convex ならば、$\alpha_{n}(s)$に関して減少する。 また、$\alpha_{n}(\mathcal{S})$は $n$ に関して増加する。 また、は $n$ に関して減少する。

補題 11 (最大化問題) $u(s)$ が $P$-concave ならば、$u(s)$ が $P$$s$に関して増加する。

補題 10 (最小化問題) $u(s)$ が $P$ -concave ならば、
$u(s)$ が $P$

は$\alpha_{n}(s)$は $n$ に関して減少する。 また、は $n$ に関して増加する。

Stocahstic Convexity and Concavity$X$と $Y$ を 2 つの確率変数とするとき、 基本的な確率的な順序関係として、 つぎのようなものが知られている。

(1) 任意の増加関数 $u(s)$ に対して、 $E[u(X)]\geq E[u(Y)]$ であるとき、 $X\geq s\tau Y$ と表す (stochastic order)(2) 任意の増加 (減少) 凸 (convex) 関数 $u(s)$ に対して、 $E[u(X)]\geq E[u(Y)]$ であるとき、 $X\geq ICX(\geq Dcx)Y$ と表す。 (increasing (decreasing) convex order)(3) 任意の増加 (減少) 凹 (concave) 関数 $u(s)$ に対して、 $E[u(X)]\geq E[u(Y)]$ であると$X\geq ICV(\geq DCV)Y$ と表す (increasing (decreasing) concave order)
き．
$\circ$$\circ$

つぎに、 Shaked and Shanthikumar [9] にしたがって、数列$\{X(s)|s\in(-\infty, \infty)\}\ovalbox{\tt\small REJECT}>$$s$

をパラメータとする確率変対して、 Stocahstic Convexity と Stocahstic Concavity をつぎのように定義する。

(1) $\{X(s)|s\in(-\infty, \infty)\}$ が $SI$ であるとは、任意の増加関数 $u(s)$ に対して、 $E[u(X(s))]$が、 の増加関数となることをいう。 (stocahstically increasing)(2) $\{X(s)|s\in(-\infty, \infty)\}$ が SICX であるとは、 任意の増加凸関数 $u(s)$ に対して、$E[u(X(s))]$ が、 の増加凸関数となることをいう。 (stocahstically increasing andconvex)(3) $\{X(s)|s\in(-\infty, \infty)\}$ が SICV であるとは、 任意の増加凹関数 $u(s)$ に対して、$E[u(X(s))]$ が、 の増加凹関数となることをいう。 (stocahstically increasing andconcave)(4) $\{X(s)|s\in(-\infty, \infty)\}$ が $SD$. であるとは、任意の増加関数 $u(s)$ に対して、 $E[u(X(s))]$が、 の減少関数となることをいう。 (stocahstically decreasing)(5) $\{X(s)|s\in(-\infty, \infty)\}$ が SDCX であるとは、 任意の増加凸関数 $u(s)$ に対して、$E[u(X(s))]$ が、 の減少凸関数となることをいう。 (stocahstically decreasing andconvex)(6) $\{X(s)|s\in(-\infty, \infty)\}$ が SDCV であるとは、 任意の増加凹関数 $u(s)$ に対して、$E[u(X(s))]$ が、 の減少凹関数となることをいう。 (stocahstically decreasing andconcave)
$s$

$s$

$\mathcal{S}$

$s$

$s$

$s$

つぎに、 $s_{1}\leq s_{2}\leq s_{3}\leq s_{4}$ で $s_{1}+s_{4}=s_{3}+s_{2}$ のとき、 $X_{i}=X(s_{i})$ とおく$(i=1,2,3,4)$。

$(s_{4}-s_{3}=s_{2}-s_{1})$このとき、 SICX や SICV より弱い概念である

SICX(sp) と SICV(sp) をつぎのように定義する。

196(1) $\{X(s)|s\in(-\infty, \infty)\}$ が SICX(sp) であるとは、 $\max\{X_{2}, X_{3}\}\leq X_{4}$ であり (a.s.)$X_{2}+X_{3}\leq X_{1}+X_{4}$ であることをいう。 (stocahstically increasing and convex in、

sample path sense)(2) $\{X(s)|s\in(-\infty, \infty)\}$ が SICV(sp) であるとは、 $X_{1} \leq\max\{X_{2}, X_{3}\}$ であり (a.s.),$X_{2}+X_{3}\geq X_{1}+X_{4}$ であることをいう。 (stocahstically increasing and concave insample path sense)
補題 12(1) $\{X(s)|s\in(-\infty, \infty)\}$ が SICX$(sp)$ ならば、 SICX である o(2) $\{X(s)|s\in(-\infty, \infty)\}$ が SICV$(sp)$ ならば、 SICV である。
例 1 $X(\mu)$ を正規分布
SICV$(sp)$ である。

補題 13

$N(\mu,\sigma^{2})$とする。 $\{X(\mu)|\mu\in(-\infty, \infty)\}$ は SICX$(sp)$ であり(1) $\{X(s)|s\in(-\infty, \infty)\}$ が SICX$(sp)$ であり、$u(\cdot)$

を増加凸関数とする。 このとき、 $\{u(X(s))|s\in(-\infty, \infty)\}$ もまた SICX$(sp)$ である。

(2)$\{X(\mathcal{S})|\mathcal{S}\in(-\infty, \infty)\}$が SICV$(sp)$ であり、$\{u(X(\mathcal{S}))|s\in(-\infty, \infty)\}$$u(\cdot)$

を増加凹関数 とする。 このとき、もまた SICV$(sp)$ である。とする。 $Y(\mu)=e^{X(\mu)}$ とおけば、 $u(x)=e^{x}$ が増加凸例 2 $X(\mu)$ を正規分布関数だから $\{Y(\mu)|\mu\in(-\infty, \infty)\}$ は SICX$(sp)$ である。 したがって、 $Y(\mu)$ は対数正規分布であり、 対数正規分布は SICX$(sp)$ であり、 SICX である。
$N(\mu, \sigma^{2})$$u(x)$

を $x$ の $P$ -convex 関数とすれば、 $w(y)\equiv u(e^{y})$ は、 $w(\lambda\log a+(1-\lambda)\log b)=$$u(e^{\lambda\log a+(1-\lambda)\log b})\leq\lambda u(e^{\log a})+(1-\lambda)u(e^{\log b})=\lambda w(a)+(1-\lambda)w(b)$なので、$y$の凸$(\log t-\log s)^{2}$関数である。 いっぽう、 $X(s)$ を密度関数が$f_{S}(t)= \frac{1}{\sqrt{2\pi}\sigma t}e^{-}\overline{2\sigma^{l}}=\frac{\phi_{\log s,\sigma^{2}}(1\circ gt)}{t}$を正規分布の対数正規分布関数とする。 ここで、$Y(s)$ を正規分布 $N(s, \sigma^{2})$ にしたがう関数列とする。 このとき、$N(\mu, \sigma^{2})$$\phi_{\mu,\sigma^{2}}(x)$の密度関数とし、$E[u(X(a^{\lambda}b^{1-\lambda}))] = \int_{-\infty}^{\infty}\phi_{\lambda\log a-(1-\lambda)\log b,\sigma^{2}}(x)w(x)dx$となる。 ところで、 $\{Y(s)\}$ は SICX より、 $E[u(X(a^{\lambda}b^{1-\lambda}))]=E[w(Y(\lambda\log a-(1-$$\lambda)\log b))]\leq\lambda E[w(Y(\log a))]+(1-\lambda)E[w(Y(\log b))]$ となる。ここで、 $E[w(Y(\loga))]=$$E[u(X(a))]$ および $E[w(Y(\log b))]=E[u(X(b))]$ である。 よって、 $E[u(X(a^{\lambda}b^{1-\lambda}))]\leq$の $P$ -convex 関数である。
$\lambda E[u(X(a))]+(1-\lambda)E[u(X(b))]$ となる。 $E[u(X(s))]$ は$x$

定義 1 $u(s)$ を任意の増加 $P$ -convex( $P$-concave) 関数とする。 $E[u(X(s))]$ が の増加$P$-convex ( $P$-concave) 関数となるとき、 $\{X(s)\}_{s\in(0,\infty)}$ を SIPCX(SIPCV) という$s$$\circ$(stochastically increasing and

3.1$P$-convex $(P$-concave))

Partial Maintenance を考慮した多段決定問題 II

状態がマルコフ過程にしたがって推移し、 推移法則を $P=(p_{s}(t))_{s,t\in(0,\infty)}$ とする。 各とする。 このとき、 計画期間が で、 状態が のとき、 最小化問
期ごとの決定を題 (最大化問題) において、 最適に振る舞って得られる総期待損失 (総期待利得) を $w_{n}(s)$$\alpha\geq 1$$n$$s$

197とすれば、 状態がマルコフ過程にしたがって推移するから、 最適方程式はつぎのようになる。 ここで、 $E[v_{n-1}(T(s))]= \int_{0}^{\infty}p_{s}(t)v_{n-1}(t)dt$ である。

(I) 最小化問題$v_{n}(s) = \min_{\alpha\geq 1}\{C(\alpha)+E[v_{n-1}(T(\alpha \mathcal{S}))]\}$

(5)

,

ここで、
$v_{1}(s)= \min_{\alpha\geq 1}\{C(\alpha)+E[u(T(\alpha s))]\}$とする。 ただし、 $u(s)$ は$s$の減少関数とし、$C(\alpha)$は$\alpha$の増加関数とする。 ただし、 $u(s)$が $P$ -concave となる問題を考えるときは、 $C(\alpha)$ は $P$ -concave とする。

(II) 最大化問題$v_{n}(s) = \max_{\alpha\geq 1}\{-C(\alpha)+E[v_{n-1}(T(\alpha s))]\}$(6),

ここで、$v_{1}(s)= \max_{\alpha\geq 1}\{-C(\alpha)+E[u(T(\alpha s))]\}$とする。 ただし、 $u(s)$ は$s$の増加関数とし、$C(\alpha)$は$\alpha$の増加関数とする。 また、 $u(s)$が $P$ -convex となる問題を考えるときは、 $C(\alpha)$ は $P$ -convex とする。

補題 14 (最小化問題) $v_{n}(s)$ は、$s$に関する減少関数である。

補題 15 (最大化問題) $v_{n}(s)$ は、$s$に関する増加関数である。

$T(s)$ を状態が $s$ のときつぎの状態を表す確率変数とする。 推移法則が $(p_{s}(t))_{0\leq s\leq 1}$ だから、 確率変数列 $\{T(s)|s\in(0, \infty)\}$ に対して、 つぎの仮定を設ける。 これらの仮定は、$u(s)$ が $P$-convex のときは仮定 1 のもとで議論し、 $u(s)$ が -concave のときは仮定 2 の$P$もとで議論できる。

に関する増加 $P$ -convex 関数を $u(t)$ とすれば、 $E[u(T(s))]$ は関する増加 $P$-convex 関数となっている。 すなわち、 確率変数列 $\{T(s)|s\in(0, \infty)\}$ は、

仮定 1 ( $P$ -convex)$s\}_{\vec{\sim}}$$t$

SIPCX である。
仮定 2 ( $P$ -concave) に関する増加 $P$ -concave 関数を $u(t)$ とすれば、 $E[u(T(s))]$ はに関する増加 $P$ -concave 関数となっている。 すなわち、 確率変数列 $\{T(s)|\mathcal{S}\in(0, \infty)\}$

$s$

$t$

は、 SIPCV である。

補題 16 (最小化問題) 仮定 1 のもとで、 $u(s)$ が $P$-convex ならば、 $v_{n}(s)$ は $P$-convex では増加関数とする。 また、 仮定 2 のもとで、 $u(s)$ が $P$ -concave なある。 ただし、は $P$ -concaveは増加関数とし、らば、 $v_{n}(s)$ は $P$ -concave である。 ただし、$C(\alpha)$$C(\alpha)$$C(\alpha)$とする。

補題 17 (最大化問題) 仮定 1 のもとで、 $u(s)$ が $P$-convex ならば、 $v_{n}(s)$ は $P$-convex では $P$ -convex とする。 また、 仮定 2 のもとは増加関数とし、ある。 ただし、は増加関数
で、 $u(s)$ が $P$ -concave ならば、 $v_{n}(s)$ は $P$-concave である。 ただし、$C(\alpha)$$C(\alpha)$$C(\alpha)$とする。

198
計画期間が$n$であり、 状態が$s$のときの、 最適な決定を$\alpha_{n}^{*}(s)$とする。

性質 1(最小化問題) 仮定 1 のもとで、 $u(s)$ が -convex ならば、減少する。 また、 仮定 2 のもとで、 $u(s)$ が -concuve ならば、
$P$

$P$

は$\alpha_{n}^{*}(s)$は$\alpha_{n}^{*}(s)$$s$に関してに関して増加$s$する。

性質 2 (最大化問題) 仮定 2 のもとで、 $u(s)$ が $P$ -concave ならば、減少する。 また、 仮定 1 のもとで、 $u(s)$ が $P$-convex ならば、は$\alpha_{n}^{*}(s)$$\alpha_{n}^{*}(s)$は$s$に関してに関して増加$s$する。

仮定 3 ( $P$-convex) $S’\geq S$ のとき任意の $P$-convex 関数 $u(s)$ に対して、 $E[u(T(s’))]-$$E[u(T(s))]\geq u(s’)-u(s)$ である。

仮定 4 ( $P$ -concave) $s’\geq s$ のとき任意の $P$-concave 関数 $u(s)$ に対して、 $E[u(T(s’))]-$$E[u(T(s))]\leq u(s’)-u(s)$ である。

性質 3 (最小化問題) 仮定 3 のもとで、 $u(s)$ が $P$-convex ならば、減少する。 また、 仮定 4 のもとで、 $u(s)$ が $P$-concave ならば、$\alpha_{n}(s)$$\alpha_{n}(s)$は $n$ に関しては $n$ に関して増加する。

性質 4 (最大化問題) 仮定 3 のもとで、 $u(s)$ が $P$-convex ならば、増加する。 また、 仮定 4 のもとで、 $u(s)$ が$P$-concave ならば、$\alpha_{n}(s)$$\alpha_{n}(s)$は $n$ に関しては $n$ に関して減少する。

注 1 状態空間を $(0, \infty)$ とし、 状態を表す値 が大きくなれば状態が悪くなるとする。
このときつぎのような問題を考える。 状態が のとき、 決定 を取れば、 新しい状態を$s$$s$

その費用を$\alpha$とし、 $u(s)$ を最後の期の状態がのときの終端費用とする。 計画期間が で状態が のとき、 最適に振る舞ったときの総期待費用を$v_{n}(s)$ とすれば、 状態がマルコフ過程にしたがって推移するから、 最適方程式はつぎの$\alpha s$とでき$(0<\alpha\leq 1)_{\backslash }$$n$$C(\alpha)$$s$$s$

ようになる。

$v_{n}(s) = \min_{0<\alpha\leq 1}\{C(\alpha)+E[v_{n-1}(T(\alpha s))]\}$

,

(7)

ここで、
$v_{1}(s)= \min\{C(\alpha)+E[u(T(\alpha s))]\}$$0<\alpha\leq 1$とする。 ただし、 $u(s)$ は$s$の増加関数とし、$C(\alpha)$は$\alpha$の減少関数とする。 この場合にも同様の性質を求めることができる。 また、 最大化問題としても同様である。 (京都大学

数理解析研究所講究録 「不確実性下における意思決定問題」 , vol. 1734, 220-227 参照)

参考文献[1] Albright, S. ., Structural results for partially observable Markov decision processes. Oper. Res. 27 (1979), 1041-1053.
$C$

199
[2] Grosfeld-Nir, A.,
two-state partially observable Markov decision process withuniformly distributed observations. Oper. Res. 44 (1996), 458-463.
$A$[3] Itoh, H. and Nakamura, K., Partially observable Markov decision processes withimprecise parameters. Artificial Intelligence 171 (2007), 453-490.
[4] M. Kijima and M. Ohnishi: Stochastic Orders and Their Applications in Financial
optimization, Math. Methods of Oper. Res., 50, 351-372, (1999).

[5] G. E. Monahan: Optimal selection with alternative information. Naval Res. Logist. Quart. 33 (1986), 293-307.
[6] T. Nakai, A Sequential Decision Problem based on the Rate Depending on aMarkov Process, Recent Advances in Stochastic Operations Research 2 (Eds. $T.$Dohi, S. Osaki and K. Sawaki), World Scientific Publishing, 11-30, 2009.
[7] T. Nakai, Sequential Decision Problem with Partial Maintenance on a PartiallyObservable Markov Process, Scientiae Mathematicae Japonicae, vol. 72, no. 1,

11-20, 2010.
[S] Ohnishi, M., Kawai, H. and Mine, H., An optimal inspection and replacement
policy under incomplete state information. European J. Oper. Res. 27 (1986),117-128.
[9] Shaked, M. and Shanthikumar, J. ., Stochastic Orders and Their Applicati $ons$(Probability and mathematical statistics: a series of monographs and textbooks),
Academic Press, Boston, Massachusetts, 1994.
$G$[10] White, D. J. Structural properties for contracting state partially observable
Markov decision processes. J. Math. Anal. Appl. 186 (1994), 486-503