政 策 反 復 法 に つ い て

政 策 反 復 法 に つ い て

奥 田 英 輔

一

オ ペ レ ー シ ョ ン ズ ・ ‑ サ ー チ ( O p e r a t i o n s ‑ R e s e a r c h )   に お い て 直 面 す る 多 く の 問 題 に お い て は ︑ 普 通 ︑ 系 は 確

率的・決定論的特徴をもつ︒このような望ロには︑問題のモデルは︑全‑複雑で解析的に取‑扱いにぐい︒ベルマン

(Be︼︼man)ホワード(Howard)によって,このケースの研究がなされて︑問題がかなり解決されている (cO

旧的

しかし︑ホワード(9)においては︑問題が単純化され過ぎているように思われる︒現実に適用する場合に︑その

範囲が狭‑な‑︑また興味のある性質が︑そがれる可能性が出て来る︒

また︑彼の論文では︑具体例(玩具製造屋の例)に︑不適切で︑暖味なところがある︒そこで︑この小論では︑適

切な具体例を述べて︑さらに︑ホワードの問題を少し一般化して︑解答を予想の形で示した︒

二

マルコフ過程(Markovprocess)は︑複雑な系の研究におけるモデルとして有用である︒マルコ過程の概念は︑

一九〇七年に︑最初︑AAフマルコフ(Markov)によって作られた︒それから︑年々︑著名になって行った︒基礎

°    °

経 営 と 経 済

四

O 

的研究の完成は︑

一 九

三

0

年 代 に コ ル モ ゴ ロ フ に よ っ て 完 成 さ れ

︑ ダ ブ リ ン ( 口

︒

︒ ロ ロ )

︑ ド

l

ブ

( ロ

g t )

によって重要な貢献がなされた︒現在のマルコフ過程の理論の概要は︑

( 間

三 日

︒ 問

︒ 円

︒ ︿

)

( 7

﹀

に述べられている︒

高々可算個の状態に︑

トコ

CJ.コ

、 .

と審号がつけられているとしよう︒一つの系を考え︑それが前述の状態のどれかにあるとしよう︒離散的な︑とびと

びの時間において︑系は一つの状態から他の一つの状態に推移するものとする︒

Ms

ur

‑‑

. 

を系によって占有せられた状態の系列だとする︒ 九は最初の状態であり︑

九 は

第

n

回目の推移の後に系の占める状態

で あ

る ︒

すべての有限個の状態の系列

Mo wu rw

・ ・ : ・

‑w M

内 ロ

に 対

し て

︑

同

M

︹

M

内 ロ 土

¥ M

内

g u r ‑

‑ : : ‑

M

ロ )

ー 可

︹

U

内 ロ

+ 目

¥ u 内 し

ロ 10w プ N

( N

・ 一 )

が成立するとき︑系はマルコフ過程をなすという︒

マルコフ過程とは︑次に起る状態の推移の条件付確率が︑系によって占められた直前の状態にだけ関係

す な

わ ち

︑

の条件付確率は︑推移確率といわ

れる︒乙れは

n

には関係しない︒今後は︑状態の個数が有限伺であるような︑有限マルコフ過程だけを考える︒そし し︑その状態に入る以前の系の歴史には︑関係しない過程である︒方程式

(N

・ 一 )

て状態の呑号を

ァ ド

・

::

‑w

Z

という整数で表わす︒状態・ーから状態 j への推移の確率を︑

司

︹ M F + H I

い

¥ M

内 ロ U 日︺

I l  

旬

グ ] U

プN

i ‑

‑ ‑

w Z

ロu

o w

プ

N

・

によって表わす

D

系は︑次の推移において︑どれかの状態にならなければならないから

1 1   M Z 

U  1 1  

( N

・ _M

)

で あ

る ︒

( N

‑ M )

は︑系が︑そのまま状態・ーに留まったときの確率九を含む︒引は確率だから

C M E

M

川

で あ る

D

具体的な例を述べて話を進めていこう︒以下において述べる具体例は︑ホワ!ドの著書

( 9 )

具製造屋の例を筆者が改良したものである︒ に述べられている玩

既に定義したような︑離散的なマルコフ過程の簡単な例は映画館経営者の場合に考えられる︒映画館経営者は︑常

に︑翌週︑彼の映画館で上映すべき映画の選択に頭を使っているとしよう︒彼は次の

2

つの状態のいずれかにある︒

第

1

の状態は︑彼の映画館で︑現在上映している映画に︑大きな人気があり︑大勢の観客がある場合である︒第

2

政 策

反 復

法 に

つ い

て

四

経 営 と 経 済

四

の状態は︑現在上映している映画に人気が無く︑観客が少数しかない場合である︒そこで︑次のように仮定する︒彼

が第

1

の状態にあるとき︑翌週の終りに第

1

の状態にそのまま留まる確率が印パーセントである︒即ち︑第

2

の状態

に推移する確率が切パーセントである

D

これは︑彼の映画館そのものが人気を獲得した為である︒彼が第

2

の状態に

あるとき︑一週間後に新しい映画を上映して︑第

1

