閾値確率基準マルコフ決定過程とポジティブ DP

(1)

閾値確率基準マルコフ決定過程とポジティブ DP

船　　木　　洋　　一　

Ⅰ　はじめに

　閾値確率基準マルコフ決定過程をポジティブ

DP

として定式化し、その定常な最適政策の存在を述べる。

　無限期間の逐次決定問題を考える。システムの可能な状態空間を

S

とする。システムの状態が

i

である時の可能な行動空間を

A i

とする。時点

t

^{でシステムの状態が}

i ^∈ S

^{のとき行動}

a ^∈ A i

を選択すると、その期に直接報酬

r

iaが得られ、次の期に推移確率

p

ijaで状態

j

^{になる。時点}

t

^で行動を選択する規則を関数

d t

で表す。決定時点が

t ^＝ ^{0, 1,} …と番号付けられているものとする。各時

点でのこの行動の選択規則の列

　　　π≡

｛ d d d

⁰⁰

^, d d d

¹¹

^{, …,} d d d n n ^{,… ｝}

を政策と呼ぶ。

t

^{時点における状態を}

s t 、行動を a t

とするとき　　　

（ s

0

, a

0

, s

1

, a

1

, …, a t

^-1

, s t ）

を時点

t

における履歴と呼ぶ。時点

t

で行動を選択する規則が、履歴を考慮して行うか、考慮しないで行うか、ランダムな選択を許すか、許さないかによって、政策を以下のように呼ぶことにしよう。

　　政策：履歴に依存しランダムな選択を許す、もっとも一般的な政策。

　　マルコフ政策：現在の状態にのみ依存しランダムな選択を許す政策。

　　定常政策：マルコフ政策でランダムな選択を許さず害害害害害害害害害害害

、各時点の決定規則が同じ政策。

　割引率

（ discount factor ）

を

β （ 0＜ β ＜1 ）

として、時点

t

^{における直接報酬を}

R t

であらわすと、

無限期間の割引総報酬

V

^は

V＝ Σ

_t

^β ^t ^t ^t ^R ^R ^t

であらわされる。これは確率変数であり、値は初期状態

i

と選択した政策πに依存して決まる。それを強調したいときには

V i

^πと書く。その期待値を

E E E

^π^π

［ i V ］

であらわす。すべての

i

に対して、この期待値を最大にする政策を割引最適政策と呼ぼう。本稿を通して次の仮定を置く。

仮定１

（1）

　状態集合

S＝｛1, 2, …｝は可算、

（2）

A i

は各

i ^∈ S

に対して完備可分距離空間のコンパクトな部分集合、

（3）

　直接報酬

r （ 0 i a － ^＜ r i a ＜－ G ^{）は各状態} i ^∈ S

^に対して

a

^{に関して連続、}

（4）

　推移確率

p ij a

は各状態

i ^∈ S

^と

j ^∈ S

^に対して

a

^{に関して連続。}

(2)

この仮定１が成立する時、定常政策の中に割引最適政策が存在することが知られている。

Ⅱ　閾値確率基準

　ここで割引総報酬が一定の値を超える確率

P

^π

［ i V ^＞ _－ C ］を考えよう。これは政策πを用い、初期

状態

i

から出発したときの割引総報酬が

C

以上となる確率をあらわす。この確率を最大にする政策を求めたい。

s

π up P

^π

［ i V ^＞－ C ^］

^{を与える政策である。}この基準を閾値確率基準と呼ぶことにしよう。

　初期時点で状態

i

^{にあり、目標は}

V ^＞ _－ C

^{とする。状態}

i

^で行動

a

^{を選択して、報酬}

r ij a

を得て、

次の時点で状態

j

に推移したとする。そうすると、次の時点での目標は、

V V V j j ^＞ _－ ^（ C ^－ r ij a ） / β

となる。（ただし

V V V j j

は次の時点以後の割引総報酬である。）なぜならば

V ^＝ r ij a ＋ β V V V j j ^＞－ C

^{となるからである。}

　この章以降、現時点で得られる直接報酬を次の時点の状態

j

にも依存するとする。この場合、前章での直接報酬は

r i a ＝ Σ

_j

^r îj â ^p îj â

