数理解析研究所講究録 1207 巻 2001 年 79-100

79
確率最適化における過去集積値と未来閾値について
九大大学院経済学研究科

植野貴之 (Takayuki Ueno)

Graduate School of Economics, Kyushu University
九大大学院経済学研究院

岩本誠一 (Seiicbi Iwamoto)

Faculty of Econoniics, Kyushu University

1

はじめに

本論文では、 不確実性の下で多段階にわたる加法型 (総合) 評価値が所定の基準値以上になる (閾値) 確率を最適化する問題を考える。 2 種類の(1) 過去集積値に基づく (2) 未来-

閾値に基づく一拡大マルコフ政策を導入して、 それぞれのクラスでの最適政策を求める。 さらに、 両政策の間に双対性および一致性が成り立っことを示す。 期待値最適化問題では、 最適政策はマルコフ政策クラスの中に存在することがわかっているが、 閾値確率最適化問題では一般にマルコフ政策は十分でなく、 広く一般政策クラスに最適政策が存在することを示す。

2

閾値確率制御問題
以下、 本論文で用いる記号と用語を述べておこう。

(1)$N\geq 2$(2)$X=\{s_{1}, s_{2}, \ldots, s_{p}\}$は有限状態空間 (state space)(3)$U=\{a_{1} , a_{2}\ldots., a_{k}.\}$

は有限決定空間 (action space).

(4)は段の総数 (total number of stage) を表す正整数: $X\cross Uarrow R^{1}$ は第$r_{n}’$; $r_{n}(x.u)$ は第

$n$

’

$n$

利得関数 ( -th reward function)
$n$

期に状態

$x$

で決定

$u$

$(0\leq n\leq N-1)$をとったとき、 システムから得られる

利得 (リターン) を表す。

$\backslash _{\iota}\cdot$: $Xarrow R^{1}$ は終端利得関数 (terminal reward function)$r_{N}$; $r_{N}(x)$ は最終 $N$ 期に状態$x$になったとき、 システムから得られる終端利得を

表す。

(5)

$p=\{p(y|x, u)\}$:はマノレコフ推移法貝り (Markov transition law)$p(y|x.u)\geq 0$$\sum_{y\in X}p.(y|x, u)=1$;$p(y|x_{\backslash }u)$が$\sim$$y$$\forall(.x., v, y)\subset-X\cross U\cross X$$\forall(.’\iota\cdot, u)\in X\cross U$は現在状態$\tilde{X}$が$x$