の状態に推移する確率が%であり︑第

2

の状態にそのまま留まる

確率が%である︒これは︑彼の映画館そのものが人気を失った為である︒以上から

司 ト

・

ト ー4 H

叫

J F H

71

ムナ

ア同日中

である︒行列の形に表わせば

可

1 1  

f

、 一 I " d  

」ーノ

ω)'0  11'0卜

ω[∞ 

で あ

る ︒

対応する系の推移図表は︑状態と推移確率をグラフの形に表わして︑図 ω

・ ↓

の よ

う に

な る

︒

図 ω

・ 一

推移行列

P

は︑このようにして︑ マルコフ過程を完全に記述する口乙の行列の行の和はーになる︒そして︑その各

元素はーより大でない非負の数である︒このような行列は︑確率行列(ωgoEω己目︒自己止と

マルコフ過程に関するすべての問題に解答を与える︒例えば︑映画館経営者が︑最初に第

1

の状態 とよばれる

D

我々はこ

の行列を用いて︑

にあったとして︑ n 週間後にもやはり第

1

の状態にある確率は幾らであろうか︒この問題および他の問題に解答を与

ロ V

︒ )

^{えるために︑確率}

3(

ロ )

の推移の後に︑この系が状態・ーを占める確率である︒この定義から

を 定

義 す

る ︒

即 ち

︑

ロー︒としたときの系の状態が知られているとき︑

n

回(ただし︑

i i

  1 : ‑ 1  

z 

~

〆 戸 、 、

、 ロ ‑ "

( ω

・ 一 )

で あ

り ︑

叶 吋

} (

ロ 十

︼ )

i

i   1 : ‑ 1  

z 

N 

/ 問 、 、

、

口

‑ "

司

DH Ow

‑

( ω

・ _N

)

である

D

叶 吋

( ロ

) は

成 分

と し

て

3(

ロ )

を も

っ

N

次元行ベクトルであると定義する︒そうすると︑

司 (

ロ 十

︼ )

日 刊 ( ロ )HM

ロ

U O

( ω

・ ω )

と設かれる︒故に︑

叶 吋

( 一

)

u q ( O )

司

叶 吋

( N )

H N ( 一 ) 司 H N ( O ) H V U

H

円

( ω )

日 吋 吋

( M ) 阿

M u q ( O ) H M U

政策反復法について

四

経 営 と 経 済

四

四

で あ

る ︒

一 般

に ︑

q

(

ロ )

u q

ロ ( ︒)司ロ

1 0

( ω

・ム

)

である︒このようにして︑ n 回の推移の後に︑系が各状態を占める確率向(ロ)を見付けることは︑司令)

に ?

を 一

束

ずることによって可能である︒

これらの乙とを︑映画館経営者の場合に例をとって説明しよう︒映画館経営者が最初成功した映画をもって出発し

たとしよう︒そうすると︑

q H ( O )

日 一

である︒そして︑

可 ♂

( O ) U O

である︒即ち

可 吋

( O )

日

f

一

、

・ ー ー 晶

、 .

C

コ

L J  

である︒それ故方程式

( ω

・

ω )

から

叫吋(一)日刊

( O ) H M H

r‑¥ 

‑ ー 晶

、 .

C コ

L J  

ωIN  Nl一

切|ωNl~

となる︒すなわち︑

判 円 ( 一 ) 日

で あ

る ︒

つ ま

り ︑

一週間後には︑映函館経営者は成功と不成功であることが同程度確からしい︒二週間後には︑

刊 吋

( N )

日 刊 ( 一 ) 同

M H

となる︒したがって︑

司

( N )

日

ω[N  N[

^→

^a  ω￨ωN

ト

となる︒故に映画館経営者は僅かばかり不成功であることが確からしい︒三週間後には︑

司

( ω )

日 刊

(M﹀

] V

H

『¥コ

1 ‑ ‑ "

C

コ

1‑‑"

C

コ

1‑‑‑

~

となるから︑二週間後のその値から少しばかり変化している︒

政策反復法について

四

五

経 営 と 経 済

であるから︑司

( ω )

は直接に

判 吋

( ω ) 1 N ( O ) 司 ロ

からも求められることは注意しなければならない︒ 四 六

表 ω ・一に示されるように︑

3(

ロ )

を

n

の関数として計算すると興味ある傾向が現れる︒

制

ω

・ 一

一 口

H

一 一 一 一 32

一 一 一 一 25

一 一 一

恰 も

︑

n

が非常に大きくなるに従って︑

3(

ロ )

C

コ

0

・印

C

コ

︒・印

が不成功な玩具で出発したならば︑

可吋

H ( O ) H O

か つ

︑

可吋

U ( O ) 1

一

は

% 

に 一 一 一 一 一 ‑

; : ; t  

ロ

は

l

一一一一一一

% 

l 乙

近

イ 〉

て 行 く よ

で

つ

あ る

映

画 館 経 営 者

トJ

0

・ム 印

0 ・ m

印

であり︑そのときの

3

官)に関する表は表

ω ・

N

で あ る ︒

淵ω ・

N

ロ

< = >  

肖 同 ( ロ )

0 ・ A

C

コ

対 同 ( ロ )

0

・∞

ト

、 コ

0 ・

h主

0

・日 一

亡ムコ

0

・ム

h

昂

0

・印印印

巳ムコ

0

・ムムム

0

・印印白

0

・ムムム印

0

・印印印印

ヰ』

0

・ム ム

h

玄

0

・印印印∞

...t. 

仁)1