^{として考える。（}

^r ^ij ^a

^は

⁰ ^＜－ r ij a ＜－ G

であり、各状態

i, j ^∈ S

^に対して

a

に関して連続であると仮定する。）

［状態空間の拡張］

　閾値確率基準では、最適政策を求めるときに、マルコフ政策のみを考えたのでは十分ではない。

拡張した状態空間の上でのマルコフ政策を考えなければならない。この点を説明しよう。今、従来の政策の意味でπ＝

｛ d d d

⁰⁰

^, d d d

¹¹

^{, … ｝}

^{を考える。}

q （ i a ^）

^で

d d d ^（

⁰⁰

i ^） ^＝ a

となる確率を表す。本稿を通して度数分布の形でのみ証明する。すると

　　　 P

iπ

［ V ^＞ _－ C ］＝ Σ

_a

^q ^（a）

ⁱ

Σ

_j

^p ^ij ^a ^P ^P ^P ^j ^j ^π ^π ^π ^［ ^' ^' ^V ^＞ ^－ ^C ^C ^C ^' ^' ^］ ……… （1）

となる。ここで

C' ^＝ ^（ C ^－ r ij a ） / β

であり、π

' ＝｛ d d d

00

' , d d d

11

' , … ｝は政策πを一つずらした政策である。

d t

d ' ^（ h t ' ^） ^＝ d d d t t

⁺¹

^（ h t

⁺¹

）

で定義される。ただし

t ^＞－ 0

に対して　　　

h t

⁺¹

＝（ i ^, a ^, s

⁰

' , a

⁰

' , …, a t

^-1

' , s t ' ）

のとき

h t ' _t ' _t ＝（ s

⁰

' , a

⁰

' , …, a t

^-1

' , s t ' ' ' ））

である。

　上式

（1）の両辺で政策πに関して sup

をとると

　　　s up π P

^π

_i ^［ V ^＞ _－ C ^］ ^＝s ^up

_π 兼献

験

Σ

_a

^q （ i a ） Σ

_j

^p ij a P P P

^π

_j _j ［ ^' V ^＞ _－ C C C ' ' ^］

^券^献鹸

　　　　　　　　　＝sup

d₀ d₀ d

兼献

験

Σ

_a

^q ^（ ⁱ ^a ^） Σ

_j

^p îj â ^s ûp _π' ^{（ P} ^P ^P

^π

^j ^j ^［ ^' ^V ^V ^V ^＞ ^＞ ^－ ^C ^C ^C ^' ^' ^］ ^）

^券^献

鹸となる。s

up P π' P P

^π

_j _j ［ ^' V V V ^＞ ^＞ _－ C ' ' ' ］］

の値はの値は

C '

により影響を受ける。ここで

C ' ＝（ C ^－ r ij a ） / β

であるから、右辺を最大にする

d d d

⁰⁰^は

C

の値にも依存する。すなわち最適政策も

C

に依存する。したがって、この目

(3)

的関数を持つ、マルコフ決定モデルでは、最適政策は、その時点までのシステムの状態と行動ばかりでなく、基準となる値

C

^{にも依存する。}

　それで、システムの状態

S

^{と実数直線}

R

^との直積

S ^× R

を考えて、これを拡張された状態空間と呼ぶことにしよう。この拡張された状態空間は非可算の集合となる。また、

S ^× R

^{の要素を拡張} された状態と呼び

i ^∈ S ^、 C ^∈ R

^として

^（ i ^, C ^）

で表そう。また一つの文字でこの拡張された状態を表すときには

x

を用いることにしよう。すなわち

x ^∈ S ^× R

である。行動空間は拡張された状態の

１番目の要素のみに依存して、拡張前と同様である。

x ^∈ ^（ i ^, C ^）

^のとき、

A

x

≡ A

iと定義しよう。

［履歴の拡張］

　状態空間の拡張に伴い、履歴も拡張する必要がある。履歴を　　　

（ x

⁰

^, a

⁰

^, x

¹

^, a

¹

^{, …,} x t

^-1

, a t

^-1

, x t ）

x x x k k ^＝ ^（ i i i

^k^k

^, c c c

^k^k

