平成 12 年 9 月 1 日

人工知能基礎 (O) 演習資料

状態遷移に不確実性を伴う環境下での意志決定問題
1

はじめに
実問題における多くの場面において，状態遷移に不確実性を伴うダイナミクスのもとでの意志決定が求められている．例えば，在庫管理や生産システム管理，計算機システムにおける資源割り当て，ロボットの制御など ，その分野は多岐にわたる．そのような問題を定式化し ，洗練された方法論を与えるモデルの一つにマルコフ決定過程 (Markovdecision process: MDP) がある．状態遷移のダ イナミクスが既知である場合において，最適な意志決定を求めることは「プラニング 」と呼ばれる．
エージェント（コントローラ ）6状態観測 st?

行動 at

6

報酬 rt

環境（ 制御対象）= MDP
図 1: MDP におけるプラニングの枠組．行為主体『エ−ジェント 』の報酬獲得が最大になる制御規則を求める．

MDP におけるプラニングの枠組は，図 1に示すように最適制御問題になっている．行為主体『エ−ジェント 』と制御対象『環境』は，以下のやりとりを繰り返す．

1. エ−ジェントは時刻 t において環境の状態観測 stに基づいて意志決定を行い，行動 atを出力
2. エ−ジェントの行動により，環境は st+1へ状態遷移し，その遷移に応じた報酬 rtをエ−ジェントに与える．
3. 時刻 t を t + 1 に進めてステップ 1 へ戻る
エ−ジェントの利得（ return: 最も単純な場合，報酬の総計）が最大となるような制御規則，すなわち状態観測から行動出力へのマッピング（ 政策（ policy ）と呼ばれる）を求める．

【プラニングの例：在庫管理問題】
・状態：在庫量×市場動向
・行動：品物を仕入れる数量
・状態遷移：（ 次の日の在庫量）＝（ 現在の在庫量）＋（ 仕入れた数量）−（ 注文を受けた数量）
ただし 在庫はゼロより小さくなることはない
市場動向に応じて注文を受ける数量が確率的に変化する．
・報酬＝（ 注文を受けた利益）−（ 在庫量に応じた管理費）−（ 仕入れ費用）
ただし 在庫がゼロの場合，注文はキャンセルされる・利益を最大にするには，ど のような制御規則で品物を仕入れたらよいか？

1

2

マルコフ決定過程 (MDP) とは ?

●マルコフ性：とは？

状態 s0への遷移が，そのときの状態 s と行動 a にのみ依存し ，それ以前の状態や行動には関係ないこと．