0

・ムムム

K 5

0

・印印印印印

(Jl 

0 ・ _A

A A

h 芋

0

・印 印同 月一

∞

こ の

場 合

は ︑

n を大きくすれば

3

( ロ

) は

% に

近 づ

き ︑

3(

ロ )

は %

に 近

づ く

︒

し た

が っ

て ︑

推移の回数を大きく

すれば︑各状態を占める確率は︑系の出発する状態に独立であることがわかる︒多くのマルコフ過程はこの性質を一示

す︒完全エルゴ

l

ド的マルコフ過程とは︑出発したときの状態に極限の状態の確率分布が無関係であるようなマルコ

フ過程をいう︒系がひとたびある状態の集合にはいれば︑決してその集合から出ないような最小の集合をエルゴ

l

ド

的集合 ( O

円四二日のお伴)

というが︑このエルゴ

l

ド的集合がただ一つあって︑他の状態はすべて不安定状態の場合に︑

過程は完全エルゴ

l

ド的となる︒ここの議論は

(6

︑ロ)を参照されたい︒推移の回数が大きいとき︑状態を占める

確率が系が出発するときの状態に関係するようなマルコフ過程の議論はここでは割愛する︒

完全エルゴ

l

ド的マルコフ過程の場合に︑引として推移の回数が大きいとき系が i 番目の状態を占める確率とする口

成分?伊}もつ行ベクトル Z は︑このようにして︑

n

が無限に大きくなったときの

q (

ロ)の極限である︒方程式

( ω

・ ω )

からずか従う万程式として︑

o:t 

1 1  

司

トU

( ω

・ 印 )

が当然なりたつ︒また︑勿論︑ 万の成分の和は

1

でなければならないから

1 1   t

、 I j

z 

司

1 1  

( ω

・ ∞ )

で あ

る ︒

万程式

( ω

・ 印

) お

よ び

( ω ‑ m

)

を用いて極限状態の確率を見つけることができる︒映画館経営者の例においては︑万

程式

( ω

・ 印

) か

ら

政 策

反 復

法 に

つ い

て

四

七

経 営 と 経 済

四

/i、

H ~

I I  

NI‑‑

H ~

+ 

ωIN 

~

であり︑また

3 1

1

_叶

3

ω￨ω 

+ 

~

である︒万程式会・∞)を用いて

qH+qul 

である︒この

3

つの方程式を︑未知数町︑ 同 に つ い て 解 け ば ︑

~

∞ ￨ 与

ω 

3 1

叫

J l

と な

る ︒

四

N

個の状態をもっマルコフ過程を考えよう︒系が状態・ーから状態 j に推移するとき︑刊の報酬(円︒当日仏)がある

と す

る ︒

町 宇

伊 }

状 態

・ ー

か ら

j

へ の

推 移

に 伴

う 報

酬 と

い う

︒ 元

古 来

日 中

伊 }

も つ

行 列

同

I I  

( 片 山 } )

を報酬行列という︒

このようにすれば︑マルコフ過程は状態から状抱へ推移するに従って報酬の系列をもっ︒報酬はマルコフ過程の確

率関係によって規定される確率分布をもっ確率変数である︒

J J (

ロ)は︑系が現在状態

i

にあるとき︑次の

n

回の推移で得られることが期待される全報酬であると定義する︒

そうすると︑乙の定義から次のような循環関係が得られる︒

〈

〆ー、

、ロJ

1 1  

!1'‑1z 

可 1¥ 

円

+ 

〈

〆ー、

ロ

、

ー・園

J

'L.J 

ゲ ︺

H

ア ド

: ‑ w z

ロ

H プ

N

( ム ・ 一

)

方程式

( み ・ 一

)

は次のような形に苦かれることは注意しなければならない︒

〈

〆F

、 、

、ロ^J

1 1  

!1'‑1z 

ト " 0

"1 

τ+  . 1'‑1 z 

司 く

f

、 町

ロ

、

炉・園

^J

︺u

一 ︑ ド

: ‑ w z

ロ

H

プ

N

( ム ・

M)

乙こでもとして次のような室を定義する︒

円 山 即 日

τ.

上 ‑ . . 1

z 

匂

"1 

] u

‑ W

N W

‑ :

: ‑

w z

 

( 品 ・

ω )

すると︑方程式会・

3

は次のような形になる︒

3

(ロ

)HP+

i i  

1'‑1 z 

司

〈

〆'句、

ロ

、ー 占ー〆

円 H

プ ド

: ・

u z

ロ

u ‑

W N

W ‑

:

( ム ・ ・

み )

もは︑状態・ーにあるとき︑次の推移で得られる報酬の期待値であると解釈される︒方程式会・一)を方程式公・舎