^） ^∈ S ^× R，　 k ＝0, 1, …, t ； a a a

^k^k

^∈ A i

k

，

k ＝ 0, 1, …, t ^－1

であらわし、今後この拡張された履歴を

h t

で表すことにしよう。

［決定関数の新しい履歴への依存］

　また

t

^{時点で履歴}

h t

のときの行動

a ^∈ A _it

^{をとる確率が}

q _ht ^（ a ^）

Σ

_a

^q ht （ a ^） ^＝1，

⁰

^＜ _－ q _ht ^（ a ^） ^＜ _－ ¹

であるランダムな決定関数を

d d d ^（ t t h t ）

であらわし、この決定関数からなる政策

｛ d d d

⁰⁰

^, d d d

¹¹

^{, … ｝}

^{を考える。}

　今後も記号

q _ht ^（ a ^）

^{でランダムな決定関数}

d d d ^（ t t h t ）

に対応する確率を表すことにする。

［政策の再定義］

　今後システムの状態といったら拡張された状態

x ^∈ S ^× R

^を指し、政策といったら新しい拡張された履歴に依存する政策を指すことにする。マルコフ政策、定常政策の場合についてもそれらの依存する状態は

x ^∈ S ^× R

^である。

［目的関数の書き換え］

　確率は初期状態

x

と政策πに依存する。すべての状態

i

^{とすべての実数}

C

^に対して　　　

Pr ^［ V V V i i

^π*

^＞ _－ C ^］ ^＝s ^up _π Pr ^［ V V V i i

^π

^＞ _－ C ^］

となるπ^＊が閾値確率基準での最適政策である。システムの状態が拡張されたモデルに対しても、

確率が初期状態

x

と政策πに依存していることを表すために　　　

P x

^π

［・］ ≡ Pr ^［・］

と書くことにしよう。

x ^＝ ^（ i ^, C ^）

^のとき、

P x

^π

［ V V V V V C ^＞ ^＞ _－ _－ ^］ ^＝ Pr ^［ V V V i i

^π

^＞ _－ C ^］

(4)

である。

（証明）

　簡単な式の変形により

（1） C ^＞ r ij a （1－ / β ）

ならば

（ C ^－ r ij a ） / β ＞ C ^。 C' ^＝ ^（ C ^－ r ij a ） / β

より

C' ^＞ C ^{。他も同様。}

（2）（1）より明らか。

（3） J ＝ C' ^－ C ＝｛ ^（1－ β ） C ^－ r ij a ｝ / β

であり、1－

β ＞0

であることより

J

^は

C

^{の単調増加関数。}

(

証明終わり

)

（3）

のイメージは数直線上で

C

が大きければ大きいほど

C'

^は

C

より右方により大きく離れ、

C

が小さければ小さいほど

C'

^は

C

より左方により大きく離れるということである。

仮定２

　割引総報酬

V

の確率分布は連続と仮定する。

　すなわち任意の

i

と対象とする政策πに対して

V V V V V i i

^π^π^{が特定の値}

C

^{をとる確率が}

⁰

^{と仮定する。}

U ^＝ ^｛（ i ^, C ^）

^│

^（ i ^, C ^） ^∈ S ^× R ^， C ^＞ _－ ru ^（1－ ^/ β ）｝，

L ^＝ ^｛（ i ^, C ^）

^│

^（ i ^, C ^） ^∈ S ^× R ^， C ＜ rl ^（1－ ^/ β ）｝

と二つの集合を定義する。定理１

（2）

から、いったん

C ^＞ _－ ru ^（1－ ^/ β ）

や

C ^＜ rl ^（1－ ^/ β ）

になると、それ以降もそうであることがわかる。

　任意の政策πに対して

x ^∈ U

^{ならば、常に目標}

C

^{は達成できないので、}

P x

^π

［ V ^＞ _－ C ^］ ^＝0、

x ^∈ L

^{ならば、常に目標}

C

^{は達成できるので、}

P x

^π

［ V ^＞ _－ C ^］ ^＝1

である。

　割引率

β ＜1，直接報酬 r ij a ＜－ G

^{なので総報酬の実現値}

v

v ^＝ r

⁰

^＋ β r

¹

^＋ β

²

r

²