●エルゴ −ト 性：とは？
任意の状態 s からスタ−トし ，無限時間経過した後の状態分布確率は最初の状態とは無関係になること．

 環境のとりうる状態の集合 S = fs1 ; s2;    ; sng エージェントが選択可能な行動の集合 A = fa1; a2;    ; a`g 状態遷移のダ イナミクス：

状態 s において行動 a を実行したときの状態 s0へ遷移する確率 Pr(s0 s; a) により記述．

j

状態遷移は離散時間ステップで発生．

 報酬のダ イナミクス：

状態 s において行動 a を実行した後，状態 s0へ遷移した場合の報酬の期待値 Ra (s; s0 ) により記述．

@@R

行動 a を選択S



a0aa00状態遷移Pr(S 0 jS; a)▲
報酬Ra (S; S 0 )



- S0

【 MDP によるモデル化の例：迷路問題】
s0s5s10s15s20s1s2

s3s4状態 S : (goal を除く) 迷路のマス目に相当, 24 状態
行動 A : 上下左右への移動 (4 種類)

s6s7s8s9s11s12s13s14s16s17s18s19

遷移規則 Pr(s0 s; a) : 壁が存在する方向へは移動できない等を記述
ゴ ールと同時に一様分布で他のマスへ飛ぶ
報酬 Ra (s; s0 ) : ゴ ールした時 100，それ以外 0s21s22s23

Goal

図中の○が現在のロボットの位置．すなわち st = s12 .

j

図 2: 迷路問題を MDP で表現した例．

 エージェントは現在ロボットがいる場所の番号だけを観測する．
 迷路中での移動が確率 Pr(s0 js; a) によって表されているため，行動を選択してもある確率で失敗したり別の方向へ移動してし まうなど のダ イナミクスも表現できる．

 報酬の設定を変えれば，壁に衝突したら罰 (負の報酬) を与えたり，移動コストを考慮する問題も表現可能．
 状態遷移の不確実性や移動コスト等の扱いが求められると，単なる経路探索では解けない難しい問題となる．
2




3



マルコフ解析

● 政策は，エージェントの制御規則である．

j

状態 s で行動 a をとる確率を表す関数(s; a) = Pr(at = a st = s) とし て定義されることが多い．
● 定常政策とは，時間とともに変化することのない政策．

ある定常政策をとり続けるとき，状態 s において状態 s0 へ遷移する確率を P  (s; s0 ) で表すと
PP  (s; s0 ) = a Pr(s0 s; a)(s; a) である．よって定常政策のもとでは状態遷移規則は以下の nP で表現される．同様に報酬の期待値 R は以下のように 1 n の行列で表される．

j

2
P

P  (s1 ; s1)
6 P  (s ; s )62 1= 6642R



..
.

P  (s1 ; s2 )P  (s2 ; s2 )..
.

P  (sn ; s1) P  (sn ; s2 )3

 n の正方行列3   P  (s1 ; sn )   P  (s2 ; sn ) 777
..

..
.

.

   P  (sn ; sn )

(1)

752 P
3P
(a; s1 ) Ra (s1 ; s0) Pr(s0 js1 ; a)←状態 s1の報酬の期待値
s2Sa2A
P6 P
7a00

(a;s)
R(s;s)
Pr(sjs;a)67 ←状態 s2の報酬の期待値
222
7 = 6 s 2S a2A
7(2)
= 6..
..
67 6745 4
5.
.
P
Pa00
←状態 snの報酬の期待値
R (sn )s 2S a2A (a; sn ) R (sn ; s ) Pr(s jsn ; a)R (s1 )6 R (s ) 7
62 7000

このように環境の性質をマトリクスの数学的性質へ帰着して考えるのがマルコフ解析である．

●kステップ 後にエージェントが状態 s に存在する確率の計算方法：
エージェントが時刻 kに状態 s に存在する確率を Uk とし て以下のようにマトリクス表現する．

23Uk (s1 )←エージェントが状態 s1に存在する確率
6 U  (s ) 76 k 2 7 ←エージェントが状態 s2に存在する確率

Uk = 6647..
75.
←エージェントが状態 snに存在する確率
Uk (sn )(3)

初期状態分布が U0 のとき，kステップ後の状態分布 Ukは，式 1，3 を用いて以下のように計算される：
t (U  ) = t(U  )(P  )kk0(4) が存在する．
ただし記号 t はマトリクスの転置を表す．エルゴ ート的な MDP では無限ステップ経過後の状態分布 U1

これを定常分布または平衡分布と呼ぶ．定常分布は以下の平衡方程式の解である：
t (U  ) = t (U  )P 1(5)1 が確率分布で，要素の合計が１になる条件を用いる．
この方程式だけでは未知数の数に対して式が１つ足りない．U1●kステップ 後に得る直接報酬の期待値の計算方法：
初期状態分布が U  のとき，直接報酬の期待値 E r は以下の式でスカラーの値とし て計算される：

0f 0g

E fr0g = t (U0 )R

(6)

f g

よって，初期状態分布が U0 のとき，エージェントが kステップ 後に得る直接報酬の期待値 E rk は，式 1，3よりE frk g = t(Uk )R = t(U0 )(P  )k R Rは，１ステップあたりの平均報酬を表す．
定常分布における直接報酬の期待値t U13(7)【マルコフ解析の例：オモチャ製造業者の問題】[3] 玩具の製造業者が，市場における彼の製品の人気の状態を観測し ，各状態に応じて適切な決定を下す．
 状態 s1：製品が市場に人気がある
 状態 s2：製品が市場に人気なし
 状態 s1における行動 a1：広告をしない，行動 a2：広告を出す
 状態 s2における行動 a1：研究をしない，行動 a2：研究する 報酬：売上から経費を差し 引いた金額
推移確率

状態 s

行動 a

s1：人気ありa1：広告なし
a2：広告ありs2：人気なし

Pr(s1 js; a)
0:5
0:8
0:4
0:7

a1：研究なし
a2：研究あり報酬

Pr(s2 js; a)
0:5
0:2
0:6
0:3

Ra (s; s )94
3
1

Ra (s; s2 )1

直接報酬の期待値

6 = 0:5  9 + 0:5  3
4 = 0:8  4 + 0:2  4
3 = 0:4  3 + 0:6  ( 7)
5 = 0:7  1 + 0:3  ( 19)34719

状態 s1では常に行動 a1 ，状態 s2でも常に行動 a1をとる政策を11とすると，状態遷移マトリクス P 11 および報酬の期待値マトリクス R11 は"P 11=0:5 0:50:4 0:6#"

R11,0:5  9 + 0:5  30:4  3 + 0:6  ( 7)

=

#

"="

エージェントが時刻 t = 0 において状態 s にいるとき，状態分布マトリクスは U 11 =10

よって政策11をとる場合，1 ステップ 後の状態分布 U111 は以下のとおり
t U 111=tU 11 P 110=

hi

1 0

"

0:5 0:50:4 0:6

同様に kステップ後の状態分布 Uk11 は以下のようになる：
tU 11k=tU 11 (P 11 )k0=

h1 0i"#h=0:5 0:50:5 0:50:4 0:6

10i

63
##(8)

である．

(9)

#k(10)

f g

政策11をとり，初期状態が s1のとき，ステップ t = 0 における直接報酬の期待値 E r0 は以下のように計算する：

E fr0g = t (U0 )R =hi

1 0f g"63#=6(11)

同様に kステップ後に得る直接報酬の期待値 E rk は以下のとおり：

E fr k g= t (U  )(P 11 )k R

0=

h4

1 0i

"

0:5 0:50:4 0:6

#k "

63

#(12)

4

割引報酬による評価：最適な政策とは？

●プラニングの目的は，ある評価値が最大になる政策を見付けること●1 ステップあたり 1の確率で活動停止するエージェントが得る報酬の合計を利得 (return)と呼ぶ．

ただし は割引率と呼ばれ，0  1 である．この評価は，割引報酬による評価と呼ばれる．

●評価値はベクトル表現：マルコフ決定過程においてエ−ジェントが定常政策をとるとき，利得の期待値は，時間には関係なく状態 s だけに依存する．利得の期待値は状態 s の valueと呼ばれ，定常政策のもとで状態 s の関数とし て表される value をstate-value 関数と呼び V  (s) で表す．式 1,2を用いると，この V  (s) を要素とし てマトリクス表現すると，以下の方程式が成り立つ．

2V

3←状態 s1からスタートした場合の報酬合計の期待値
V  (s 1 )6 V  (s ) 7 ←状態 s からスタートした場合の報酬合計の期待値
622 7= 6647..
..
75.
.
←状態 snからスタートした場合の報酬合計の期待値V (sn )1Xt (P  )t R
= R + P  R + 2 (P  )2 R +    =t=0= R + P  V = (IP  ) 1R

(13)● 最適政策と最適 state-value 関数：

 ２つの政策と0 およびそれぞれの政策の評価関数 V  および V  を考える．
全ての状態 s において V  (s)  V  (s) となるとき，政策は 0より優れているという．
 マルコフ決定過程では，他のどんな政策よりも優れた，あるいは同等な政策が確定的 (deterministic) な政00

策の集合中に少なくとも 1 つ存在する．これを最適政策 という．

 最適政策は複数存在することもあるが，全ての最適政策は唯一の state-value 関数を共有する．これは最適な state-value 関数 V と呼ばれる．

【迷路問題においてランダム政策をとる場合の value 関数の値】
0:58 0:81 1:39 0:74 0:42
0:61 1:12 3:24 6:54 0:29
0:91 1:62 1:12 12:7 24:6
2:12 4:06 10:2 20:9 47:4

●割引率 = 0:9 とし て value 関数 V  (s) を計算●関数 V  (s) は，ゴ ールから遠いほど 低い地形となる●遷移規則 Pr(s0 s; a) : ゴ ール時にランダム遷移する以外は状態遷移に不確実性無し

j1:13 0:65 0:45 14:5 Goal
迷路問題においてエージェントがランダムに行動選択する場合の value 関数 V  の値．DP の反復計算を 100 回行って求めた．これは，1 ステップあたり 0:1 の確率で故障するロボットが任意の場所からスタートしてランダ ムに行動選択をとり続けた場合において未来に得る報酬合計の期待値と等価．

5【迷路問題における最適 value 関数の値】
115128142128115128142158176104142158142195217158176195217241142128115195 Goal

●割引率 = 0:9 とし て最適 value 関数 V  (s) を計算●関数 V  (s) は，ゴ ール状態が最も高く，遠いほど 低い地形となる●遷移規則 Pr(s0 s; a) : ゴ ール時にランダム遷移する以外は状態遷移に不確実性無し●最も高い方向へと移動することがゴ ールへの最短パス＝最適政策j

迷路問題における最適 value 関数 V の値．DP の反復計算を 100 回行って求めた．これは，1 ステップあたり 0:1 の確率で故障するロボットが任意の場所からスタートして最適政策をとり続けた場合において未来に得る報酬合計の期待値と等価．

【演習問題】
オモチャ製造業者の問題において，状態 s1では常に行動 a1 ，状態 s2では常に行動 a2をとる政策を12，状態 s1では行動 a2，状態 s2で行動 a1をとる政策を 21，

状態 s1でも状態 s2でも行動 a2をとる政策を 22とする．
以下を計算せよ．

1. それぞれの政策12, 21, 22における遷移確率 P 12 , P 21 , P 22
および直接報酬の期待値 R12 , R21 , R22 を求めよ．
2. 割引率 = 0:5 のとき，各政策11, 12, 21, 22における value 関数 V 11 , V 12 , V 21 , V 22 を求めよ．
3. 割引率 = 0:5 のとき，最適な政策は 11, 12, 21, 22のどれであるか答えよ．
4. 割引率 = 0:9 のとき，各政策11, 12, 21, 22における value 関数 V 11 , V 12 , V 21 , V 22 を求めよ．
5. 割引率 = 0:9 のとき，最適な政策は 11, 12, 21, 22のどれであるか答えよ．

65

プラニング：最適政策を求める方法は？
割引報酬による評価では，最適な政策は確定的 (deterministic) な (確率的ではない ) 政策集合中に存在する．確定的な政策集合は離散 MDP では有限なので，確定的な全政策について value を計算し ，最大の value を持つ政策を探せばよいのだが，探索空間は状態数の指数オーダーになってし まう．そこで下記のように少ない計算量で済む方法を用いて最適政策を探す．
また，状態数が大きくなるとマトリクスの逆行列演算が大変なので以下の DP のテクニックを用いる．

5.1

Howard の政策反復法 (Policy Iteration Method)

環境の状態遷移確率 Pr(s0 s; a) および報酬関数 Ra (s; s0 ) が与えられたとき，ある政策を決めると，式 1,2より P と R がすぐに決まり，方程式 13の解は V  = (IP  ) 1 R を計算することにより得る．ここで，ある状態 s におjいてとは別の政策0に従って行動をとるときR (s) +0

Xs0 2SP  (s; s0 )V  (s0 ) > V  (s)0(14)ならば，その状態 s だけは政策0に従う新しい政策の value は の value よりも改善されることが証明されている [3]．
P0
00  0式 14は の value だけを用いて簡単に計算できる．よって全状態において R (s) +s0 2S P (s; s )V (s ) が最大0として再び V  = (IP  ) 1 R を計算して同様の操作を繰り返せば よになるように政策を0へ改善し ，い．確定的な政策集合は離散 MDP では有限であるから，上記の政策改善を確定的な政策集合中で行うと，わずかな

有限回数で最適政策を得る．政策反復法の手順を以下にまとめる：

1. 確定的 (deterministic) な政策について，V  = (IP  ) 1 R を計算する．
P
0  002. 全状態において R (s) +s 2S P (s; s )V (s ) が最大になるように政策を確定的政策 へ改善する．
0


5.200

3. 0  のとき，は最適政策なので処理を打ち切る．さもなければ 0とし て手順 1 より繰り返す．

●【 例１】 式 13の V  = (I

動的計画法 (Dynamic Programming: DP)

DP は概念が広すぎて説明が困難だが，ここでは式 13 を解くための逆行列演算など を繰り返し 処理によって数値的に計算する方法だと考えればよい [1] [3]．特に行列がまばら (sparse) だと効率が良い．

P  ) 1 R を DP で計算する場合：

1. V  の全要素を適当な値 (ゼロなど ) に初期化 (X とおく)
2. V  に R + P  V  の値を代入
3. 処理手順 2 を収束するまで繰り返す【 解説】上記の処理は，初期化直後は V  = Xだが，手順 2 を 1 回実行すると，V  = R + P  X ，2 回実行すると V  = R + P  R + 2 (P  )2 X ，n 回実行すると V  = R + P  R + 2 (P  )2 R +    + n 1 (P  )n 1 R + n (P  )n X となる．
式 13より V  = R + P  R + 2 (P  )2 R +   なので，処理 2 の繰返しは高次の項まで近似していくのと等価．

7レポート 課題
右図のように，2 台の機械 M1，M2 より構成される生産ラインがある．

Ｍ１- Ｍ２ - 製品

●各機械は「 稼働」と「 休止」の２状態．よってライン全体で４状態◎機械Ｍ２は，Ｍ１が休止していたら次のステップでは稼働できない●機械Ｍ２が稼働しているときは常に 1:0 の報酬を得る．それ以外の場合，報酬は 0．
●若い作業員と年配の作業員がそれぞれ機械を操作●若い作業員が稼働中の機械を操作すると，◎の場合を除き確率 0:8 で稼働状態を継続●若い作業員が休止中の機械を操作すると，◎の場合を除き確率 0:5 で稼働状態へ●年配の作業員が稼働中の機械を操作すると，◎の場合を除き確率 0:9 で稼働状態を継続●年配の作業員が休止中の機械を操作すると，◎の場合を除き確率 0:4 で稼働状態へ●Ｍ１休止かつＭ２休止の状態を s1 ，Ｍ１休止かつＭ２稼働の状態を s2 ，Ｍ１稼働かつＭ２休止の状態を s3 ，Ｍ１稼働かつＭ２稼働の状態を s4とする●若い作業員をＭ１へ，年配の作業員をＭ２へ配置する行動を a1

年配の作業員をＭ１へ，若い作業員をＭ２へ配置する行動を a2とする【 問１】全ての状態で行動 a1をとる政策を1111，全ての状態で行動 a2をとる政策を2222とする．
このとき P 1111 ，P 2222 ，V 1111 ，V 2222 を求めよ．ただし 割引率 = 0:9 とする．

【 問２】割引率 = 0:9 のときの最適な政策 および最適 valueV を求めよ．
レポ−ト 提出期限：平成 12 年 9 月 21 日 (木) 午後 5 時 必着

レポ−ト 提出先 ：学務部教務掛 (西８Ｅ号館 101 号室)
レポートは A4 判で作成すること
１枚目は表紙とし て以下の事項を明記すること
・人工知能基礎 (O)・レポート (９月１日出題分)



・学籍番号
・氏名

参考文献
[1] Barto, A. G., Bradtke, S. J. and Singh, S. P.: Learning to act using real-time dynamic programming, Arti cialIntelligence 72 (1995), 81-138.
[2] Bertsekas, D.P. & Tsitsiklis, J. N.: Neuro-Dynamic Programming, Athena Scienti c (1996).
[3] 小笠原正巳，坂本武司 著，北川 敏男 編: 情報科学講座 (全 62 巻)A・5・1

マルコフ過程，共立出版 (1967).

[4] Sutton, R. S. & Barto, A.: Reinforcement Learning: An Introduction, A Bradford Book, The MIT Press (1998).

本演習問題に関する質問等は メールにて担当の木村へ行うこと

gen@fe.dis.titech.ac.jp
http://www.fe.dis.titech.ac.jp/ gen/indexj.html
8