のように書き換えると︑系の報酬の期待値を決定するためには︑行列

P

と行列

R

の両方を指定することは不必要であ

る 乙 と が わ か る

︒ 行 列

P

と

N

個 の

h

刊を成分としてもつ列ベクトル

q

を指定するだけで十分である︒方程式

︐ ︼ ︑ ︑

︐ ﹄ ︑

み

i

ふ

J

政 策

反 復

法 に

つ い

て

四

九

経 営 と 経 済

五 O

( P A )

は次のように書かれる︒

J 1 (

ロ

) 1 ρ +

官 官

l

一 )

ロ

H プ

N

(kF ・ 印 )

乙 乙

に ︑

ぐ (

ロ )

は

N

個

の

J J (

ロ)を成分としてもつ列ベクトルである︒

映画館経営者に例をとって考えてみよう︒以下に述べる具体例は︑特に筆者が︑ホワ

l

ド

( 9 )

に述べられている

玩具製造屋の具体例を工夫して改良したものである︒ホワ

l

ドの例では︑推移に伴う報酬という概念が出て来るが︑

これを現実と照し合せたとき︑どのように解釈すればよいのかわからない︒現実には系の推移に伴う報酬ではなくて︑

系が現在ある状態に留っている乙とによる報酬である︒推移に伴う報酬とは︑系が状態・ーから状態 j へ推移したとき

の

2

つの状態に留っていたことによる報酬の平均であると考えられる︒そ乙で︑次のような見方をする︒

まず次のように︑映画館経営者の行動を明確に定義する︒彼の経営している映画館は︑毎日休むことなく映画を上

映しており︑映画の上映時間は︑午前一

O

時から午後一

O

時までの十二時間である︒そして︑新しい映画の上映は日

曜日から行うものとする︒勿論︑彼が営業を開始した第一週も日曜日から始まるものとする︒彼は決算を毎週水曜日

の午後四時に行うものとする︒水曜日の午後四時に決算を行うのだから︑その週の日曜日の午前一

O

時に︑新しい映

画を上映し始めてからの四二時間の営業成績と︑先週の水曜日の午後四時から土曜日の午後一

O

時まで古い映画を上

映していたときの成績の合計が決算されることになる︒それを︑先週の状態(成功であったか不成功であったか)か

ら︑今週の状態への推移に伴う報酬ということにする︒このように映画館経営者の営業活動を明確に定義しておいて

次の議論に進む︒

映画館経営者が成功した映画をもち(系が状態ーにあり)︑そして︑翌週にも成功した映画をもっとき(系が状態

ーから状態

1

に推移するとき)︑彼は

9

ドルを稼ぐ︒つまり︑このときの推移に伴う報酬は

9

ドルであるとするロし

h は

9

に等しい︒もし︑不成功な状態から不成功な状態に推移するとき(状態

2

から状態

2

へ)︑映画館

経営者は

7

ドルの損をする︒つまり︑

た が

っ て

︑

同

1 1  

ー 、 」

である︒最後に︑不成功から成功へ︑または成功から不成功へ推移するときは︑

3

ドル稼ぐ︒つまり︑

吋

U

H u p u u ω

である︒こうであると報酬行列は

tj 

1 1  

/一一一一一一¥

ι

。

C.J.コ

\、一ー一一一一ー一~

C.J.コ

ー 、 」

で あ

る ︒

先 に

︑

P 

は 次 の

￨13 

よ

/ 一 一 一 ¥ あ

C

コ

C

コ

コマ

ヰ 』 印 T

こ

司

C

コ

c

コ

(.0 

(刀

¥』一一一一一一一/'

方程式会・

ω )

から

ρ  1 1  

ト 刀

同 1 1  

/一一一一一¥

σ

コ

¥一一一一一一ノ

cρ 

と な

る ︒

q

ベクトルを見れば︑映画館経営者が成功した映画をもてば︑翌週には期待値として

6

ドルを稼ぐことになる︒も

政策反復法について

五

経 営 と 経 済

五

し︑彼が成功した映画をもたなければ︑翌週には期待値として

3

ド ル の 損 を す る ︒

映画館経営者が

n

週間に稼ぐ収益の総量を知るにはどうしたらよいだろうか︒乙の問題には︑方程式(デム)また

は方程式会・印)が直接に応用されるが︑しかし境界値

3(

︒)の組が指定されなければならない︒乙乙では簡単の

た め

J J (

︒ ) は す べ て

0

に 等 し い と す る ︒

方程式会・

A )

を用いれば表子一が得られる︒

叫 州

kF

・ 一 ロ

C

コ

N 

w 

..t.. 

C

コ

1 0

・， . 

t

刀

l ι

