マルコフ決定過程に基づく最適保全方策
保全の問題では、対象システムに何も保全行動という介入しなければ、システムは劣化していく。 ただしその状態の遷移は、現在の状態とマルコフ行列に記された条件付き分布に従う。 ゲームはプレイヤーが複数いるのが通例だが、保全の問題では対象であるシステムが打ってくる手はとても単純で、保全行動を実行しなければ劣化による状態遷移が発生する。保全行動を実行すれば、その結果として状態が回復するという状態遷移が発生する。
マルコフ性の活用と状態遷移行列の活用
保全を施さない場合のシステムの劣化が、次の図で表されるマルコフ連鎖に従うとする。
これを行列で表すと、次のようになる。
| P[1→1]=9/10 | P[1→2]=1/10 | P[1→3]=0 |
| P[2→1]=0 | P[2→2]=9/10 | P[2→3]=1/10 |
| P[3→1]=0 | P[3→2]=0 | P[3→3]=1 |
選択した行動の実施によって生じる費用も次のように与える。
| 稼働 | 修理 | 取替 | |
| 1 | 0 | 10 | 150 |
| 2 | 0 | 50 | 150 |
| 3 | 2000 | 250 | 150 |
当初の状態が1だったとする。また、各状態の総期待費用が次の表で与えられているとする。
| 状態 | 1 | 2 | 3 |
| 費用V | 1 | 5 | 10 |
このとき、現時点で行動aを選択する時の１時点先の費用は次のように予測できる。
| 行動 | 稼働 | 修理 | 取替 | 最小値 | ||
| 1 | 0+0.9×1+0.1×5 | 10+0 | 150+0 | 1.4 | ||
| 2 | 0+0.9×5+0.1×2000 | 50+0 | 150+0 | 50 | ||
| 3 | 0+2000 | 250+0 | 150+0 | 150 | ||
この計算は例えば、現在の状態が2とする。何も介入しなければ、現時点では費用発生はなし。そして確率0.9で状態2に留まる。その場合には費用5が発生する。また確率0.1で状態3に進む。その場合には費用2000が発生する。これらのことから、状態2において行動「稼働」を選択した場合の総期待費用は0+0.9×5+0.1×2000=204.5と予測できる。他の状態と行動についても、同様に計算する。
これで状態ごとの最適行動が、次の表のように定まる。
| 状態 | 1 | 2 | 3 |
| 最適行動 | 稼働 | 修理 | 取替 |
価値関数あるいは費用関数
マルコフ連鎖に基づいて推移する対象に、保全行動によって介入する場合には、最適な行動を選択するためには、将来に渡る費用を算出する関数Vの学習が不可欠となる。 そのためのアルゴリズムを２つ紹介する。
学習アルゴリズム
価値関数V(s)の学習には大きく、policy iterationとvalue iterationという2種類のアルゴリズムがある。 以下では状態sにあって、行動aによって状態s^\primeに遷移する確率を P[s\prime|s,\pi(s\prime)] と書く。 以前の書き方では P(a)[s→s^\prime]であった。
迷路など、状態の遷移や行動の実行可能性に状態や環境による制約が加わる時には、それも考慮する。
ベルマン更新
時点tに状態がsの状況を評価する関数をV_t(s)と書く。 また時点tで行動aをとったときに、次の時点t+1に取る状態をS'(s,a)とする。 S'(s,a)は、sとaに依って変わる確率分布F(s|s,a)に従う確率変数である。
現時点では、状態sと行動aに応じて、費用が生じる。これが確率変数の場合は(条件ごとに異なる)条件付き期待値E[C|s,a]、定数の場合は条件によって定まる費用C(s,a)となる。これと、次の時点の状態S'(s,a)によって定まる費用V(S')の期待値の和が、状態sで行動aを執った場合の総費用となる。
将来の費用を現在価値に換算するために、割引係数β=1/(1+r)をかけるなら、次のようになる。
そして時点tの行動aをQt(s,a)を最小にするように選ぶ。
この計算式をベルマン更新という。
ベルマン方程式
現在の最適な行動と、その行動の帰結として将来に渡って発生する費用の総額は、勿論、将来の費用に依存する。t=∞の時点の費用が分かっていれば、例えば V∞(s)≡0ならば、そこから1時点ずつ遡ってVtを計算していくことが考えられる。この計算が、tを小さくするにつれて、つまり過去に遡るにつれて、ある一定の関数に収束するなら、その関数は次の方程式を満たす。
これがベルマン方程式である。
費用ではなく、報酬が得られる場合は、ベルマン更新が
定常状態におけるQ関数とベルマン方程式はそれぞれ次のようになる。
そこで、将来の費用関数をどのように算出するか、そして将来の状態をどのように予測するか、がマルコフ決定過程がうまく働くための鍵となる。
マルコフ連鎖に基づく予測
ベルマン方程式は、現在の状態sに基づいて、行動aを選択する際に、将来に渡って発生する費用を算出することができる。マルコフ決定過程において最も重要な式である。 将来の費用の予測の部分は、推移にマルコフ連鎖を仮定すると、ベルマン更新の方は次のようになる。
これを反映させた、ベルマン更新は次の式で定まる。
ベルマン方程式のための将来の費用の予測も同様に計算できる。
これを反映させた、状態と行動ごとのQ(s,a)は次の式で定まる。
これで、状態毎に予測を含む費用Q(s,a)を次のような表にまとめることができる。
| Q | 1 | 2 | A | |
| 1 | E[C(s=1,a=1)]+E[V(a=1)[1→S]] | E[C(s=1,a=2)]+E[V(a=2)[1→S]] | E[C(s=1,a=A)]+E[V(a=A)[1→S]] | |
| 2 | E[C(s=2,a=1)]+E[V(a=1)[2→S]] | E[C(s=2,a=2)]+E[V(a=2)[2→S]] | E[C(s=2,a=A)]+E[V(a=A)[2→S]] | |
| N | E[C(s=N,a=1)]+E[V(a=1)[N→S]] | E[C(s=N,a=2)]+E[V(a=2)[N→S]] | E[C(s=N,a=A)]+E[V(a=A)[N→S]] |
これがQ(s,1)、Q(s,2)、…、Q(s,A)の最も小さい値に対応する行動を、状態sにおける最適な行動とする。 これを状態sごとに最小化するベルマン方程式は次の式になる。
方策反復
まず状態と行動の対応表を一つ定める。この表を方策(policy)といい、πで表す。 方策が与えられるとは、 s ごとに a を与える関数π(s)が定まっていることを意味する。 この方策πを適用すると、次のようなQ関数が得られる。
これを状態ごとに最小にする方策を求める。
これを新しい方策とする。
このように方策を更新していくのが、方策反復policy iterationである。 収束するまでこれを繰り返して、最適方策を得る。 日本語では方策反復法と呼ばれることもある。
価値反復
value iterationは、ベルマン更新をそのまま用いる。
最終時点のVをひとつ与える。次にベルマン更新
によって、時点を１つ戻す。毎時点、費用を最小にするように状態sごとに行動aを選ぶ。 この対応が方策π(s)になっているが、そのことは特に意識しない。 そしてVt(s)が収束した時点の方策π(s)を最適方策、またそのときの関数Vt(s)をV(s)とする。
まとめ
上の二つのアルゴリズムはどちらも関数V(s)を与える。 この関数を用いて、現時点で将来の推移を考慮しながら、最適な行動を選択する。