マルコフ決定過程

マルコフ決定過程は、状態遷移が確率的に生じる動的システムの確率モデルであり、状態遷移がマルコフ性を満たすものをいう。 MDP は不確実性を伴う意思決定のモデリングにおける数学的枠組みとして、強化学習など動的計画法が適用される幅広い最適化問題の研究に活用されている。 MDP は少なくとも1950年代には知られていたBellmanが、研究の中核は1960年に出版された Ronald A. Howard の "Dynamic Programming and Markov Processes" に起因するHoward。 MDP はロボット工学や自動制御、経済学、製造業を含む幅広い分野で用いられている。

1. 概要
-----

マルコフ決定過程は離散時間における確率制御過程  である。 各時刻において過程  はある状態  を取り、意思決定者  はその状態において利用可能な行動  を任意に選択する。 その後過程はランダムに新しい状態へと遷移し、その際に意思決定者は状態遷移に対応した報酬  を受けとる。

遷移後の状態 、および得られる報酬の値 は現在の状態 と行動 のみに依存し、 と が与えられたもとでそれより過去の状態および行動と条件付き独立となる。 言い換えると、マルコフ決定過程の状態遷移はマルコフ性を満たす。

マルコフ決定過程はマルコフ連鎖に行動、および報酬を追加し拡張したものであると解釈できる。 逆に言えば、各ステップにとる行動がそのステップにおける状態のみ依存するとき、マルコフ決定過程は等価なマルコフ連鎖に置き換えることが出来る。

2. 定義
-----

有限マルコフ決定過程  は4つの要素の組  で表される。ここで各要素はそれぞれ次を意味する。

 : 状態の有限集合
 : 行動の有限集合
 : 遷移関数 
: 報酬関数 遷移関数 は状態 にあり行動 を取ったときの状態 への状態遷移確率 である。 また報酬関数 は状態 から に行動 を伴い遷移する際に得られる即時報酬  、またはその期待値 を表す。

3. 問題設定
-------

MDP における基本的な問題設定は、現在の状態が が与えられたときに意思決定者の取る行動 を既定する方策  を求めることである。 方策は通常 の条件付き分布 として規定され、状態 に 行動 を取る確率を と表記する。

方策を求める際に用いられるゴールは、典型的には現在時刻から無限区間先の未来までにおける「割引された」報酬の累積値が用いられる:

ここで  は割引率  と呼ばれる値であり、現在の報酬と未来の報酬との間における重要度  の差異を表している。 状態が確率的に遷移することから上の値は確率変数となるため、通常はその期待値が用いられる。

4. アルゴリズム
---------

MDP は線形計画法または動的計画法で解くことができる。ここでは後者によるアプローチを示す．

いま，ある方策 を採用した場合における割引報酬和 は現在の状態 のみに依存し、これを 状態価値関数  と呼ぶ。 この状態価値関数 は次式を満たす。 ただし は状態 において方策 を採用した場合における即時報酬の期待値である。

任意の および に対し を満たす方策 を最適方策  と呼ぶ。を採用したときの状態価値関数の最大値 は次のベルマン方程式を満たすSuton．

4.1. 価値反復法
----------

価値反復法 Bellmanは後ろ向き帰納法  とも呼ばれ、ベルマン方程式を満たす価値関数を繰り返し計算により求める。 ロイド・シャープレー  が1953年に発表した確率ゲームに関する論文Shapleyには価値反復法の特殊な場合が含まれるが、このことが認知されたのは後になってからであるKallenberg．

ステップ における価値関数の計算結果を と表記すると、価値反復法における更新式はつぎのように記述される:

上式をすべての状態において値が収束するまで繰り返したときの値を とし、最適方策 を次式で求める。

4.2. 方策反復法
----------

方策反復法 Howardでは、方策固定の下で行われる価値関数の更新  と、価値関数固定のもとで行われる方策の更新  を交互に行うことで最適方策を求める。

次の線形方程式を解き、価値関数を更新する
方策を次式で更新するこれらの操作を がすべての状態に対し変化しなくなるまで繰り返すことで、最適方策を得る。 方策反復法は離散値を取る方策の値が変化しなくなるという明確な終了条件を持つため有限時間でアルゴリズムが終了するという利点を持つ。

5. 拡張と一般化
---------

5.1. 部分観測マルコフ決定過程
-----------------

MDP では方策 を計算する際に現在の状態 が既知であることを仮定している。 実際には状態観測に不確実性が伴う場合などこの仮定が成り立たない場合が多く、このような場合の一般化として部分観測マルコフ決定過程  が用いられる。

5.2. 強化学習
---------

状態遷移確率 や報酬関数 が未知の場合，環境との相互作用を通じてこれらの情報を得ながら行動を決定する必要がしばしば生じる．このような問題は強化学習の枠組みで議論されるSutton．

強化学習における代表的な学習アルゴリズムはQ学習と呼ばれるものである。 Q学習では、行動価値関数  と呼ばれる関数 に着目する。ここで は次のように定義される:

いま，最適方策のもとでの行動価値関数 は を満たす。 すなわち、 を学習することができれば最適方策を獲得することができる。 Q学習では、各試行における遷移前後の状態と入力、および試行で得られる即時報酬の実現値をもとに の値を逐次更新する。 実際の学習プロセスでは、すべての状態を十分サンプリングするため確率的なゆらぎを含むよう学習時の行動が選択される。

強化学習では最適化に必要なパラメータの学習を状態遷移確率・報酬関数を介することなくおこなうことが出来る。 状態数が膨大な場合、強化学習はしばしばニューラルネットワークなどの関数近似と組み合わせられる。

5.3. 学習オートマトン
-------------

機械学習理論における MDP のもう一つの応用は学習オートマトン  と呼ばれる。 これは環境が確率的な挙動を示す場合における強化学習の一つでもある。 学習オートマトンに関する最初の詳細な論文は 1974 年に Narendra と Thathachar によりまとめられたNarendra。 強化学習と同様，学習オートマトンのアルゴリズムも確率や報酬が未知の場合の問題を解くことができる。 Q学習の違いは，価値関数ではく学習の結果を探すために行動の確率を直接求めることである。 学習オートマトンは収束性が解析学の要領で厳密に証明されているNarendra．

5.4. 制約付きマルコフ決定過程
-----------------

制約付きマルコフ決定過程  はマルコフ決定過程の拡張である。 MDP と CMDP には3つの基本的な違いがあるAltman:

ある行動をほかのものの代わりに適用した後でコストが発生する
CMDP は線形計画法のみで解くことが出来る
終端時刻における方策が初期状態に依存するCMDP の応用例は数多く存在し、最近ではロボット工学におけるモーションプランニングに用いられているFeyzabadi。

6. 参考文献
-------

7. 外部リンク
--------

[1] An Introduction by Richard S. Sutton and Andrew G. Barto
[2] by [3]
[4] by Burnetas and Katehakis 
ソフトウェアパッケージ
[5] The Markov Decision Processes  Toolbox.
[6] - An excellent tutorial and Matlab toolbox for working with MDPs.
[7] A package for solving MDPs
[8] A structured MDP solver for download by Jesse Hoey

8. 関連項目
-------

動的計画法
ベルマン方程式
強化学習
Q学習