Jl (J1 1ι刀

ι

刀

l ι

Jl

cn 1ιn 

一一一

ιn 

︿

H (

ロ )

C

コ

cn 

吋

‑ u

∞・印印∞・印印印

︿ 同 ( ロ )

C

コ

w 

lM ・ A

! ? h

_玄

1 0

・h

玄 品

映函館経営者は四週間に︑ もし彼が成功した映画を最初にもてば∞

‑ g ω

ド ル

稼 ぎ

︑

n

を大きくすれば 不成功な映画をもてば 0

・ 主 ム

ドル損をする︒映画館経営者の場合︑

JJ(

ロ

) l d (

ロ )

は 叩

に 近

づ き

︑

JJ(

ロ

) 1 3 (

ロ

lc

および

JJ(

ロ)

!♂ (ロ

lc

はーに近づくことが証明される︒

n

が大きい場合︑興味があるのは増分

および JJ(

ロ

)

1 3

ロ

(

ー一

)

で あ

る ︒

JJ(

ロ

)

1 2

ロ

(

ー一

)

映画館経営者の例では

可

1 1  

/ 一 一 一 『 ¥

C コ C コ

ヰ ( J 1

同 1 1  

/一一一一一一「

で あ

っ た

︒

C

コ C コ

五

σ (J1 

¥ 、 一 一 一 一 一 一 一 ー ‑ ‑ ‑ ‑ ‑

ι。

‑‑J  ひコ

¥ 一 一 一 /

今度は︑映画館経営者が異なった行動をして︑上の確率分布とか報酬を変化させる例を考えよう︒例えば︑映画館

経営者が成功した映画を持っているとき︑広告をして︑不成功な映画をもっ機会を減少させることができるとしよう︒

し か し

︑ 広 告 賀 の た め に

︑ 一 般 に 減 少 す る も の と す る

︒ た と え ば

︑ 広 告 を し た と き

︑ 状

態ーからの推移の確率分布は

︹︼

VH})

u ( 0

・

∞

政 策

反 復

法 に

つ い

て

C

心

一週間に期待される利益は︑

0 ・

N

︺

五

経営と経済

五

四

r‑‑¥ 

ド

t

ド4

~.

、ーーノ

であるとする︒そして︑それに対応する報酬の分布は

r 、 一 中 h

ヰ』

' ‑ J  

である︒映画館経営者は状態ーにあるとき

2

つの手段をもっ︒すなわち︑広告をしないか︑広告をするかである︒乙

れらの手段を︑それぞれ手段

1

および手段

2

という︒各手段は︑状態ーから推移するときの報酬および確率の分布を

もっ︒手段を示すために︑肩に添数を書くことにする︒状態ーにあるときの手段

1

に 対

し て

は ︑

， ‑ 、

...

司

..... 

' ‑ J  

および ︹ 0 ・

ω

0

・ 印 ︺ ハ 吋

f ︺日ハ∞

である︒状態ーにあるときの手段

2

に対しては

r‑‑¥ 

ト " 0

.... l~

、 ‑ . f

および

r‑‑¥ 

円 ト~ l~

~.

'‑ーノ

で あ

る ︒

ιρ 

' ‑ J  

( 0

・ ∞

0

・

N ︺

r‑‑¥ 

...p... 

ヰ』

' ‑ J  

系が状態

2

にあるときの手段についても考えられる︒ (映画館経営者が不成功な映画をもっとき)︒目的を追及す

るための出費は成功的な映画をもっ確率を増加させるだろう︒しかし︑反面状態

2

にある費用を増加させもする︒状

( 可 凶 } )

態

2

にあるときの以前からの手段を手段

1

とする︒手段ーでは

0 ・ ∞ ︺

︹ 0

・ ム

および

︹同

u ‑

︺

r‑¥ 

c ; . コ

であった︒目的を追及するために努力するという手段を手段

2

と す る ︒

ー 、 」

' ‑ ‑ ‑ 1  

手段

2

で は

r‑¥ 

句

'‑‑‑1 

および

︹円 U}

︺

r‑¥ 

.目白」

︹ 0

・吋

0

・

ω )

ー 一 ∞ ︺

である口そうすると︑状態

2

にあるときの手段ーに対しては

︹

M M 2

︺ 日

︹

0 ・ k 干

および 0

・ ∞ ︺

︹円凶}︺ U ハ ω

である︒状態

2

にあるときの手段

2

に対しては ω 

(HMMH}

︺ u ︹ 0

・J

﹁

および

︹C J

︺

1 2

で あ る ︒

l

吋

︺ 0

・

ω

︺

l ‑

∞ ︺

N

個の状態をもっ系に対する手段の概念は図

ω

・一に示されている︒このダイヤグラムでは︑第

1

の状態に対して︑

2

つの手段がある︒第

1

の手段

( 7 3

についてみれば︑状態ーから状態ーへの推移は︑確率叫によって行なわれ︑

五 五

政策反復法について

経 営 と 経 済

J信

1

i国

2

図

5.1 

i=20 

J国 3

Oj=N 

五 六

状態ーから状態

2

へ の 推 移 は ︑ 確 率 1M に よ っ て 行 わ れ ︑

P 

ーから

3

への推移は︑確率ゐにより︑以下順次この

P 

ように行われる︒とれらの推移に伴う報酬は

円 円

w

円 切 :

・

・ 円

H U H ω H Z  

である︒第

1

の状態における第

2

の手段

( w

u N

)  

I 乙

i 

=30 

つ

t " ¥   て み 司 れ

=ω

ば

ト1:1

5ta 

' " t : 1  

Z

③ ・

ト1:1

z 

そ し て

i 

=:~O

カ f

そ れ ぞ

れ

H円 一

確 に 山 率 円

と

Z U

報 酬同門

u

で ヘ 目 あ る

ド

t

zu 

図

ω

・ 一

で は

︑ 第

1

の手段に伴う推移は棒線で︑第

2

の手段に伴う推移は点線で示してある︒各状態における手段の

個数は︑有限個でなければならないが︑ある状態における手段の個数は︑他の状態におけるそれとは異なってもよい

ことは注意しなければならない︒

各状態でとる手段を定めることを決定

の例の場合︑大きな

n

あることが証明される︒

(

ロ

W

N )

について報酬を最大にする手段は︑

2 2 2 Z

ロ﹀という︒すべての決定の集合を政策

状態

1

においても状態

2

においても︑手段

2

で

. J . . . . o ，  

ノ、

( 唱

︒ ロ

の 可

) と

い う

︒ 我

々

N 個の状態をもっ完全エルゴ

l

ド的マルコフ過程を考えよう︒その推移行列は

P

であり︑報酬行列は

R

である︒過

程は︑非常に大きな回数推移をし︑我々は︑過程の儲けに興味をもつものとしよう︒期待される儲けの総長は︑系の

推移の総数によって決まり︑したがって︑問題とする量は

1

回の推移当りの儲けの平均量ということになる︒乙の呈

は︑前に述べたように︑推移の回数が大きいときは意味をもっ量である︒乙の呈を過程の利得(向丘ロ)という︒

このような過程が幾つかあり︑推移の回数が大きいとき︑最も有利な過程を選ぶには︑各過程の利得を計算して︑

それを最大にするものを選べばよい︒その計算は理論的には可能である︒

図

A Y

2

個の手段を︑第

41

の状態では 個の状態の場合︑つまり第 は

5

‑

で は

3

個︑第

3

で は

2

個︑第

4

で は

1

個 ︑

図? 一

.0 

O' 戸 印

、 .

印 可

凹 ]

討 3

詫 慌

第

5

で は

5

個の手段がある場合を示す︒配置の前面

は︑各状態における第

1

の手段を示し︑第

2

行は各

状態における第

2

の手段を示し︑以下順次につづく︒

X

は各状態における選ばれた手段を示す︒このよう

にして選ばれた手段はその状態に対する決定といわ

れる︒それは最早︑ n の関数ではない︒

X

の 集

合 ︑

または︑決定の集合は政策といわれる︒

政策の選択は︑系の運用を規定する報酬をもった マルコフ過程を決定する︒図示されている政策は︑第

4

の状態においては第

1

の手段を︑第

2

︑第

3

の状態において は 第

2

の手段を︑第

1

および第

5

の状態においては第

3

の手段をとる︒政策をベクトル d で示すことにする︒

つ ま

り ︑

政 策

反 復

法 に

つ い

て

dは各状態において選択された手段の荘号を表わす数をその元とするベクトルである︒

五 七

こ の

場 合

に は

︑

経 営 と 経 済

五 八

~

/ 、 、

。コ‑‑"卜、コト、コひコ

¥ /  

利得または推移

1

回当りの平均収穫量を最大にする政策を最適政策という︒ここで︑すべての政策は完全エルゴ

l

ド的であると仮定する︒図∞・一に示された問題においては

占』

× 

ιρ 

×  ト

。

× 

× 

仁刀

日 一 一 ︒

だから却個の異なる政策がある︒最大の利得をもっ政策を見つけるために︑これらの政策の一つ一つについてその利

得を計算すればよいということが考えられる︒ m 個ばかりの政策については︑それは困難ではないが︑政策の個数が

非常に大きいときには︑そのような方法では間に合わない︒例えば︑日個の状態と︑各状態において日個の手段があ

る 場

沿 は

︑

ω o g ‑

‑ o z

個の政策があることになる︒このような場合には︑電子計算機によっても計算し尽くせない︒

し た

が っ

て ︑

. ζ

のような場合に︑最適な政策を計算する方法が考えられている (9) ︒そのような方法を政策反復

法 (

句 ︒

︼ 問

︒

U

1E

OB

Eg

BE

Z

品

) と

い う

︒

映画館経営者の場合︑各状態において

2

つ の 手 段 が あ る ︒

すなわち︑成功した映画をもっ場合に広告をしないか︑または広告をするかである︒また︑不成功な映画をもっ場

合に広告をしないか︑または広告をするかである

D

広告をしない手段を手段ーとし︑広告をする手段を手段

2

と す

る ︒

そうすると︑第

1

の状態にあって︑広告をしない場合の推移確率と報酬は

( 同

v w

司 ) ( 円

w

吋 )

となる︒第

1

の状態にあって広告をする場合の推移確率と報酬は

( 同

ν w

司 ) ( 円 切 片 )

となる︒第

2

の状態にあるときも同様に広告をしない場合は

( H M W 司 ) ( 円 噂 円 )

であり︑広告をする場合は

( 司

i;

可

ta 

、.../

〆 目 、 、

ド

t

l .

  同 t~

、 .

円

" 

l;;ω 

、目〆

で あ

る ︒

以上に加えるに︑映画館経営者の場合︑次のような例について考えてみよう︒広告をしなくて︑次の推移の後︑広

告をする坊合は︑広告の固定資

(2 5B

岳民間︒)が必要となる︒広告をしていて︑次の推移の後︑ 広告を止める場

合は︑その固定資が無駄になるであろう︒広告をしていて︑次の推移の後でも︑広告をする場合︑または︑広告をし

ていなくて︑次の推移の後でも︑広告をしない場合は︑固定資は必要がないと考えられる︒この例では︑手段の変更

に伴う支出を考えているのである︒つまり︑手段の変更による摩擦を考えているのである︒

U1

1

を ︑ 状 態 ・ ー に あ る と き 第 k 番目の手段を用い︑次の推移で状態jに移って︑そ乙で第 l 番目の手段を用いたと

きの固定資どとする︒つまり︑手段の変更による摩擦によって生じた固定賀だとする︒

映回館経営者の場合︑ 成功した映画をもっているとき (つまり状態ーにあるとき)︑広告をしなくて︑ (昨日一)

翌週にも成功した映画をもち︑かつ広告をしないとすると︑そのときの広告の固定資はいらないと考えられるので

政 策

反 復

法 に

つ い

て

五 九

経 営 と 経 同 済 日

だとする

D

映画館経営者が成功した映画をもっているとき︑広告をしなくて︑翌週にも成功した映画をもち︑広告を

するとすれば︑そのときは︑広告の固定費が必要だと考えられる︒すなわち

同

V v O

である︒映画館経営者が成功した映画をもっているとき広告をして︑翌週にも成功した映画をもち︑広告をしない場

合は︑広告の固定費が無駄になると考えられる︒すなわち︑

同

V v O

だとする︒映画館経営者が成功した映画をもっているとき︑広告をして︑翌週にも成功した映画をもち︑広告をする

場合は︑広告の固定費は必要がないと考えられる︒すなわち

向 日

︒

だとする︒映函館経営者が不成功な映画をもら︑広告をしなくて︑翌週には成功した映画をもら︑広告をしなければ︑

広告の固定費は必要がない︒すなわち

同

1 0

である︒映画館経営者が不成功な映画をもち︑広告をしなくて︑翌週には成功した映画をもち︑広告をするとすれば︑

広告の固定費が必要になる︒すなわち

同

V v O

六 O

C

コ

である︒映画館経営者が不成功な映画をもち︑広告をして︑翌週には成功した映画をもら︑広告をしなければ︑広告

の固定資が無駄になる︒すなわち

同

V v o

である︒映画館経営者が不成功な映画をもち︑広告をして翌週には成功した映画をもち︑広告をする場合は広告の固

定資が不必要である︒すなわち

同 日

︒

である︒映函館経営者が成功した映画をもち︑広告をしなくて︑翌週には不成功な映画をもち︑広告をしない場合は︑

広告の固定資はいらない︒すなわち

向 日

︒

である︒映画館経営者が成功した映画をもち︑広告をしなくて︑翌週には不成功な映画をもち︑広告をする場合には︑

広告の固定資が必要になる︒すなわち

H U  

同

V v O

である︒映画館経営者が成功した映画をもち︑広告をして翌週には不成功な映画をもち︑広告をしない場合は︑広告

の固定資が無駄になる︒すなわち

同

V v O

である︒映画館経営者が成功じた映画をもち︑広告をして︑翌週には不成功な映画をもら︑広告をする場合は︑広告

の固定資は不必要である︒すなわち

政 策

反 復

法 に

つ い

て

ー‑L・ / 、 、

経 営 と 経

同

済

ー

である︒映画館経営者が不成功な映画をもち︑広告をしなくて︑翌週にも不成功な映画をもら︑広告をしない場合は︑

‑L.. 

ノ、、

C

コ

広告の固定資は必要がない︒すなわち

同

1 0

である︒映画館経営者が不成功な映画をもら︑広告をしなくて︑翌週にも不成功な映画をもち︑広告をする場合は︑

広告の固定資が必要になる︒すなわち

同

V v O

である︒映画館経営者が不成功な映画をもち︑広告をして︑翌週にも不成功な映画をもち︑広告をしない場合は︑広

告の固定資が無駄になる︒すなわち

同 リ

vo

である白映画館経営者が不成功な映画をもら︑広告をして︑翌週にも不成功な映画をもら︑広告をする場合は︑広告

の固定費は必要がない︒すなわち

ω ω   向 日

C

コ

で あ

る ︒

uf

に数値を与えて︑色々な具体例について研究してみれば興味のある結果が得られると思うが︑その問題は︑こ

u

こ で は 省 略 す る ︒

そこで推移の回数

n

を非常に大きくした場合に︑ n の関数としてではなく︑各状態に固定した手段として︑つまり︑

図 ∞

・

N

U

叫 問 削 討 中 国 制

︿

NP ‑ 叩

苦汁 阿片 滅一

nd

rJ

パ

δ

H J

甘

r 1

円 門

ρ司

問中

田﹁

Jパ

z  m + J J H ρ F +

し 円 切 乙

︿ 即 日

H

プド :・ :・

‑ z

ゅ ・

︿ 出

H O

什 ﹁

ペ ・

J

﹁

え パ

83

討

1円

qE nd FJ

ペ 蔚

︿ ︒

↓ 

開河 泊四 同知 Lr

ー ホ

υ¥

前 話 路 一

nd

FJ

パ

zw‑w  A

・

+ L

門司・・三

+NHι

・・

同・

. H

戸 ニ

]H‑M

︼ ]

