文書の過去の版を表示しています。
マルコフ決定過程
マルコフ決定過程は、対象の状態、状態の遷移、行動、状態の評価関数、の４つのコンポーネントからなる確率事象に関する意思決定のモデルである。
状態の遷移には、次の２種類がある。
- 何も行動を取らず対象に介入しないことによる状態の遷移
- 何らかの行動を取り対象に介入することによる状態の遷移
介入するか否か、また介入するならその内容は、介入後の状態の良し悪しを評価して比較検討する 例えば、車で交差点に進入する状況を考える。そのままの車線を走り続ければ直進だが、駅に家族を迎えにきたのであれば、右折レーンに入って、右折の準備をするのが良い。その方が目標を果たすことに近付く。そこで、右折のウィンカーを点灯して右折レーンに入る、という操作を行う。これが介入である。
また、ロボットを格子状の盤の上に作った迷路の中に置き、ゴールを目指させる状況を考える。ロボットは見通せる範囲の通路の形状しか認識できない。迷路の大きさも分からない。つまり、前後左右を向いたり、何歩が歩いたりしてみても、ゴールに近付いているかどうかを認識できない。状況を簡単にするために、ロボットは自分の前後左右が壁か通路かのみを認識できるとしよう。この時、どのような行動をとっていけば、ゴールに辿り着く確率が高まるだろうか。たとえ、ゴールの上に立たなければゴールに着いたことが分からないとしても、多くの試行を重ねることで、ゴールへ辿り着くための行動選択の指針を見出せることがある。
保全でも同様で、対象の状態を観測し、劣化の度合いに応じて、今、どの保全行動を取れば良いか、またもう少し遷移を見守るのが良いか、を将来に渡って運用し続けるために、余計な費用発生は避け、必要な費用発生は積極的に認めるように、保全行動を選択していく。
行動の選択は、将来の状態の評価関数の予測を行い、最も評価が高くなるように行動を選択することが合理的である、という考え方に基づいて行う。将来の状態は、行動ごとに定められた遷移行列を繰り返し用いて行う。
これらのことを、マルコフ決定過程はモデル化していく。
迷路の例
ロボットの状態を次のように考える。
| 番号 | 状態 |
| 1 | 正面に進める |
| 2 | 正面に進めない |
行動は次の3種類とする。
| 番号 | 状態 |
| 1 | 正面に進む |
| 2 | 右に90度回転する |
| 3 | 左に90度回転する |
大きさ3×3の迷路が次のようになっているとする。
左下隅に、上向きにロボットを置く。人間であれば簡単に、ゴールまでたどり着くには、
| 時点 | 行動 |
| 1 | 1(前進) |
| 2 | 1(前進) |
| 3 | 2(右90度回転) |
| 4 | 1(前進) |
| 5 | 2(右90度回転) |
| 6 | 1(前進) |
| 7 | 3(左90度回転) |
| 8 | 1(前進) |
| 9 | 3(左90度回転) |
| 10 | 1(前進) |
という行動選択をすればいい、とたぶん分かる。
コンピュータ上であれば、最初の１ステップ目で
| 番号 | 状態 |
| 1 | 正面に進む |
| 2 | 右に90度回転する |
| 3 | 左に90度回転する |
を全て試して、ゴールにたどり着くかどうかを調べる。辿り着かなければ、それぞれのステップの次に
| 番号 | 状態 |
| 1 | 正面に進む |
| 2 | 右に90度回転する |
| 3 | 左に90度回転する |
を行う、3×3=9通りの行動の組み合わせを検討する。それでもだめなら、さらに9通りそれぞれの先に
| 番号 | 状態 |
| 1 | 正面に進む |
| 2 | 右に90度回転する |
| 3 | 左に90度回転する |
を行う、9×3=27通りの行動の組み合わせを検討する。これをゴールに到達するまで繰り返すのが、総当たり法である。
それに対して、マルコフ決定過程では状態が2つしかないことから、次のような状態とアクションの対応表を埋めようとする。
| 番号 | 状態 | 行動 |
| 1 | 正面に進める | |
| 2 | 正面に進めない |
状態ごとにどのような選択をするかを、将来の評価関数を高めるように選んでいく。
状態の定め方
実は、上の２状態では、常にゴールにたどり着ける解法はもとまらない。
| 番号 | 状態 | 行動 |
| 1 | 正面に進める | 進む |
| 2 | 正面に進めない | 右に回る |
上の方策を適用すると次のようになる。
| 手順 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
| 正面の状態 | 無 | 無 | 壁 | 無 | 壁 | 無 | 壁 | 壁 | 無 | … |
| 行動 | 前進 | 前進 | 右回転 | 前進 | 右回転 | 前進 | 右回転 | 右回転 | 前進 | … |
こうすると、途中でUターンしてしまい、永遠にスタート地点付近をさまようことになる。
一度、自分で確認してみてほしい。
| 番号 | 状態 | 行動 |
| 1 | 正面に進める | 進む |
| 2 | 正面に進めない | ランダムに右か左に回る |
これなら、運が良ければ、たどり着ける。
状態を次のように拡張してみる。
| 番号 | 状態 |
| 1 | 正面に進める |
| 2 | 正面が壁で、右手の壁がない |
| 3 | 正面が壁で、左手の壁がない |
| 4 | 正面が壁で、右手と左手の両方とも壁がない |
こうすると、例えば
| 番号 | 状態 | 行動 |
| 1 | 正面に進める | 進む |
| 2 | 正面が壁で、右手の壁がない | 右に90度回転する |
| 3 | 正面が壁で、左手の壁がない | 左に90度回転する |
| 4 | 正面が壁で、右手と左手の両方とも壁がない | 右に90度回転する |
という方策を学習できたとする。適用してみよう。
| 手順 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
| 正面の状態 | 無 | 無 | 壁 | 無 | 壁 | 無 | 壁 | 無 | 壁 | … |
| 左手の状態 | 壁 | 壁 | 壁 | 壁 | 壁 | 壁 | 無 | 無 | 無 | … |
| 右手の状態 | 無 | 壁 | 無 | 無 | 無 | 無 | 壁 | 壁 | 壁 | … |
| 行動 | 前進 | 前進 | 右回転 | 前進 | 右回転 | 前進 | 右回転 | 左回転 | 前進 | … |
これで有名な「右手づたいに壁を辿る」という迷路脱出のルールと等しくなる。 最後まで続けると、ゴールに辿り着く。
このように、マルコフ決定過程による問題解決には、適切な状態の表現が不可欠となる。
もう少し状態数を増やすと、次のような表ができる。
この表の右側にどの状況でどの行動を取るかを定めるのが、方策表である。 前に壁があると、進めないなど、選択できない行動のセルは塗りつぶしてある。
正前に壁がないのに前進しないと、いつまで経っても同じ場所に留まる方策ができあがってしまう。
上の４状態での方策は、７状態でも次のようになる。
状態1,4,5,7は前進できるので前進、状態2,6,7は前進できないので右が空いていれば右、右が空いてなければ左に回転するので、同じ方策である。
方策の学習
方策の候補をひとつ定める。
正前に壁が無ければ前進、壁があれば右回転、という方策を例にとる。 これを迷路の中に、ランダムな場所に、ランダムな向きにして置いたロボットに従わせる。 たとえば100ステップ内にゴールに辿り着けたら(100-到達ステップ数)点、辿り着けなければ0点として、何回も試行してみる。 例えば、上のこの例は0点である。
まったく到達できなければ、この方策をどこか一箇所、変更してみる。
そしてまたランダムに場所と向きを変えて置いて、迷路に挑戦させる試行を何度も繰り返して、この方策を評価する。上のもう１つの例は、100-10=90点を獲得する。
別の場所に下向きに置くと、100-14=86点を獲得する。
これを繰り返して、平均点をその方策の評価とする。
このように方策を比較して、良い方策を得るように探索をしていくのが、マルコフ決定過程の基本的な考え方である。1980年代から2000年代までは、ボードゲームのコンピュータのプレイヤーを作るのに、マルコフ決定過程の考え方がよく用いられていた。どのようなボードゲームにも、神の手と呼ばれる、誰でもその手順に従えば勝てる、という方策は存在せず、相手の手に合わせて状況を評価し、最善の手を打っていくことになる。ゲームでは、状況の数が膨大になり、取り得る行動もたくさんあるため、すべての行動の順列を比較検討すると、組み合わせ爆発が生じる。その爆発した組み合わせを、アドホックに刈り込んで、必要な組み合わせだけを比較するようにして、計算量を軽減する工夫が行われていた。
学習アルゴリズム
行動の学習には大きく、policy iterationとvalue iterationという2種類のアルゴリズムがある。 以下では状態sにあって、行動aによって状態s^\primeに遷移する確率を P[s\prime|s,\pi(s\prime)] と書く。 以前の書き方では P(a)[s→s^\prime]であった。
迷路など、状態の遷移や行動の実行可能性に状態や環境による制約が加わる時には、それも考慮する。
ベルマン方程式
ベルマン方程式は、現在の状態sに基づいて、行動aを選択する際に、将来に渡って発生する費用を算出することができる。マルコフ決定過程において最も重要な式である。
V(s,a)=E[r|s,a]+\gamma \sum_{s\prime} P[s\prime|s,a]V(s\prime, a)
最後のΣも期待値の計算をしているので、簡単に次のような表にまとめることができる。
| V | 1 | 2 | A | |
| 1 | E[R(s=1,a=1)]+E[V(a=1)[1→S]] | E[R(s=1,a=2)]+E[V(a=2)[1→S]] | E[R(s=1,a=A)]+E[V(a=A)[1→S]] | |
| 2 | E[R(s=2,a=1)]+E[V(a=1)[2→S]] | E[R(s=2,a=2)]+E[V(a=2)[2→S]] | E[R(s=2,a=A)]+E[V(a=A)[2→S]] | |
| N | E[R(s=N,a=1)]+E[V(a=1)[N→S]] | E[R(s=N,a=2)]+E[V(a=2)[N→S]] | E[R(s=N,a=A)]+E[V(a=A)[N→S]] |
これで、V(s,1)、V(s,2)、…、V(s,A)の最も小さい値に対応する行動を、状態sにおける最適な行動とする。
この方程式はt時点の関数をV_{t}(s,a)と置くと、
V_{t}(s,a)=E[r|s,a]+\gamma \sum_{s\prime} P[s\prime|s,a]V_{t+1}(s\prime)
のように、右辺と左辺でVの時点がずれる。これは左辺は現時点の価値であり、右辺は1時点先の価値の期待値を計算していることによる。この方程式をベルマン更新と呼ぶことがある。t→∞の極限が収束するとき、最初の方程式が成り立つ。
方策反復
policy iterationとは、まず状態と行動の対応表を一つ定める。この表を方策(policy)といい、πで表す。 この表に基づいて行動したときに生じる費用もしくは利得の期待値(あるいは平均値)を求める。そのために、表に記された行動基準を繰り返し適用するか、次の方程式を解く。
V(s)=E[r|s,\pi(s)]+\gamma\sum_{s\prime}P[s\prime|s,\pi(s\prime)] V(s\prime)
そしてこの関数を用いて、表を次のように更新する。
\pi(s)\leftarrow \arg \min_a E[r|s,a]+\gamma\sum_{s\prime}P[s\prime|s,a] V(s\prime)
収束するまでこれを繰り返すのがpolicy iterationと呼ばれるアルゴリズムである。日本語では方策反復法と呼ばれることもある。
価値反復
value iterationは、状態sを与えると費用Cあるいは価値Vを返す関数を一つ定める。
V(s)
この関数を次のように更新する。
Q(s,a) \leftarrow E[r|s,a] + \gamma \sum_{s\prime} P[s\prime|s, a]V[s\prime]
そして、この関数のsを固定したときのaに関する最大値を新たな関数とする。
V(s) \leftarrow \min_a Q(s,a)
価値関数
上の二つのアルゴリズムはどちらも関数V(s)を与える。 この関数を用いて、現時点で将来の推移を考慮しながら、最適な行動を選択する。
強化学習
上ででてきたQという関数を、様々な状態の対象に様々な行動を適用して、その結果から試行錯誤を繰り返すことで学習し、その下で最適な行動を選択していく。必要に応じて、アクションごとの状態推移も学習する。
https://gym.openai.com/envs/MountainCarContinuous-v0/
強化学習の話は、この原稿のスコープを大きく超えるので、別の機会に譲る。