^＋…＋ β ^t r t ＋…

は確定して

v ^＜－ G ^（1－ ^/ β ）

である。ただし

r t

は

t

時点の直接報酬の実現値とする。

定理１

　拡張された状態

（ i, C ^）

^{から拡張された状態}

^（ j,C' ）

に

1

度で推移するとする。そのとき

（1） C ＝ r ij a （1－ / β ）

　ならば　

C' ＝ C 、

C ^＞ r ij a （1－ / β ）

　ならば　

C' ^＞ C ^、

C ^＜ r ij a （1－ / β ）

　ならば　

C' ^＜ C ^。

　また逆も成り立つ。

（2） ru ≡ s

i,j,a

up

i,j,a

up

i,j,a

r ij a ， rl ≡ i

i,j,a

nf r ij a

とおくと

C ^＞ _－ ru ^（1－ ^/ β ）

　ならば　C

' ^＞ _－ ru ^（1－ ^/ β ）、

　　C ＜

rl ^（1－ ^/ β ）

　ならば　C

' ^＜ rl ^（1－ ^/ β ）。

（3） J ^≡ C' ^－ C

^は

C

の単調増加関数である。

(5)

　任意の閾値

C ^（ rll ^（1－ ^（1－ ^/ ^/ β ）＜ C ^＜ ru ^（1－ ^/ β ））に対して必ず C ^＜ _－ v

^あるいは

v ^＜ C

^{のいずれか} が成立する。

（証明）

①　

rl （1－ / β ）＜ C ^＜ v

^のとき

（ v ^） k ≡ r

⁰

^＋ β r

¹

^＋ β

²

r

²

^＋…＋ β ^k ^k ^k r r r r k k

と定義する。そのとき（

v ^） T T T

^-2^-2

＋ β ^T ^T ^T

^-1^-1

rl ^（1－ ^/ β ）＜－ C

^で（

v ^） T T T

^-1^-1

＋ β ^T ^T ^T rl rl ^（1－ ^/ β ）＞ C

^となる

T

^がある。

C C C

11

^≡ ^（ C ^－ r

0

） / β ，

C C C

²²

^≡ ^（ C C C

¹¹

^－ r

¹

^） ^/ β ，

　　　…

C C C k k ^≡ ^（ C C C k k k k

^-1^-1

－ r r r k k k k

^-1^-1

） / β ，

　　　…

と定義すると

C T T T

^-1^-1

＞－ rl ^（1－ ^/ β ）

で

C T _T _T ＜＜ rl ^（1－ ^/ β ）

となり、

T

^{時点までには集合}

L

^{にはいる。}

②　

ru ^（1－ ^/ β ）＞ C C C v ^＞ ^＞

^のとき

同様にして（

v ^） T T T

^-2^-2

＋ β ^T ^T ^T

^-1^-1

ru ^（1－ ^/ β ）＞ C

^で（

v ^） T T T

^-1^-1

＋ β ^T ^T ^T ru ru ^（1－ ^/ β ）＜－ C

^となる

T

^がある。

C T T T

^-1^-1

＜ ru ^（1－ ^/ β ）

で

C T ＞－ ru ^（1－ ^/ β ）

となり、

T

^{時点までには集合}

U

^{にはいる。}

（証明終わり）

　割引総報酬の確率分布が連続であると仮定している

（仮定２）

ので、①②からシステムの状態は確率

1

で集合

U

^あるいは

L

^{にはいる。}

［ C

^{の離散化］}

　基準値

C

のとりうる値の集合は非可算である。計算と簡単化のため

C

を離散近似しよう。ここで

C

を離散近似することはそれほど不自然ではない。仮に

C

を金額であるとすると、我々は円未満を考慮しない。あるいはもっと大きな金額が最小の単位の場合もある。

　以下で

inf、sup

はすべての

i, j, a

に対しての下限や上限である。

c

を任意の実数とする。

m ^{≡ inf} ^｛ r ij a ｝（1－ / β ），

c ^－ ^{≡ inf} ^｛（ c ^－ r ij a ） / β ｝，

M ^≡sup ^｛ r ij a ｝（1－ / β ），

c ^＋ ^≡ ^sup ^｛（ c ^－ r ij a ） / β ｝，