中知汁一円叫が

1

円

ψNh‑

︑

‑ r

A ・

町 出

人 U

が︒汁可︹

G

¥ w

B S

開河

湾

S︿山中田﹁

J

が ︒

nS

什

yw

︑一 件泊 目前 田8 d h

沖協 一円 討弓 が

G J

5 5

什

5

・ふトミぷ什日が︒

当 ﹁ ︑

F J w

︐

対 同

什 釘

が ︒

前に定義したような政策として︑収益を最大

にする最適政策を求めることが問題になる︒

の方法を変更して︑図

?N

のような政策反復法が証明される乙とを 乙の場合筆者は

( 9 )

予 想

す る

︒ た

T

ご

し

問 、

‑

~図

Il∞  卜 、 コ

。

の ボ

ッ

ク ス の 中 で で あ

り ︑

何回 rHuh‑r

とする

O

伊 同

l

ご

(h wN ) 

↑ 

反復法の計算は︑政策改良ルーチンからは

いるものとする︒最初は︑すべての引を

0

と

おいて

同 国 内 戸 穴

ρ+MMM

一 同

を最大にするような

r l

︐

E

を見つける︒そして︑反復法を繰返して︑最後にどこで停止するかが問題となる︒規則は

簡単である︒それは︑相続いた二つの政策が同一であるとき最適政策に到着したことになる︒政策改良ルーチンで新