で現在の決定(こなる条・件付き確率を表す : $P$ ($\tilde{U}$$\tilde{\mathrm{Y}}=y|\tilde{X}$は確率変数を表す。 この確率的推移を

が

$u$

—x.,

になったとき、 次の状態$\tilde{U}=u$$\tilde{\mathrm{Y}}\sim p(\cdot|x, \cdot u)$$\tilde{\mathrm{Y}}$) $=p(y|x, u)$ . ただしで表現する。

80(6)は 7J レコフ政策 (Markov policy)$\pi=\{\pi_{0}, \pi_{1}, \ldots, \pi_{N-1}\}$: $Xarrow U$: X\rightarrow U》.. . ,を経てきたとき、意志決定者は途中の状, .. . ,第 段までに状態列を取ることを表している。
に無関係に決定態列, .. . ,:: $Xarrow U$,$\pi_{0}$$\pi_{N-1}$$\pi_{1}$$n$$x_{0},$$x_{0},$$x_{n}$$x_{1}$$\pi_{n}(x_{n})\in U$$x_{n-1}$$x_{1}$

マルコフ政策の全体を 兇派修 。

(6)’は一般政策 (general policy)$\sigma=\{\sigma_{0}, \sigma_{1}, \ldots, \sigma_{N-1}\}$:: XxX\rightarrow U フ. . . ,を観察したとき、意志決定者は決定, .. . ,第 段までに状態列を取ることを表している。 一般政策の全体を (g):$\sigma_{0}$: $Xarrow U$,$\sigma_{N-1}$$\sigma_{1}$$n$$x_{0},$$X\cross\cdots\cross Xarrow U$$x_{n}$$x_{1}$$\sigma_{n}(x_{0},x_{1}, \ldots, x_{n})\in U$

で表す。

(6)”

{崗,

$\mu=$$\mu_{1},$} は原始政策 (primitive policy), . ..
:$\mu_{N-1}$$\ldots,$: 崗: $Xarrow U$,$\mu_{1}$$X\cross U\cross Xarrow U$

,
第

$n$

$\mu_{N-1}$:$X\cross U\cross X\cross U\mathrm{x}\cdots \mathrm{x}U\mathrm{x}Xarrow U$

段までに状態と決定の交互列$x_{0},$

きたとき、意志決定者は途中の決定列
決定 \sigma n(x0, 拘,$x_{1},u_{1},$ $\ldots,$ $u_{n-1},$ $x_{n}$政策の全体をで表す。

$\text{ }(p)$$u_{0},$$u_{0},$$x_{1},$$u_{1}$$u_{1}$, . . .,, .. . ,$u_{n-1},$$u_{n-1}$$x_{n}$を経てにも依存して) $\in U$ を取ることを表している。 原始

いま、 ある $N$ 段システムが、初期 (第 0 段) 状態 $X0\in X$ から出発して制御マルコフ推移法
則 $p=\{p(y|x,u)\}$ に従って推移し、決定と状態の交互列$u_{0}\in U,$$x_{1}\in X,$$u_{1}\in U,$$x_{2}\in X$, ... , $u_{N-1}\in U$

を経て、最終的にある確率で $x_{N}\in X$ になり、 そこで終了するとする。 このとき、 第 0 段ではにとが得られ、 第 1 段ではに依存した利得 (リターン)と決定状態が得られ、以下、第 段では利得 r、$(x_{n}, *)$ が得られ、最終の第 $N$ 段
関係した利得に依存した終端利得 $r_{N}(x_{N})$ が得られるとする。 すなわち、終了時点には、 さらに終端状態$r_{0}(x_{0},u_{0})$$u_{0}$$x_{0}$$r_{1}(x_{1},u_{1})$$x_{1}$$u_{1}$$n$$x_{N}$

意志決定者はシステム全体を通じては各段で得られた利得の総和$r_{0}(x_{0},u_{0})+r_{1}(x_{1},u_{1})+\cdots+r_{N-1}(x_{N-1}, u_{N-1})+r_{N}(x_{N})$を得るものとする。 不確実な状況の下でこの総和があらかじめ定められた (所定の) 値 以上になる確率を最大にするように行動するには、意志決定者が各段で、 それまでの状態に応じてどのように決定を取っていけばよいかが問題である。 一般に、第 期の状態と決定をそれぞれで表わすと、得られる総利得は確率変数
確率変数
$c$

$n$

$X_{n},$$U_{n}$$r_{0}(X_{0}, U_{0})+r_{1}(X_{1}, U_{1})+\cdots+r_{N-1}(X_{N-1}, U_{N-1})+r_{N}(X_{N})$で表わされる。 総利得を表わす確率変数を以後簡単に$r_{0}+r_{1}+\cdots+r_{N-1}+r_{N}$81で表す。 したがって、 問題を数学的に記述すると、 次の閾値確率最大化問題になる :Maximize $P_{x_{0}}^{\sigma}(r_{0}+r_{1}+\cdots+r_{N-1}+r_{N}\geq c)$
subject to (i)$X_{n+1}\sim p(\cdot|x_{n},u_{n})$$\mathrm{P}_{0}(x_{0})$

(ii)
ただし

$P_{x0}^{\sigma}$

は、 初期状態$x_{0}$$n=0,1,$$u_{n}\in U$, マルコフ推移法則$p$

およひ一\Re 政策$H_{N}=X\cross U\cross X\cross U\cdots\cross U\cross X(2N+1)$$\sigma$$\ldots,$$N-1$

から履歴の直積空間個上に唯一定まる確率測度である。 また、 この確率測度にょる期待値作用素を

3(1)$E_{x_{0}}^{\sigma}$で表す。

一般政策クラス問題

この節では、 次のような決定列の選択方法を考える。 すなゎち、 与えられた初期 (第 0 段)
状態
を観て、 まず決定 $u_{0}\in U$ を選択する。 次に、 マルコフ推移法則
に従って確率的に第 1 段状態が出現する。 このとき、 これまでの二っ状態に依存して第 1 段の決定を取る。 第 2 段には確率 $p(x_{2}|x_{1}, u_{1})$ で状態になる。 このように決定列を選んでいって、 第 $(N-1)$ 段には確率 $p(x_{N-1}|x_{N-2}, u_{N-\mathit{2}})$ で状態 $x_{N-1}$ になったとき、 これまでの状
態列, . . ., $x_{N-1}$ を考慮して決定 $u_{N-1}$ を選び、 最終的に推移法則 $p(\cdot|x_{N-1},u_{N-1})$ に従って状態が現れる。 このとき、 第 0 段での決定の選択方法は関数: $Xarrow U$ で指示される。 第 1 段での選択方法は関数: $X\cross Xarrow U$ で指示され、 一般に、 第 段では関数: $X\cross X\cross\cdots\cross Xarrow U$ で示される。 関数
を第 一般決定関数という。 一般決定関数列$x_{0}$$p(\cdot|x_{0}, u_{0})$$x_{1}$$x_{0},$ $x_{1}$$u_{1}$$x_{0},$$x_{2}$$x_{1}$$x_{N}$$\sigma_{0}$$\sigma_{1}$$n$$\sigma_{n}$$\sigma_{n}$$n$$\sigma=\{\sigma_{0}, \sigma_{1}, \ldots, \sigma_{N-1}\}$

を一般政策という。 一般政策
は、 それまでの状態列の出現に応じて意志決定者の決定を指定する。 すなわち、 第 段までに状態列, ... ,を経てきたとき、 意志決定者は決定$\sigma$$n$$x_{0},$$x_{1}$$x_{n}$を取ることを表してぃる。
したがって、 意志決定者が一般政策を採用すると、 最大化問題 (1) の閾値確率は 「部分」$\sigma_{n}(x_{0}, x_{1}, \ldots, x_{n})\in U$$\sigma$

多重和$P_{x_{0}}^{\sigma}(r_{0}+r_{1}+\cdots+r_{N-1}+r_{N}\geq c)$(2)$= \sum_{(x_{1},x_{2}},\sum\ldots,\cdot\cdot\sum_{x_{N})\in(*)}p(x_{1}|x_{0}, u_{0})p(x_{2}|x_{1}, u_{1})\cdots p(x_{N}|x_{N-1}, u_{N-1})$で表される。 ただし、 多重和をとる領域 $(*)$ は$r_{0}(x_{0}, u_{0})+r_{1}(x_{1}, u_{1})+\cdots+r_{N-1}(x_{N-1},u_{N-1})+r_{N}(x_{N})$$\geq$$c$(3)を満たす $(x_{1}, x_{2}, \ldots, x_{N})\in X\cross X\cross\cdots\cross X$ 全体にわたる多重和である。 ここに、 式 (2) $,(3)$ における決定列 $\{u_{0}, u_{1}, \cdots, u_{N-1}\}$ は一般政策を通して定まってぃることに注意すべきである :$\sigma--\{\sigma_{0}, \ldots, \sigma_{N-1}\}$$u_{0}=\sigma_{0}(x_{0}),$$u_{1}=\sigma_{0}(x_{0},x_{1})$, . .. , $u_{N-1}=\sigma_{0}(x_{0}, x_{1}, \ldots, x_{N-1})$ .

82
を選ぶ問題
を明示して、 一般政策
原問題 ( では、 逐次制約条件 (i), (ii) 0としてダイナミックに表現している。 しかし、 実質的に同じことであるが、 一般政策全体 (g)$\ovalbox{\tt\small REJECT} n\ovalbox{\tt\small REJECT} N-1$$\mathfrak{y}$$\sigma$

上の最大化としてスタティックにMaximize$\mathrm{P}_{0}(x_{0})$subject to$P_{x_{0}}^{\sigma}(r_{0}+\cdots+r_{N-1}+r_{N}\geq c)$$\sigma\in\Pi(g)$で表すこともできることに注意しよう。
さて、 われわれの求める最適解は問題 (1) の最大値関数 $v_{0}=v_{0}(x_{0})$ および最大値を与える最
である :
適政策
$\sigma^{*}$$=$$v_{0}(x_{0})$$=$$P_{x_{0}}^{\sigma^{*}}(r_{0}+\cdots+r_{N-1}+r_{N}\geq c)$$x_{0}\in X$$\sigma\in\Pi(g){\rm Max} P_{x_{0}}^{\sigma}(r_{0}+\cdots+r_{N-1}+r_{N}\geq c)$.

この問題を一般政策クラス問題、 または短く一般問題と呼ぶ。
次節では一般問題を等価な問題に変換して上記の最適解を求める。 そのため、 閾値確率を期待値に変換しておこう。
が 以上になる確率
上の区間 $[c, \infty)$ の定義
は、 数直線
一般に、 確率変数関数$\mathrm{Y}$$\psi(y):=1_{[\mathrm{c},\infty)}(y):=\{$

を通した確率変数$\psi(\mathrm{Y})$$R^{1}$$P(\mathrm{Y}\geq c)$

$c$

の期待値

$E[\psi(\mathrm{Y})]$1$y\geq c$0

そ\emptyset 他で表される :

$P(\mathrm{Y}\geq c)=E[\psi(\mathrm{Y})]$.

このことに注意すると、一般問題 (1) の閾値確率は定義関数 $\psi=\psi(y)$ を通した期待値になる :$P_{x_{0}}^{\sigma}(r_{0}+\cdots+r_{N-1}+r_{N}\geq c)$$=$$E_{x_{0}}^{\sigma}[\psi(r_{0}+\cdots+r_{N-1}+r_{N})]$.

すなわち、「部分」 多重和は定義関数を通した 「全」 多重和に等しい :$= \Sigma’\Sigma\cdots.\sum_{X(x,\mathrm{x}X\mathrm{x}\cdots\cross \mathrm{x}_{\cross p(x_{1}|0,0)p(x_{2}|x_{1},u_{1})\cdots p(x_{N}|x_{N-1},u_{N-1})\}}}^{|x_{0},u_{0})p(x_{2}|x_{1},u_{1})\cdots p(x_{N}|x_{N-1},u_{N-1})}(x1\sum_{x_{2}}\sum_{x_{N},\prime\prime}\cdot\cdot\sum_{\in 1x_{2},\ldots\prime x_{N})}p(x_{1})\in(*)\{\psi(r\mathrm{o}(x0,u\mathrm{o})+\cdots+r_{N1}-(x_{N1}-,u_{N-1})+r_{N}(x_{N}))xu$.

4

拡大マルコフ政策クラス問題 I
前節の議論により、「閾値確率」 最大化問題は次の 「期待値」 最大化問題になる :Maximizesubject to$E_{x_{0}}^{\sigma}[\psi(r_{0}+r_{1}+\cdots+r_{N-1}+r_{N})]$$(\mathrm{i})_{n}X_{n+1}\sim p(\cdot|x_{n},u_{n})$$n=0,1,$$\ldots,$$N-1$$(\mathrm{i}\mathrm{i})_{n}u_{n}\in U$

これはダイナミックに表されているが、 スタティックにはMaximize$E_{x_{0}}^{\sigma}[\psi(r_{0}+r_{1}+\cdots+r_{N-1}+r_{N})]$subject to$\sigma\in\Pi(g)$83で表される。
この問題を、 新たに過去値をパラメータとする問題に埋め込んで考える。 まず、 第 段までの集積値確率変数列
およびそれらが取り得る過去値集合列をそれぞれ次で定義す$n$$\{\tilde{\Lambda}_{n}\}$$\{\Lambda_{n}\}$る [6-8, 11-13]:$\tilde{\Lambda}_{0}$$\tilde{\Lambda}_{n}$$\Lambda_{0}$$\Lambda_{n}$$=0\triangle$$n=1,$$=r_{0}(X_{0}, U_{0})\triangle+\cdots+r_{n-1}(X_{n-1}, U_{n-1})$$\ldots,$

(4)

$N$

$=\{0\}\triangle$$=\triangle\{\lambda_{n}|\lambda_{n}=r_{0}(x_{0},u_{0})+\cdots+r_{n-1}(x_{n-1}, u_{n-1})$,$(x_{0}, u_{0}, \ldots, x_{n-1}, u_{n-1})\in X\cross U\cross\cdots\cross X\cross U\}$$n=1,$$\ldots,$$N$

このとき、 総利得は次になる :$r_{0}+r_{1}+\cdots+r_{N-1}+r_{N}=\tilde{\Lambda}_{N}+r_{N}$.

式 (4) は漸化式$=0$$\tilde{\Lambda}_{0}$$n=0,$$=\tilde{\Lambda}_{n}+r_{n}(X_{n}, U_{n})$$\tilde{\Lambda}_{n+1}$に同値である。 また、 相隣る過去値集合$\{\Lambda_{n-1}, \Lambda_{n}\}$$\ldots,$$N-1$

間には次の前向き再帰式が成り立っ :補題 4.1$\Lambda_{0}=\{0\}$$n=1,2,$$\Lambda_{n}=\{\lambda+r_{n-1}(x, u)|\lambda\in\Lambda_{n-1}, (x, u)\in X\cross U\}$

さらに、 本来の状態空間 $X$ に過去値集合を貼り合せた拡大状態空間列$\ldots,$$N$$\{\mathrm{Y}_{n}\}$.

を直積で定義する :$n=0,1,$$=X\cross\Lambda_{n}\triangle$$\mathrm{Y}_{n}$この新状態空間列上のマルコフ政策$\gamma_{n}$:$\gamma=\{\gamma_{0}, \gamma_{1}, \ldots, \gamma_{N-1}\}$,$\mathrm{Y}_{n}arrow U$$\ldots,$$N$.

はマルコフ決定関数列$(n=1,2, . . . , N)$で定まる。 これを過去値による拡大マルコフ政策といい、 その全体を得関数 $T$ を$T(x;\lambda)=\psi(\lambda\triangle+r_{N}(x))$

兇派修 。
新たに終端利$(x;\lambda)\in \mathrm{Y}_{N}$で定義する。 さらに、 定常マルコフ推移法則 $p=\{p(y|x, u)\}$ およびパラメータ・ダイナミックス$\{\lambda_{n+1}=\lambda_{n}+r_{n}(x_{n}, u_{n})\}$$q=\{q_{n}\}$によって拡大状態空間列上に定まる非定常マルコフ推移法則

を$p(y|x, u)$$q_{n}((y;\mu)|(x;\lambda), u)=\triangle\{$0$\lambda+r_{n-1}(x, u)=\mu\sigma)$

その他.

とき

84
で定義する。 このとき、 拡大マルコフ政策空間上の終端型評価問題

Maximizesubject to$\mathrm{Q}_{0}(y_{0})$5$[\psi(\tilde{\Lambda}_{N}+r_{N}(X_{N})]$$(\mathrm{i})_{n}X_{n+1}\sim p(\cdot|x_{n},u_{n})$$(\mathrm{i})_{n}’\tilde{\Lambda}_{n+1}=\tilde{\Lambda}_{n}+r_{n}(X_{n}, U_{n})$$n=0,1,$$\ldots,$$N-1$$(\mathrm{i}\mathrm{i})_{n}u_{n}\in U$

を考える。 ただし、 $y0=(x_{0};0)$ . ここには、 初期状態、拡大マルコフ政策 および新マルコフ推移法則 によって拡大状態空間列上に定まる確率測度に基づく期待値作用素である ([10])。
さて、 第 段の状態
から始まる部分過程$y0$$\tilde{E}_{y0}^{\gamma}$$\gamma$$\tilde{P}_{y0}^{\gamma}$$q$$y_{n}=(x_{n};\lambda_{n})(\in \mathrm{Y}_{n}.)$$n$$\mathrm{Q}_{n}(y_{n})$Maximizesubject to$\tilde{E}_{y_{n}}^{\gamma}[\psi(\tilde{\Lambda}_{N}+r_{N}(X_{N})]$$(\mathrm{i})_{n}X_{m+1}\sim p(\cdot|x_{m},u_{m})$$(\mathrm{i})_{n}’\tilde{\Lambda}_{m+1}=\tilde{\Lambda}_{m}+r_{m}(X_{m}, U_{m})$$m=n,$$\ldots,$$N-1$$(\mathrm{i}\mathrm{i})_{n}u_{m}\in U$の最大値を$u^{n}(x_{n};\lambda_{n})$とする。 ただし$u^{N}(x_{N};\lambda_{N})=\psi(\lambda_{N}\triangle+r_{N}(x_{N}))$$(x_{N};\lambda_{N})\in \mathrm{Y}_{N}$.

このとき、 次の後向きの再帰式が成り立つ :定理 4.1$u^{N}(x;\lambda)$$u^{n}(x;\lambda)$$x\in X,$$=\psi(\lambda+r_{N}(x))$$\lambda\in\Lambda_{N}$(5)$={\rm Max} \sum_{y\in X}u^{n+1}(y;\lambda+r_{n}(x,u))p(y|x, u)u\in U$$x\in X,$$\lambda\in\Lambda_{n}$,$0\leq n\leq N-1$ .

さて、 式 (5) の最大 (値を与える) 点の全体をとすると、 拡大マルコフ政策クラス
か兇涼罎任虜播 政策が得られる ([10, Theorem 42])。 さらに、
ら、以下のように一般政策を生成する。 すなわち、$\gamma_{n}^{*}(x;\lambda)$$\gamma^{*}=\{\gamma_{0}^{*}, \gamma_{1}^{*}, \ldots, \gamma_{N-1}^{*}\}$$\gamma^{*}$$\sigma_{n}^{*}(x_{0}, x_{1}, \ldots, x_{n})$$\sigma^{*}=\{\sigma_{0}^{*}, \sigma_{1}^{*}, \ldots, \sigma_{N-1}^{*}\}$

は$u_{0}:=\gamma_{1}^{*}(x_{0};0)$,$u_{1}:=\gamma_{1}^{*}(x_{1};\lambda_{1}.\cdot.)$$\lambda_{1}:=0+r(x_{0}, u_{0})$,$\lambda_{2}:=\lambda_{1}+r(x_{1},u_{1})$$u_{n-1}:=\gamma_{n-1}^{*}(x_{n-1}; \lambda_{n-1})$,$\lambda_{n}:=\lambda_{n-1}+r(x_{n-1}, u_{n-1})$$\sigma_{n}^{*}(x_{0}, x_{1}, \ldots, x_{n}):=\gamma_{n}^{*}(x_{n};\lambda_{n})$.

このとき、 次が成り立つ :定理 4.2(, Iheorem 6.1])
は一般政策クラス(i) 政策$[\mathrm{J}\theta$の中での最適である。
(ii) 拡大マルコフ政策クラス 兇虜蚤臙佑楼貳明 策クラス (g) の最大値に等しい :$\sigma^{*}$$\text{ }(g)$$u^{0}(x_{0;}0)=v_{0}(x_{0})$

.

85
5

拡大マルコフクラス問題 II

この節では、 与えられた水準値 を固定して、 もう 1 つの拡大マルコフ政策クラスの中で最適化しても最適政策が得られることを示す。 このマルコフクラス上の閾値確率最大化問題は$c$

Maximizesubject to$\mathrm{M}_{0}(x_{0})$$P_{x_{0}}^{\tau}(r_{0}+r_{1}+\cdots+r_{N-1}+r_{N}\geq c)$$(\mathrm{i})_{n}X_{n+1}\sim p(\cdot|x_{n}, u_{n})$$n=0,1,$$\ldots$, ヤー 1(6)$(\mathrm{i}\mathrm{i})_{n}u_{n}\in U$で表される。 この問題では、 マルコフ的に推移する本来の状態変数に加えて、 新たに導入する将来の閾値
が所与の閾値 $c_{0}=c$ から時間と共に確定的に変化すると、 捉える。 すなわ
ち、 対 (;c\mapsto を新状態変数とし、 その新たなマルコフ推移のもとで所与の閾値確率を最小化をする。 そのため、 まずここで、 未来閾値集合列$X_{n}$$c_{n}$$X_{n}$$\{C_{n}\}$$C_{0}$$=\triangle\{c_{0}|c_{0}=c\}$$=\triangle$$C_{n}${ら$|$$c_{n}=c-r_{0}(x_{0},u_{0})-\cdots-r_{n-1}(x_{n-1}, u_{n-1})(x_{0},u_{0},\ldots,x_{n-1}, u_{n-1})\in X\cross U\cross\cdots\cross X\cross U\}$$n=1,$

は未来の時刻で導入しておく。
は次の前向きの再帰式を満たす :$C_{n}$$n$$\ldots,$$N$

での可能な閾値の集合を表している。 このとき、列$\{C_{n}\}$補題 5.1$C_{0}$$=$$\{c\}$$C_{n+1}$$=$$\{c-r(x, u)|c\in C_{n}, (x, u)\in X\cross U\}$

$0\leq n\leq N-1$ .

したがって、 時刻

で「拡大」 状態 $(x_{n};c_{n})$ において意思決定者が決定を選ぶと、 次の時刻 $(n+1)$ では $(x_{n+1}; c_{n+1})$ に確率 $p(x_{n+1}|x_{n}, u_{n})$ で推移する。 ただし、 第 2 成分は確定的(こ定まる : $c_{n+1}:=c_{n}-r(x_{n}, u_{n})$ .
このとき、 決定関数$n$$u_{n}$$\tau_{n}$: $X\cross C_{n}arrow U$$0\leq n\leq N-1$から成る列 $\tau=\{\tau_{0}, \ldots, \tau_{N-1}\}$ を未来 (閾) 値による 「拡大 マルコフ政策という。 この拡大
マルコフ政策の全体をで表す。 意思決定者が拡大マルコフ政策を採用すると、 最$\mathrm{j}$$\text{ }-$$\tau(\in\text{ })-$

大化問題 (6) の閾値確率は 「部分」 多重和$P_{x_{0}}^{\tau}(r_{0}+r_{1}+\cdots+r_{N-1}+r_{N}\geq c)$$= \sum_{(x_{1},x_{2}},\sum\ldots,\cdot\cdot\sum_{x_{N})\in(*)}p(x_{1}|x_{0}, u_{0})p(x_{2}|x_{1}, u_{1})\cdots p(x_{N}|x_{N-1}, u_{N-1})$(7)で表される。 ただし、 多重和をとる領域 $(*)$ は$r_{0}(x_{0}, u_{0})+r_{1}(x_{1}, u_{1})+\cdots+r_{N-1}(x_{N-1},u_{N-1})+r_{N}(x_{N})$$\geq$

$c$

(8)

86
全体にわたる多重和である。 ここに、 式 (7) $,(8)$ におを満たす
ける決定列 $\{u_{0}, u,, \cdots, u_{N-1}\}$ はマルコフ政策 の決定関数列を通して定まっていることに$(x,, x_{2}, \ldots, x_{N})\mathrm{C}X\cross X\cross\cdot\cdot \mathrm{x}X$$\tau$

注意すべきである$\ovalbox{\tt\small REJECT}$$u_{1}=\tau_{1}(x_{1};c_{1})$$u_{0}=\tau_{0}(x_{0};c_{0}),$, . . . , $u_{N-1}=\tau_{N-1}(x_{N-1}; c_{N-1})$ .

このとき、 次の関係式を得る。

補題 52 任意のマルコフ政策$P_{x_{n}}^{\tau}$と任意の $(x_{n};x_{n})\in X\cross C_{n}$ に対して、$\tau=.\{\tau_{n}, \tau_{n+1}, \ldots, \tau_{N-1}\}$( $r_{n}+\cdots+r_{N}\geq$ ら)$=x_{n+1} \in X\sum P_{x_{n+1}}^{\tau’}(r_{n+1}+\cdots+r_{N}\geq c_{n}-r_{n})p(x_{n+1}|x_{n}, u_{n})$が成り立つ。 ここに$r_{n}=r(x_{n}, u_{n})$,$u_{n}=\tau_{n}$($x_{n}$; ら),$\tau’=\{\tau_{n+1}, \ldots, \tau_{N-1}\}$.

補題 52 を多重和で表すと、 次になる。
補題 5.3 任意のマルコフ政策と任意の $x_{n}\in X$ に対して、$\tau=\{\tau_{n}, \tau_{n+1}, \ldots, \tau_{N-1}\}$$\sum_{(x_{n+1},x}\sum_{n+2,}\cdot..\cdot.,\cdot\sum_{x_{N}}p_{n+1}p_{n+2}\cdots p_{N})\in(*)$[(x +\Sigma 2’. .,xN.)\Sigma \in (|pn+2. .
$\cdot$$= \sum_{x_{n+1}\in X}$$p_{N}]p(x_{n+1}|x_{n}, u_{n})$が戒り立つ。 ここに$p_{m+1}=p(x_{m+1}|x_{m}, u_{m}),$$u_{m}=\tau_{m}$($x_{m}$; 果), 果、+1$=$

果、 $-r$ ( $x_{m}$ , 果、)$n\leq m\leq N-1$ .

また、 $(*)$ は $r_{n}(x_{n}, u_{n})+\cdots+r_{N}(x_{N})\geq$ へを満たす $(x_{n+1}, \ldots, x_{N})\in X\cross\cdots\cross X$ 全体 (こわたを満 す $(x_{n+2}, \ldots, x_{N})$ 全
は $r_{n+1}(x_{n+1}, u_{n+1})+\cdots+r_{N}(x_{N})\geq$ ら一る多重和であり、$_{\mathrm{c}}^{-}$$(\star)$$r_{n}$

体 [こわたっている。 ただし、 $r_{n}=r(x_{n}, u_{n}),$ $u_{n}=\tau_{n}(x_{n};c_{n})$ .

したがって、 上述の補題から後向きの再帰式が成り立つ :定理 5.1(9)$f_{n}(x;c)={\rm Max} \sum_{y\in X}f_{n+1}(y;c-r(x, u))p(y|x, u)u\in U$$(x;c)\in X\cross C_{n}$$f_{N}(x;c)=$$\{$1if $r(x)\geq c$0otherwise,$0\leq n\leq$$(x;c)\in X\cross C_{N}$

.

えー 1

87
さて、 式 (9) の最大点の全体を九とすると、 拡大マルコフ政策クラス
の中での
最適政策
が得られる。 さらに、 から、 以下のように一般政策$\ovalbox{\tt\small REJECT}$$(x\ovalbox{\tt\small REJECT} c)$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\{\ovalbox{\tt\small REJECT}, \ovalbox{\tt\small REJECT},, \ldots, \ovalbox{\tt\small REJECT}_{\ovalbox{\tt\small REJECT}-1}\}${$\ovalbox{\tt\small REJECT}_{0},$$\ovalbox{\tt\small REJECT}_{\mathrm{b}\ovalbox{\tt\small REJECT}}$.,$\ovalbox{\tt\small REJECT}$ー’} を生成する。 すなわち、$u_{0}:=\overline{\tau}_{0}(x_{0};c)$,$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}_{\mathrm{o}}(x_{0}, x,, \ldots, x_{n})\}$

ま$c_{1}:=c-r(x_{0}, u_{0})$,$c_{2}:=c_{1}-r(x_{1}, u_{1})$$u_{1}:=\overline{\tau}_{1}(x_{1};c_{1}.\cdot.)$$u_{n-1}:=\overline{\tau}_{n-1}(x_{n-1}; c_{n-1})$,

c、$:=$ ら-1 $-r(x_{n-1}, u_{n-1})$$n(x_{0}, x_{1}, \ldots, x_{n}):=\overline{\tau}_{n}(x_{n};c_{n})$.

このとき、 次が成り立つ :定理 52([10, Iheooem6.1])(i) 政策 は一般政策クラスの中での最適である。
の最大値は一般政策クラス$\text{ }(g)$$\overline{\sigma}$(ii) 拡大マルコフ政策クラス$\tilde{\text{ }}$$f_{0}(x_{0;}c)=v_{0}(x_{0})$の最大値に等しい :$\text{ }(g)$.

さらに、 過去値に基づく拡大マルコフ, クラス問題 I と未来 (閾) 値に基づく拡大マルコフクラス問題垣の間には次のような相補的な双対性が戒り立っている。
定理 53(相補的双対定理)(i) 任意の$\lambda_{n}\in\Lambda_{n}$に対してある $c_{n}\in C_{n}$ が存在して、 その和は一定値$\lambda_{n}+c_{n}=c$

逆も成り立つ。 すなわち、 任意のらである。

$\in C_{n}$

$c$

である

:

.

に対してあるが存在してその和は一定値$\lambda_{n}\in\Lambda_{n}$$c$(ii) このとき、 最適解 (最適値と最適決定関数) は共に一致している :$u^{n}(x_{n};\lambda_{n})=f_{n}(x_{n};c_{n})$,$x_{n}\in X$$\gamma_{n}^{*}(x_{n};\lambda_{n})=\overline{\tau}_{n}(x_{n};c_{n})$.

(iii) 過去値に基づく拡大マルコフクラス問題の最適解と未来 (閾) 値に基づく拡大マルコフクラス問題の最適解は上述の定和という意味で一致している :$u^{n}(x_{n} ; c-c_{n})=f_{n}(x_{n} ; c_{n})$,$\gamma_{n}^{*}(x_{n} ; c-c_{n})=\overline{\tau}_{n}$$(x_{n};c_{n})\in X\cross C_{n}$,($x_{n}$; ら)$0\leq n\leq N$ .

すなわち
$f_{n}(x_{n};c-\lambda_{n})=u^{n}(x_{n};\lambda_{n})$,$\overline{\tau}_{n}(x_{n};c-\lambda_{n})=\gamma_{n}^{*}(x_{n};\lambda_{n})$$(x_{n};\lambda_{n})\in X\cross\Lambda_{n}$,$0\leq n\leq N$ .

定理 54(一致定理)

過去値による拡大最適政策
から生戒された一般最適政策
政策 から生成された一般最適政策 に一致している :$\gamma^{*}$$\overline{\tau}$$\overline{\sigma}$$\sigma^{*}=\overline{\sigma}$.

$\sigma^{*}$

は未来 (閾) 値による拡大最適88
63 状態 2 決定 2 段問題
この節では、 3-2-2 (3 状態 2 決定 2 段) モデルにおいて (加法型) 総合評価値が $c=2.5$ 以
上になる閾値確率を最大化する問題を考える :Maximize $P_{x_{0}}^{\sigma}(r_{0}(U_{0})+r_{1}(U_{1})+r_{2}(X_{2})\geq 2.5)$
subject to (i)$n=0,1$$X_{n+1}\sim p(\cdot|x_{n}, u_{n})$(ii)$u_{0}\in U,$$u_{1}\in U$

ただし、 データとしては、 次のような Bellman and Zadeh [1, pp.B154] の数値例を用いる :$r_{2}(s_{1})=0.3$$r_{2}(s_{2})=1.0$$r_{1}(a_{1})=1.0$$r_{1}$$r_{0}(a_{1})=0.7$$r_{0}$$r_{2}(s_{3})=0.8$(a2) $=0.6$(a2) $=1.0$$u_{t}=a_{1}$$x_{t}\backslash x_{t+1}$$s_{2}$$s_{1}$

0.8 0.1
0.0 0.1
0.8 0.1$s_{1}$$s_{2}$$s_{3}$

6.1$u_{t}=a_{2}$$x_{t}\backslash x_{t+1}$$s_{3}$

0. 1
0.1
0.9
0. 1

$s_{1}$$s_{2}$$s_{3}$

0.1 0.9 0.
0.00
0.8 0.1 0. 1
0.1 0.0 0.9$s_{1}$$s_{2}$$s_{3}$

拡大マルコフ政策 I

最初に、 定義$\Lambda_{0}$$=\{0\}$$\Lambda_{1}$$=\{\lambda_{1}|\lambda_{1}=r_{0}(u_{0}), u_{0}\in U\}$$\Lambda_{2}$$=\{\lambda_{2}|\lambda_{2}=r_{0}(u_{0})+r_{1}(u_{1}), u_{0}, u_{1}\in U\}$

より、過去値集合列$\Lambda_{0}=\{0\}$,$\Lambda_{1}=\{0.7,1.0\}$,$\mathrm{A}_{2}=\{1.3,1.6,1.7,2.0\}$

を求めておく。 このとき、集積値確率変数$\tilde{\Lambda}_{0}=0$,$\tilde{\Lambda}_{1}=r_{0}(U_{0})$,$\tilde{\Lambda}_{2}=r_{0}(U_{0})+r_{1}(U_{1})$を用いると、 拡大状態空間上の終端問題はMaximizesubject to (i)(i)’$\tilde{E}_{y0}^{\gamma}[\psi(\tilde{\Lambda}_{2}+r_{2}(X_{2})]$(ii)$(y_{0}=(x_{0};0))$$X_{n+1}\sim p(\cdot|x_{n}, u_{n})$$\tilde{\Lambda}_{n+1}=\tilde{\Lambda}_{n}+r_{n}(U_{n})$$u_{n}\in\{a_{1}, a_{2}\}$$n=0,1$

89(こなる。 ただし$\psi(y)\ovalbox{\tt\small REJECT} 1[25,\infty$) $(y),$$\gamma\ovalbox{\tt\small REJECT}\{\ovalbox{\tt\small REJECT}, \gamma_{1}\}$.

まず、 終端関数$u^{2}(x_{2};\lambda_{2})$は次の表 1 の通り$=\psi(\lambda_{2}+r_{2}(x_{2}))$:

1.3 1.6 1.7 2.0
0
0
0
0
1
0
1
1
0
0
1
1

$x_{2}\backslash \lambda_{2}$$s_{1}$$s_{2}$$s_{3}$

表 1:$u^{2}(x_{2};\lambda_{2})$次に、 第 2 最適値関数$u^{1}(x_{1};\lambda_{1})$$=$${\rm Max} \sum_{x_{2}}u^{2}(x_{2;}\lambda_{1}+r_{1}(u_{1}))p(x_{2}|x_{1}, u_{1})u_{1}$を計算するのに表 1 を用いる。 最初の$u^{1}(s_{1}$

; 0.7

$)$

$=$

$u^{1}(s_{1}$; 0.7 は$)$[$u^{2}(s_{1}; 0.7+1.0)0.8+u^{2}(s_{2}; 0.7+1.0)0.1+u^{2}(s_{3}$ ; 0.7+1.0 0. 月$)$$\vee[u^{2}(s_{1}; 0.7+0.6)0.1+u^{2}(s_{2};0.7+0.6)0.9+u^{2}(s_{3};0.7+0.6)0.0]$$=$$[u^{2}(s_{1}; 1.7)0.8+u^{2}(s_{2};1.7)0.1+u^{2}(s_{3};1.7)0.1]$$\vee[u^{2}(s_{1} ; 1.3)0.1+u^{2}(s_{2};1.3)0.9+u^{2}(s_{3};1.3)0.0]$$=$[ $0\cross 0.8+1\cross 0.1+1$$\cross$

0. 月 $\vee[0\cross 0.1+0\cross 0.9+0\cross 0.0]$$=0.2\vee 0$$=0.2$$\gamma_{1}^{*}(s_{1}; 0.7)=a_{1}$になる。 以下、 同様にすると、 第 2 最適値関数$x_{1}\backslash \lambda_{1}$$s_{1}$$u^{1}$

0.7
0.2$a_{1}$$s_{2}$$1.0$$a_{1}$$s_{3}$$0.2$$a_{1}$

表 2:と第 2 最適決定関数$\gamma_{1}^{*}$

1.0
0.9
1.0
0.2

$a_{2}$$a_{1}$$a_{1}$$u^{1}(x_{1}; \lambda_{1})\gamma_{1}^{*}(x_{1}; \lambda_{1})$

最後に、 第 1 最適値関数$u^{0}(x_{0;}\lambda_{0})$$=$${\rm Max} \sum_{x_{1}}u^{1}(x_{1}; \lambda_{0}+r_{0}(u_{0}))p(x_{1}|x_{0}, u_{0})u_{0}$は次の表 2 になる

90
を求める。
$u^{0}(s_{1}$$u^{0}(s_{1}$

;0

$)$

; 0.7 は表 2 を用いると

$=$

$)$

$[u^{1}(s_{1};0.7)0.8+u^{1}(s_{2};0.7)0.1+u^{1}(s_{3};0.7)0.1]$$\vee[u^{1}(s_{1};1.0)0.1+u^{1}(s_{2};1.0)0.9+u^{1}(s_{3};1.0)0.0]$$=$$[0.2\cross 0.8+1.0\cross 0.1+0.2\cross 0.1]\vee[0.9\cross 0.1+1.0\cross 0.9+0.2 \cross 0.0]$$=$$0.28\vee 0.99$

$=$

0.99

$\gamma_{0}^{*}(s_{1}; 0)=a_{2}$になる。 同様にすると、 第 1 最適値関数$x_{0}$$u^{0}$と第 1 最適決定関数$u^{0}(x_{0}$

;0

$)$

$a_{2}$$s_{2}$$0.84$$a_{2}$$s_{3}$$0.28$$a_{1}$

表 3:

は次の表 3 になる :$\gamma_{0}^{*}(x_{0}; 0)$0.99$s_{1}$$\gamma_{0}^{*}$$u^{0}(x_{0};0)\gamma_{0}^{*}(x_{0};0)$

最適解をまとめると、 次の表 4 になる。

表 4: 拡大マルコフ政策クラス I の最適解

さて、 埋没問題の最適 (拡大マルコフ) 政策$\sigma_{0}^{*}(x_{0})$$\gamma^{*}=\{\gamma_{0}^{*}, \gamma_{1}^{*}\}$$:=\gamma_{0}^{*}(x_{0;}0)$$u_{0}:=\gamma_{0}^{*}(x_{0};0)$$\sigma_{0}^{*}(x_{0}, x_{1})$によって、 最適 (一般) 政策

から、 式

,

$\lambda_{1}:=r_{0}(u_{0})$$:=\gamma_{1}^{*}(x_{1}; \lambda_{1})$$\sigma^{*}=\{\sigma_{0}^{*}, \sigma_{1}^{*}\}$を構戒しよう。 まず、 第 1 決定関数$\sigma_{0}^{*}(s_{1})=\gamma_{0}^{*}(s_{1};0)=a_{2}$$\sigma_{0}^{*}(s_{2})=\gamma_{0}^{*}(s_{2;}0)=a_{2}$$\sigma_{0}^{*}(s_{3})=\gamma_{0}^{*}(s_{3;}0)=a_{1}$が得られる。 次に、 第 2 決定関数は以下になる :$\sigma_{1}^{*}(s_{1}, s_{1})=\gamma_{1}^{*}(s_{1}; 1.0)=a_{2}$$\sigma_{1}^{*}(s_{1}, s_{2})=\gamma_{1}^{*}(s_{2;}1.0)=a_{1}$$\sigma_{1}^{*}(s_{1}, s_{3})=\gamma_{1}^{*}(s_{3;}1.0)=a_{1}$91$\sigma_{1}^{*}(s_{2}, s_{1})=\gamma_{1}^{*}(s_{1}; 1.0)=a_{2}$$\sigma_{1}^{*}(s_{2}, s_{2})=\gamma_{1}^{*}(s_{2};1.0)=a_{1}$$\sigma_{1}^{*}(s_{2}, s_{3})=\gamma_{1}^{*}(s_{3};1.0)=a_{1}$$\sigma_{1}^{*}(s_{3}, s_{1})=\gamma_{1}^{*}(s_{1}; 0.7)=a_{1}$$\sigma_{1}^{*}(s_{3}, s_{2})=\gamma_{1}^{*}(s_{2};0.7)=a_{1}$$\sigma_{1}^{*}(s_{3}, s_{3})=\gamma_{1}^{*}(s_{3};0.7)=a_{1}$すなわち、 不変埋没原理によって (マルコフでない ) 最適政策
$!!$

6.2

$\sigma^{*}$が得られた。

拡大マルコフ政策垣

最初に、 定義$C_{0}$$=\{2.5\}$$C_{1}$$=\{c_{1}|c_{1}=2.5-r_{0}(u_{0}), u_{0}\in U\}$

$C_{2}$$=\{c_{2}|c_{2}=2.5-r_{0}(u_{0})-r_{1}(u_{1}), u_{0}, u_{1}\in U\}$より、 未来 (閾) 値集合列
$C_{0}=\{2.5\}$,$C_{1}=\{1.8,1.5\}$ ,$C_{2}=\{1.2,0.9,0.8,0.5\}$を求めておく。
まず、$f_{2}$を$\dot{1}$$f_{2}(x_{2;}c_{2})=$if$r(x_{2})\geq c_{2}$$(x_{2;}c_{2})\in X\cross C_{2}$$\{$0otherwiseで計算すると、 は次の表 5 が得られる :$x_{2}\backslash c_{2}$$s_{1}$$s_{2}$$s_{3}$

1.2 0.9
0
0
1
0
0
0

表5

:

0.6 0.5
0
0
1
1

1
1

$f_{2}(x_{2;}c_{2})$次に、 表 5 を用いて、 五を$f_{1}(x_{1}; c_{1})$$={\rm Max} \sum_{x_{2}}f_{2}(x_{2;}c_{1}-r_{1}(u_{1}))p(x_{2}|x_{1}, u_{1})u_{1}$92で計算する。 最初の五$f_{1}(s_{1};1.8)$$(s_{1}$; 1.8 は$)$$[f_{2}(s_{1};1.8-1.0)0.8+f_{2}(s_{2};1.8-1.0)0.1+f_{2}(s_{3};1.8-1.0)0.1]$$=$$\vee[f_{2}(s_{1}; 1.8-0.6)0.1+f_{2}(s_{2};1.8-0.6)0.9+f_{2}(s_{3};1.8-0.6)0.0]$$[f_{2}(s_{1}; 0.8)0.8+f_{2}(s_{2};0.8)0.1+f_{2}(s_{3};0.8)0.1]$$=$$\vee[f_{2}(s_{1}; 1.2)0.1+f_{2}(s_{2};1.2)0.9+f_{2}(s_{3};1.2)0.0]$$[0\cross 0.8+1\cross 0.1+1\cross 0.1]\vee[0\cross 0.1+0\cross 0.9+0\cross 0.0]$$=$$=0.2\vee 0$$=0.2$$\overline{\tau}_{1}(s_{1};0.7)=a_{1}$になる。 以下、 同様にすると、 第 2 最適値関数$x_{1}\backslash c_{1}$$s_{1}$.

$f_{1}$

1.8
0.2$a_{1}$$s_{2}$$1.0$$a_{1}$$s_{3}$$0.2$$a_{1}$

表 6:と第 2 最適決定関数$\overline{\tau}_{1}$は次の表 6 になる

1.5
0.9
1.0

$a_{2}$$a_{1}$

0.2$a_{1}$$f_{1}(x_{1}; c_{1})\overline{\tau}_{1}(x_{1};c_{1})$

最後に、 第 1 最適値関数$f_{0}(x_{0;}c_{0})$を求める。
$f_{0}(s_{1}$$f_{0}(s_{1}$

; 2.5

$)$

$=$

${\rm Max} \sum_{x_{1}}f_{1}(x_{1;}c_{0}-r_{0}(u_{0}))p(x_{1}|x_{0}, u_{0})u_{0}$; 2.5 は表 6 を用いると
$)$

$=$

$[f_{1}(s_{1};1.8)0.8+f_{1}(s_{2};1.8)0.1+f_{1}(s_{3};1.8)0.1]$$\vee[f_{1}(s_{1};1.5)0.1+f_{1}(s_{2};1.5)0.9+f_{1}(s_{3};1.5)0.0]$$=$$[0.2\cross 0.8+1.0\cross 0.1+0.2\cross 0.1]\vee[0.9\cross 0.1+1.0\cross 0.9+0.2\cross 0.0]$$=$$0.28\vee 0.99$

$=$

0.99

$\overline{\tau}_{0}(s_{1}; 0)=a_{2}$になる。 同様にすると、 第 1 最適値関数$x_{0}$$f_{0}$と第 1 最適決定関数$f_{0}(x_{0;} 2.5)$$s_{1}$

0.99$\overline{\tau}_{0}(x_{0;} 2.5)$$a_{2}$$s_{2}$$0.84$$a_{2}$$s_{3}$$0.28$$a_{1}$

表7 :$f_{0}(x_{0};2.5)\overline{\tau}_{0}(x_{0;}2.5)$

最適解をまとめると、 次の表 8 になる。

$\overline{\tau}_{0}$は次の表 7 になる :93$f_{1}(x_{1}; c_{1})$$f_{2}(x_{2}; c_{2})$$x_{n}\backslash \lambda_{n}$$s_{1}$$s_{2}$$s_{3}$$f_{0}(x_{0}$$\overline{\tau}_{1}(x_{1}; c_{1})$

1.2 0.9 0.8 0.5
1.8
0
0 0.2
0
0
1
1
1 $1.0$0
1
1 $0.2$00; 2.5$a_{2}$$a_{1}$$a_{1}$$1\overline{\tau}_{0}(x_{0;} 2.5)$

2.5
0.99

1.5
0.9
1.0
0.2

$a_{1}$$)$$a_{2}$$a_{1}$$0.84$$a_{2}$$a_{1}$$0.28$$a_{1}$

表 8: 拡大マルコフ政策クラス I の最適解

さて、 この埋没問題の最適 (拡大マルコフ) 政策$\overline{\sigma}_{0}(x_{0})$$:=$によって、 最適 (一般) 政策

$:=$

から、 式

$\overline{\tau}_{0}(x_{0};2.5)$$u_{0}:=\overline{\tau}_{0}(x_{0};2.5)$$\overline{\sigma}_{0}(x_{0}, x_{1})$$\overline{\tau}=\{\overline{\tau}_{0},\overline{\tau}_{1}\}$,$c_{1}:=2.5-r_{0}(u_{0})$$\overline{\tau}_{1}(x_{1}; c_{1})$$\overline{\sigma}=\{\overline{\sigma}_{0},\overline{\sigma}_{1}\}$を構成しよう。 まず、 第 1 決定関数$\overline{\sigma}_{0}(s_{1})--\overline{\tau}_{0}(s_{1}; 2.5)=a_{2}$$\overline{\sigma}_{0}(s_{2})=\overline{\tau}_{0}(s_{2};2.5)=a_{2}$$\overline{\sigma}_{0}(s_{3})=\overline{\tau}_{0}(s_{3};2.5)=a_{1}$が得られる。 次に、 第 2 決定関数は以下になる :$\overline{\sigma}_{1}(s_{1}, s_{1})=\overline{\tau}_{1}(s_{1};1.5)=a_{2}$$\overline{\sigma}_{1}(s_{1}, s_{2})=\overline{\tau}_{1}(s_{2};1.5)=a_{1}$

1 $(s_{1}, s_{3})=\overline{\tau}_{1}(s_{3};1.5)=a_{1}$$\overline{\sigma}_{1}(s_{2}, s_{1})=\overline{\tau}_{1}(s_{1};1.5)=a_{2}$$\overline{\sigma}_{1}(s_{2}, s_{2})=\overline{\tau}_{1}(s_{2};1.5)=a_{1}$

1 $(s_{2}, s_{3})=\overline{\tau}_{1}(s_{3};1.5)=a_{1}$$\overline{\sigma}_{1}(s_{3}, s_{1})=\overline{\tau}_{1}(s_{1}; 1.8)=a_{1}$$\overline{\sigma}_{1}(s_{3}, s_{2})=\overline{\tau}_{1}(s_{2};1.8)=a_{1}$$\overline{\sigma}_{1}(s_{3}, s_{3})=\overline{\tau}_{1}(s_{3};1.8)=a_{1}$すなわち、 不変埋没原理によって (マルコフでない!!) 最適政策から生成された一般最適政策
過去値による拡大最適政策
適政策 から生成された一般最適政策 に一致している :$\gamma^{*}$$\overline{\tau}$$\overline{\sigma}$$\sigma^{*}=\overline{\sigma}$.

$\sigma^{*}$が得られた。
は未来 (閾) 値による拡大最$\overline{\sigma}$

94
6.3

多段確率決定樹表

多段確率決定樹表は、 いわゆる決定樹 (ディシジョン・ツリー) 、決定表 (ディシジョン・テーブル) をそれぞれ進化・発展させ、 多段階にわたる確率的決定過程の問題記述から最適解構戒に至るまでを 1 枚に統合した図表である。 問題のデータを過程の進行状況に応じて配列し、 あらゆる可能な経路とその評価値・確率を図示し、各段における最適決定の選択を明示している。
この意味では列挙法の解構戒を与えている。 しかし、 最適解に至るまでは動的計画法の再帰式
を解く順に構戒されている。 この樹表ではあらゆる型の評価関数に対してその期待値最適化が解かれる [5]。
を次で定義する :まず、 原始政策 $\mu=\{\mu_{0}, \mu_{1}\}$ に対して、 条件付き期待値作用素$E_{x_{0}^{0}}^{\mu},$$E_{h_{1}}^{\mu_{1}}$$=\triangle$$E_{x_{0}^{0}}^{\mu}[g_{1}]$$\sum_{x_{1}\in X}g_{1}(x_{0}, u_{0}, x_{1})p(x_{1}|x_{0}, u_{0})$ただし $u_{0}=\mu_{0}(x_{0})$ ,$E_{h_{1}}^{\mu 1}[g_{2}]$$g_{1}$: $X\cross U\cross Xarrow R^{1}$$= \triangle\sum_{x_{2}\in X}g_{2}(x_{0},u_{0},x_{1}, u_{1}, x_{2})p(x_{2}|x_{1}, u_{1})$

ただし $u_{1}=\mu_{1}(h_{1});h_{1}=$ ($g_{2}$$x_{0},$ $u_{0}$, xl)》: $X\cross U\cross X\cross U\cross Xarrow R^{1}$ .

このとき、 閾値確率は期待値になり、 条件付き期待値作用素の繰り返しで表される :$P_{x_{0}}^{\mu}(r_{0}+r_{1}+r_{2}\geq c)$$=E_{x_{0}}^{\mu}[\psi(r_{0}+r_{1}+r_{2})]$$=E_{x_{0}^{0}}^{\mu}E_{h_{1}}^{\mu 1}[\psi(r_{0}+r_{1}+r_{2})]$

したがって、 原始政策クラス$\text{ }(p)$上の 「同時」 最適化は条件付き期待値の 「繰り返し」 最適化に等しい [3] :${\rm Max} P_{x_{0}}^{\mu}(r_{0}+r_{1}+r_{2}\geq c)$$\mu\in\Pi(p)$$=$${\rm Max} E_{x_{0}}^{\mu}[\psi(r_{0}+r_{1}+r_{2})]$$\mu\in\Pi(\mathrm{p})$$=$${\rm Max}{\rm Max} E_{x_{0}}^{\mu 0}E_{h_{1}}^{\mu_{1}}\mu 0\mu_{1}[\psi(r_{0}+r_{1}+r_{2})]$$=$${\rm Max} E_{x_{0}}^{\mu 0}{\rm Max} E_{h_{1}}^{\mu_{1}}\mu 0\mu 1[\psi(r_{0}+r_{1}+r_{2})]$.

これは動的計画法の原始的な型 (a primitive form) である [4]。 すなわち、 原始政策クラス問題の再帰式$w_{2}(x_{0}, u_{0}, x_{1}, u_{1}, x_{2})$$w_{1}(x_{0}, u_{0}, x_{1})$$w_{0}(x_{0})$が得られたことになる。

$=$$\psi$( (v り)+rl $(u_{1})+r_{2}(x_{2})$ )$r_{0}$$={\rm Max} \sum_{x_{2}}w_{2}(x_{0}, u_{0}, x_{1}, u_{1}, x_{2})p(x_{2}|x_{1}, u_{1})u_{1}$$=$${\rm Max} \sum_{x_{0}}w_{1}(x_{0}, u_{0}, x_{1})p(x_{1}|x_{0}, u_{0})u_{0}$95
図 1, 2 および 3 では、 次のように簡略化している:

履歴 $=x_{0}r_{0}(u_{0})/u_{0}p0x_{1}r_{1}(u_{1})/u_{1}p_{1}x_{2}r_{2}(x_{2})$
ただし $p_{0}=p(x_{1}|x_{0}, u_{0})$ ,$p_{1}=p(x_{2}|x_{1}, u_{1})$

加法 $=$ 加法型評価値 $=r_{0}(u_{0})+r_{1}(u_{1})+r_{2}(x_{2})$
経路 $=$ 経路確率 =p0 角

閾確 $=$ 閾値確率 $=\psi(r_{0}(u_{0})+r_{1}(u_{1})+r_{2}(x_{2}))p_{0}p_{1}$ただし $\psi(y)=1[2.5,\infty)(y)$

部分確 $=$ 部分確率 $= \sum_{x_{2}}\psi(r_{0}(u_{0})+r_{1}(u_{1})+r_{2}(x_{2}))p_{0}p_{1}$
全確率 $=$ 全体確率 $= \sum_{x_{1}}\sum_{x_{2}}\psi(r_{0}(u_{0})+r_{1}(u_{1})+r_{2}(x_{2}))p_{0}p_{1}$ .

イタリソク体は確率を表し、ボールド体は上下の確率のうち大きい方を選択したことを表す。特(こ、 履歴の欄で (ま 5 つの数値 $r_{0}=r_{0}(u_{0}),$

図 1 によって$P\mathrm{o},$$r_{1}=r_{1}(u_{1}),$$r_{2}=r_{2}(x_{2})$$p_{1},$のみを記して$\mathrm{A}\mathrm{a}$る。

からの最適解 (最大値および最適決定関数列) が求められる。 まず、「部分確」 の列は、 過程が $x_{0}=s_{1}arrow u_{0}arrow x_{1}$ まで進行してきたとき、 各選択において (上下の) 大
きい値 ( ゴチック体の数字) を原始最適決定$s_{1}$$=$$\tilde{\mu}_{1}(s_{1}, a_{1}, s_{1})=a_{1}$$\tilde{\mu}_{1}(s_{1}, a_{2}, s_{1})=a_{2}$,,$\tilde{\mu}_{1}(s_{1}, a_{1}, s_{2})=a_{1}$$\tilde{\mu}_{1}(s_{1}, a_{2}, s_{2})=a_{1}$,,$\tilde{\mu}_{1}(s_{1}, a_{1}, s_{3})=a_{1}$$\tilde{\mu}_{1}(s_{1}, a_{2}, s_{3})=a_{1},$ $a_{2}$として選択していることを示している。 すなわち、「部分確」 の列のボールド体は、 各 $h_{1}=$に対して、 最初の最適化$(s_{1}, u_{0}, x_{1})$${\rm Max} E_{h_{1}}^{\mu 1}[\psi(r_{0}\mu 1+r_{1}+r_{2})]$を行なっている。 この最大値を $g_{1}=g_{1}(h_{1})$ とする。
次に、「全確率」 の列は、 過程が $x_{0}=s_{1}$ から出発すると、 上下の比較にょってが最適決定で、 最大値は $w_{0}(s_{1})=0.99$ あることを示してぃる。 したがって、 一般最適決定$\tilde{\mu}_{0}(s_{1})=a_{2}$$\tilde{\sigma}_{1}(s_{1}, s_{1})=a_{2}$$\ovalbox{\tt\small REJECT}_{0}(s_{1})=a_{2;}$,$\tilde{\sigma}_{1}(s_{1}, s_{2})=a_{1}$,$\tilde{\sigma}_{1}(s_{1}, s_{3})=a_{1},$ $a_{2}$が得られる。 すなわち、「全確率」 の列のボールド体は $x_{0}=s_{1}$ に対して次の最適化${\rm Max} E_{x_{0}}^{\mu 0}[g_{1}]\mu 0$を行なっている。
さらに$\text{、}$$s_{2},$$s_{3}$からの図 2,3 と合せると、 原始最適政策$\tilde{\mu}=\{\tilde{\mu}_{0},\tilde{\mu}_{1}\}$が得られ、 最適解は$\tilde{\sigma}_{0}(s_{2})=a_{2}$;$\tilde{\sigma}_{1}(s_{2}, s_{1})=a_{2}$,$\tilde{\sigma}_{1}(s_{2}, s_{2})=a_{1}$,$\tilde{\sigma}_{1}(s_{2}, s_{3})=a_{1}$$\tilde{\sigma}_{0}(s_{3})=a_{1}$;$\tilde{\sigma}_{1}(s_{3}, s_{1})=a_{1}$,$\tilde{\sigma}_{1}(s_{3}, s_{2})=a_{1}$,$\tilde{\sigma}_{1}(s_{3}, s_{3})=a_{1}$$w_{0}(s_{2})=0.84$,になる。 この一般最適政策

三つの最適な一般政策$\tilde{\sigma}=\{\tilde{\sigma}_{1},\tilde{\sigma}_{2}\}$$\sigma^{*},\hat{\sigma},\tilde{\sigma}$

2.5 以上になる確率は 0 である )。

$w_{0}(s_{3})=0.28$

はマルコフでない :は本質的に一致している$\tilde{\sigma}_{1}(s_{1}, s_{1})\neq\tilde{\sigma}_{1}(s_{3}, s_{1})$$(\tilde{\sigma}_{1}(s_{1}, s_{3})=a_{1}$.

, a2 のいずれでも

96$w_{0}(\ovalbox{\tt\small REJECT} \mathrm{s}_{1})\ovalbox{\tt\small REJECT}{\rm Max} P\ovalbox{\tt\small REJECT}(r_{\ovalbox{\tt\small REJECT}}(U\ovalbox{\tt\small REJECT}_{0})+r_{1}(U_{1})+r_{2}(X_{2})\ovalbox{\tt\small REJECT} 25)$$\mu$

図 1: 状態$s_{1}$からの 2 段確率決定樹表

97$w_{0}(s_{2})\ovalbox{\tt\small REJECT}{\rm Max} I\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}(r\mathrm{o}(U\mathrm{o})+r.(\mathrm{U}\ovalbox{\tt\small REJECT})+r_{2}(X_{2})\ovalbox{\tt\small REJECT} 25)$$\mu$

図 2: 状態$s_{2}$からの 2 段確率決定樹表

98$\mathrm{t}\mathrm{o}_{0}(\mathrm{s}_{3})\ovalbox{\tt\small REJECT}{\rm Max} P\ovalbox{\tt\small REJECT} 7(r_{0}(U_{0})+r.(U.)+7^{\ovalbox{\tt\small REJECT}}2(X_{2})\ovalbox{\tt\small REJECT} 2.5)$$\mathrm{p}$図 3: 状態$s_{3}$からの 2 段確率決定樹表

99$J^{0}(x_{0}\ovalbox{\tt\small REJECT}\pi)$1$\ovalbox{\tt\small REJECT} I\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}(r_{0}+r_{1}+r_{2}\ovalbox{\tt\small REJECT} 25)$

ただし、$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}$$I\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}[\psi(r_{0}+r_{1}+r_{2})]$$\sum$$\psi(y)\ovalbox{\tt\small REJECT}$$y\ovalbox{\tt\small REJECT} 25$

0 $y<25$$\{[\psi(r_{0}(u_{0})+r_{1}(u_{1})+r_{2}(x_{2}))]p(x_{1}|x_{0},u_{0})p(x_{2}|x_{1},u_{1})\}$$(x_{1},x_{2})\mathrm{C}X\cross X$

表 9: 全閾値確率ベクトル $J^{0}(\pi)$ , ただし、 $\pi=\{\pi_{0}, \pi_{1}\}$ はマルコフ政策

一般に、 加法型評価系であっても閾値確率最適化問題ではマルコフ政策が最適になるとは限らない。 事実、表 9 における (全 64 個の) マルコフ政策クラスには最適政策は存在しない $[2, 14]$

。

100
参考文献
[1]

. Bellman andence, 17, 1970$\mathrm{R}.\mathrm{E}$$\mathrm{L}.\mathrm{A}$. Zadeh, Decision-making in afuzzy environment, Management Sci-

[2] M. Bouah.z and Y. Kebir, Target-level criterion in Markov decision processes, Journal of
Optimizahon Iheory and Applications, 86 (1995), 1-15.
[3] G. H. Hardy, J. E. littlewood and G.

$\mathrm{P}6\mathrm{l}\mathrm{y}\mathrm{a}$, Inequalities, 2nd ed., Cambridge Univ. Press,

1952.
[4] 岩本誠一, 「動的計画の最近の進歩」 , 第 2$\fbox-\mathrm{R}$AM$\mathrm{P}$

シンポジウム論文集, 129-140, 1990.

[5] 岩本誠一, 多段確率決定樹表について, 日本 OR 学会秋季研究発表会アブストラクト集, pp.
58-59, 1999.
[6] 岩本誠一, 確率最適化における再帰式と決定樹表, 「不確実、 不確定性の下での数理的決定理論」 京大数理研講究録 1132, 2000 年, 15-23.
[7] S. Iwamoto, Maximizing threshold probability through invariant imbedding, $Eds$ . H. .
Proceedings of The Eighth BELLMAN CONTINUUM, Hsinchu, ROC,
Wang and $U.P$ .
Dec.2000, pp. 17-22.
$F$$Wen_{f}$[8] S. Iwamoto, Fuzzy decision-making through three dynamic programming approaches, $Eds$ .
$H.F$. Wang and $U.P$ . $Wen$ , Proceedings of The Eighth BELLMAN CONTINUUM, Hsinchu,
ROC, Dec.2000, pp.23-27.

[9] S. Iwamoto and T. Fujita, Stochastic decision-making in afuzzy environment, J. Operations. Soc. Japan, 38, 1995${\rm Res}$[10] S. Iwamoto, T. Ueno and T. Fujita, Controlled Markov chains with utility functions,
Proc. of The International Workshop on Markov Processes and Controlled Markov Chains,
Changsha, China, August, 1999, in press.
[11] 植野貴之, マルコフ連鎖上の閾値確率制御, 九州大学大学院経済学研究科修士論文, 2001
年 3 月.

[12] 植野貴之・岩本誠一, 最小型評価系の閾値確率制御, 日本 OR 学会秋季研究発表会アブス
トラクト集, pp. 124-125,2000.

[13] 植野貴之・岩本誠一, 制御マルコフ連鎖上での閾値確率最適化の方法, 研究集会 「不確実性の下での数理モデルの構築と最適化」 , 2000 年 11 月, 京都大・数理研.
[14] C. Wu and Y. Lin, Minimizing risk models in Markov decision processed with policies
depending on target values, Joumal of Mathematical Analysis and Applications, 231 (1999),