　と定義する。

m

^と

M

^の間を

ⁿ

^{等分する。}

c

¹

^≡ m ^，

c n

⁺¹

≡ M

として、両端を含めて小さい方から　　　

c

¹

^, c

²

^{, …,} c n

⁺¹

定理２

　各

x ^∈ S ^× R

に対して

ε ＞ 0

と

T ＜ ∞

が存在して

P

^π

x ［ X X X T T ^∈ U ^∪ L ^］ ^＞ ε

が成立する。

(6)

とする。

　半開区間

［ c i , c i

⁺¹

）の点を左端の点 c i

で近似する。さらに

［（m ^－） ^－ , m ^－ ^） ^∪ ^［ m ^－ ^, c 1 ）

を

m ^－

^{で（これを}

c

⁰^{とおく）、}

［ M M M M ^, ^, M M ^＋ ^＋ ^］

^を

M

^{で、すなわち}

c n

⁺¹

で近似する。

K ^≡｛ c

⁰

^, c

¹

^, c

²

^{, …,} c n

⁺¹

｝，

K ^＋ ^≡｛ c

¹

^, c

²

^{, …,} c n

⁺¹

｝

と定義する。

状態空間は

S×K

とする。この状態空間は可算の集合となる。今後、状態はすべてこの近似された状態で考える。また、この近似により、正確には近似式であるところも等式で表わすことにする。

　次の定理により、任意の政策に対して、時点

t

の状態と行動に対して同じ確率分布を与えるという意味で、同等のマルコフ政策が存在する。証明は

Puterman[3]134p

参照。分布

q （ h a ^）

^がより一般的な場合は Strauch [6]参照。

　このマルコフ政策は初期状態

x

に依存して決まる（Strauch

［6］ , random semi-Markov policy）。

定理３は、状態を近似していない場合に対してもいえる。この定理３によってマルコフ政策のみを考えて良いことが保証される。

［再帰関係式］

π

をマルコフ政策とすると、次の再帰関係式が成立する。

W W W W W

^（^（i,i,

^π

C）

≡Pr ［ V V V i i ^π ^＞ _－ C ^］ ^＝ Σ

_a

^q ^h （ 0 a ^） Σ

_j

^p ^ij ^a ^Pr ^［ ^V ^V ^V ^j ^j ^π ^' ^＞－ C ' ^］

　　　　　＝

Σ

_a

^q ^h （ 0 a ^） Σ

_j

^p ^ij ^a ^W ^W ^W W W

^（^（

j, _j, ^π _C' ^' ' '

）^）

π '

^は

π

を１期ずらした政策で、

C' ^＝ ^（ C－r ij a ） / β

である。可能な

C

を離散近似しているので、等号は近似での等号である。

　次の記号を定義する定理３

π

を政策とする、そのとき各

x ^∈ S×K

に対してマルコフ政策

π '

が存在して　　

P x π ［ ' X X X t t ^＝ y ^, B t ＝ a ^］ ^＝ P π x ［ X X X t t ^＝ y ^, B t ＝ a ^］

t ^{＝ 0, 1, …．}

ここで

X X X t t

は時点

t

^{における状態、}

B t

は時点

t

において選択される行動である。

(7)

　　　　　　　　　１　

if D ^＝ ^（ C ^－ r ij a ） /

Δ

^（i,C）

^a

^{（ j, D}^{（ j, D}^（^）^） ^）

^≡ ｛

　　　　　　　　　１　

｛

　　　　　　　　　１　

｛

　　　　　　　　　０　^（　　　　　　　　　０　^（i,C 　　　　　　　　　０　^i,C）^（　　　　　　　　　０　^{（ j, D}^）　　　　　　　　　０　^{（ j, D}^（^）^）^{j, D} 　　　　　　　　　０　^{（ j, D}^（^）^） ^）　　　　　　　　　０　^）

｛

　　　　　　　　　０　

｛ ^{if D} ^≠ ^（ ^C ^－ ^r ^ij ^a ^） ^/ ^．

　上の再帰関係式から、決定関数

d d d ^（ t t ^, t ^{＝0, 1,…）}

が現在の状態にのみ依存するときには、行動