政 策

反 復

法 に

つ い

て

政策の

( ‑ J W

︑)が直前の(てい︑)に等しい呈を与えるならば︑前の

G J

W ︑)を変更しないでそのままにしておく︒

‑'‑'・ / ¥  

4

く盟 iミトホ代会へ工、 Z話斗うt6 P =R1'制栴 8Þ ト思 8 -1:豆長 ~P~ t()。主主国窓際組制 8~P .."p-+ミ会的吋小~

l' 

\tt守 ~8ß~ 士三日き土 ~Ç"\ ~U 患

~wr ~~ l'Q 

10 

..IJ士 f 盟会い~M<:lfl ~~

8 P 

~ l'Q  ..IJ m~~ ミ足時。

108 吋 ~Ç"\~

l' 

i呉服 Q 闘ととよさ土ゃい赴 rヤl'Q 10 ベ J=RtW: J~W 長時組.t:(羽田?鶴市民~~ ~l'Q I0..IJ~

l' 

~，医科よさ純蛍~~.."pや P~!{\ 組制..IJ ~担惚

~C"\ 0 

R.Bellman

， 

Dynamic Programming

，

1957

， 

Princeton Univ

， 

Press. 

D.Blackwell

， 

Discrete Dynamic Programming

， 

Ann

， 