a

^を用いたときの状態

（ i ^, C ^）

から状態

（ j ^, D ^）

への推移確率が

p ij a ・ Δ

^（

^a i

^,

C

^）^（

j

^,

D

^）で与えられるマルコフ過程を考えることができる。

x ^＝ ^（ i ^, C ^） ^, y ^＝ ^（ j ^, C' ^） ^, C' ^＝ ^（ C ^－ r ij a ） / β

とする。

１　 if C' ^＞ _－ M

U

U

a

U x, ^x,

U ^y ^≡ ｛

０　 if C' ^＜ M ^,

１　 if C' ^＜ m

L

L a x,y ≡ ｛

０　 if C' C' C' ^＞ ^＞ _－ m

を定義する。

U ^a x,y

は次期に、システムの状態が

U

に入るか入らないかの指標で、入ったら１、入らなかったら

0

である。同様に

L ^a x,y

は次期に、システムの状態が

L

に入るか入らないかの指標で、入ったら１、

入らなかったら

0

である。

（証明）

x ^＝ ^（ i ^, C ^） ^, y ^＝ ^（ j ^, D ^）

^{とする。ここでは}

q h （

0

a ^）

^{を簡単のため}

q ^（ a ^）

^{と書くことにする。}

π '

^は

π

を１期間シフトさせた政策である。

W W W x x ^π ^＝ Σ

_a

^q ^（ ^a ^） Σ

_j

Σ

_D

^p îj â ^・ Δ ^（i,C） â ^（j,D ^） ^（j,D ^） ^（ ^） ^W ^W ^W ^y ^y ^π ^'

　　　　＝

Σ

_a

^q ^（ ^a ^） Σ

_j

Σ

_D

^p ^ij ^a ^・ ^Δ

^（

^a ⁱ

^,

^C

^）^（^）^（^）^（

^j ^j

^,

^D

^）

^・ ^U ^a ^x,y ^・ ^W ^W ^W ^y ^y ^π ^'

　　　　　＋

Σ

_a

^q ^（ ^a ^） Σ

_j

Σ

_D

^p ^ij ^a ^・ Δ

^（

^a ⁱ

^,

^C

^）^（^）^（^）^（

^j ^j

^,

^D

^）

^・ ^L ^a ^x,y ^・ ^W ^W ^W ^y ^y ^π ^'

＋ Σ

_a

^q ^（ ^a ^） Σ

_j

Σ

_D

^p ^ij ^a ^・ ^Δ

^（

^a ⁱ

^,

^C

^）^（^）^（^）^（

^j ^j

^,

^D

^）

^・ ^（1－ Û â ^x,y ^） ^・ ^（1－ ^L â ^x,y ^） ^・ ^W ^W ^W ^y ^y ^π ^'

である。

y ^∈ U

^ならば

W W W y y ^π ^' ^＝ ⁰

^{より最右辺第}

¹

^項は

⁰

^{である。また}

y ^∈ L

^ならば

W W W y y ^π ^' ^＝ ¹

^である。

したがって

W W W x x ^π ^＝ Σ

_a

^q ^（ ^a ^） Σ

_j

Σ

_D

^p ^ij ^a ^・ ^Δ

^（

^a ^i,C

^）^（^）^（^）^（

^j,D ^j,D

^）

^・ ^L ^a ^x,y

定理４

W （

W i π ,

C） ≡Pr ［ V V V i i ^π ＞－ C ^］ ^＝｛マルコフ政策 π

によって

（ i ^, C ^）

^{から出発して初めて}

L

^{に達する確率}

^}

である。

(8)

＋ Σ

_a

^q ^（ ^a ^） Σ

_j

Σ

_D

^p ^ij ^a ^・ Δ

^（

^a ⁱ

^,

^C

^）^（

^j

^,

^D

^）

^・ ^（1－ Û â ^x,y ^） ^・ ^（1－ ^L â ^x,y ^） ^・ ^W ^W ^W ^y ^y ^π ^'

である。

R （i,C） ^a ≡ Σ

_j

Σ

_D

^p ^ij ^a ^・ Δ

^（

^a ^i,C

^）^（

^j,D

^）

^・ ^L ^（i,C） ^a ^{（ j,D）} ^, ，

　　………（2）

Q （i,C） â （ j,D） ≡ p ij a ・ Δ ^（i,C） â ^{（ j,D）} ^・ ^（1－ Û ^（i,C） â ^{（ j,D）} ^, ^） ^・ ^（1－ ^L ^（i,C） â ^{（ j,D）} ^, ^{）………（3）}

と定義する。

R x a

は行動

a

^{のもとで次期に状態}

L

^{に入る確率である。}

また

Q ^a xy

は行動

a

^{の下で次期に状態}

y ^∈ S×R ^－ U ^－ L

^{となる確率である。}

y ／ ∈ ／ ∈ S×R － U － L

に対しては

Q ^a xy ＝ 0

である。

W W W x x ^π ^＝ Σ

_a

^q ^（ ^a ^） ^R ^x ^a

＋ Σ

_a

^q ^（ ^a ^） Σ

_y

^Q ^a ^xy ^W ^W ^W ^y ^y ^π ^'

である。右辺の

W W W y y ^π ^'

を同じように再帰的に展開していくことにより定理の証明が得られる。定理

２より右辺の和は定まる。

（証明おわり）

　定理４は、一部、和が積分になるが、状態を近似していない場合に対しても同様に証明できる。

　定常政策を

f ^∞ ^∞ ^∞ ^≡ ^≡ ^｛ ^｛ f f f f ^, ^, f f ^{, …,} ^{, …,} f f f ^{, … ｝} ^{, … ｝}

と表すことにする。また状態に１つの行動を対応させる決定関数

f

^に対して

f ^（ x ^） ^＝ a

^の時に　　　

R x f ≡ R x a ，

Q xy ^f ≡ Q ^a xy

と表すことにする。

　定常政策

f ^∞

のときには再帰関係式が

W W W x x ^f

^∞

^＝ R x f ＋ Σ

_y

^Q ^f ^xy ^W ^W ^W ^W ^W ^y ^y ^f ^f ^∞ ………（4）

となる。

［推移確率と直接報酬］

　式

（2）

から

（ R （i,C） ^a ） _{（ j,D）} ≡ p ij a ・ Δ

^（

^a ⁱ

^,

^C

^）^（

^j

^,

^D

^）

^・ ^L

^（

^a ⁱ

^,

^C

^）^（^,

^j

^,

^D

^）　………（5）

と書くことにする。はじめのモデルのデータから拡張されたモデルのデータを作成しよう。

　式（3）

（5）から以下のように計算される。

　現在の状態

x ^＝ ^（ i ^, C ^）

^で行動

a

^{をとったとき}

y ^＝ ^（ j ^, C' ^）

^とする。

①

C ^＝ c

0

, c

1のとき

(9)

　ⅰ）

C' ^＝ c

⁰^の

y

^に対して

^（ R x a ））） _y _y ＝ p ij a ，

Q ^a xy ＝ 0，

　ⅱ）その他の

y

^に対して

^（ R x a ））） _y _y ＝ 0，

Q ^a xy ＝ 0．

②

C ^＝ c n

⁺¹のとき、すべての

y

^に対して

^（ R x a ））） _y _y ＝ 0，

Q ^a xy ＝ 0．

③

C ^≠ c

¹

^， C ^≠ c n

⁺¹のとき

　ⅰ）

C' ^＝ c 0

かつ

（ C ^－ r ij a ） / β ＜ c

¹^なる

y

^に対して

^（ R x a ））） _y _y ＝ p ij a ，

Q ^a xy ＝ 0，

　ⅱ）

k ≠ 0 k ≠ 0 k ^, n ⁺¹

^として

C' ^＝ c k

かつ

c k ＜－（ C ^－ r ijiji a ） / β ＜ c k

^＋1 なる

y

^に対して

^（ R x a ）））＝ _y _y 0， Q ^a xy xy x ＝ p ij a ，

　ⅲ）その他の

y

^に対して

^（ R x a ）））＝ _y _y 0， Q ^a xy xy x ＝ 0．

R

^x

^a ^＝ Σ

_y

^（ ^R ^x ^a ^） ^） ^） ^y ^y

^である。

　以上から

　状態空間：