Math

，

Statist.

，

33(1962)'719‑726. 

D.Blackwell

， 

Discounted Dynamic Programming

， 

Ann. Math. Statist.

，

36(1965) 

，

226‑235 

制

(同)(閃)(的)(噌)

B.W. Brown

， 

On the 

It

erative Method of Dynamic programming on a Finite Space Discrete Time Markov 

Process

， 

Ann

， 

Math. Statist.

，

36(1965)

，

1279‑1285 

S.Karlin

， 

A First Course in Stochastic Process

， 

Academic Press

，

New York

，

1966. 

(的)(む)(ド)

J .L.Doob

， 

Stochastic Processes

，

1953

， 

John Wiley 

& 

Sons. 

K.

L. Chung

， 

Markov Chains with Stationary Transition Probabilities

， 

Springer Verlag

， 

Berlin

，

1960. 

R.Bellman

， 

A Markov Decision Process

， 

John Wily & Sons

， 

New York

，

1956. 

(∞

)(O) 

R.A.Howard

， 

Dynamic Programming and Markov Processes

， 

John Wiley 

& 

Sons

， 

New York

，

1958. 

R.A.Howard

， 

Research in Semi‑Markovian Decision Structures

， 

J .Operations Research Soc. Japan

，

6(1964)

， 

163‑199 

J.G.Kemmeny & J.L.Snell

， 

Finite Markov Chains

， 

D.Van Nostrand Company

，

1960

， 

1.J. Martin

， 

Baysian Decision Problems and Markov Chains

， 

John Wiley 

& 

Sons

， 

New York

，

1967.  をきと=主

_~

守‑‑< τ コ

d