S×K ^，

　行動空間：｛

A A A x x ^： x ^∈ S×K ^｝ ^（ x ^＝ ^（ i, c ^）

^のとき

A A A x x ^＝ A i ），

　直接報酬：｛

R x a ： x ^∈ S×K， a ^∈ A A A x x ^｝，

　推移確率：｛

Q ^a xy xy x ：x∈ S×K ^， a ^∈ A A A x x ^｝

^（ Σ

_y

^Q ^a ^xy ^xy ^x － ^＜ 1 ）

である、マルコフ決定過程を考えることができる。

　１．すべての

x

^と

π

に対して

P x π ［ V ^＞ _－ C ^］ ^＜ _－ ^1。

　２．各

x ^＝ ^（ i, c ^）

^に対して

R x a ＞－ 0

である少なくとも一つの

a ^∈ A A A x x

が存在する。（本稿の場合、

すべての

a ∈ A A A x x

に対して

R x a ＞－ 0

である。）

　１,

２からこのモデルはポジティブ DP（Blackwell ［1］ ,Puterman ［3］ 284p）である。

証明は

Puterman［3］294p

参照。

　したがって、閾値確率基準最適政策を求めるためには、拡張された状態の下での定常政策のみを考えれば良いことになる。また定理

2

から再帰関係式

（4）

の解が求まる

（Kushner[2]120p,Theorem8

参照）。定常最適政策を求める計算が可能である。状態が

（・ , c

⁰

^）

になるとそこでパスがなくなる。

c

⁰

^＜ m

であるので、はじめから閾値

C ^＝ c

⁰は考える必要がないので、状態空間を

S×K ^＋

^としてよい。

定理５

状態空間

S ^× K

は可算であり、またすべての

x ^∈ S ^× K

^{とすべての}

a ^∈ A A A x x

^に対して

R x a ＞－ 0

であるから、最適政策が存在するならば、定常な最適政策が存在する。

(10)

Ⅲ 終わりに

　White

［7］

は元のシステムが有限状態空間、有限行動空間で、閾値確率基準のモデルを考えている。

また最適定常政策の存在を閾値

C

を離散にせず証明している。本稿では、可能な閾値

C

^を離散化することにより、閾値確率基準マルコフ決定過程を、状態が可算無限のポジティブ

DP

に帰着させている。閾値の離散化は

White［7］でも、計算上必要になるということで、最後に簡単に触れて

いる。連続無限な状態からみると、本稿では

ε -

最適定常政策を考えていることになる。船木も［8］

第Ⅵ章で、元の状態空間も行動空間も共に有限な閾値確率基準のモデルを述べた。そこでは本稿の定理２に相当する仮定をおいた。本稿の動機はその仮定をなくすことであった。

参考文献

［1］ D. Blackwell, Positive dynamic programming, in Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1 (University of California Press, Berkeley) pp. 415-418 Mathematical Statistics and Probability, Vol. 1 (University of California Press, Berkeley) pp. 415-418 Mathematical Statistics and Probability,

(1967).

［2］ H. Kushner, Introduction to Stochastic Control Theory (Holt, Rinehart and Winston, New York, 1971).

［3］ M. L. Puterman, Markov Decision Processes, (John Wiley & Sons, New York, 1994).

［4］ Linn, I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, John Wiley & Stochastic Dynamic Programming and the Control of Queueing Systems, John Wiley & Stochastic Dynamic Programming and the Control of Queueing Systems, Sons, New York, 1999).

［5］ M. Sobel, The variance of discounted Markov decisions processes, J. Appl. Probab. 19, 794-802 (1982). J. Appl. Probab. 19, 794-802 (1982). J. Appl. Probab.

［6］ R. Strauch, Negative dynamic programming, Ann. Math. Stat. 37, 871-890 (1966). Ann. Math. Stat. 37, 871-890 (1966). Ann. Math. Stat.

［7］ D. J. White, Minimizing a Threshold Probability in Discounted Markov Decision Processes, J. Math. Anal.

Appl. 173, 634-646 (1993).

［8］船木洋一　割引基準マルコフ決定理論（東北大学博士論文）(1981).

閾値確率基準マルコフ決定過程とポジティブ DP