マルコフ決定過程

マルコフ決定過程（マルコフけっていかてい、）は、状態遷移が確率的に生じる動的システム（確率システム）の確率モデルであり、状態遷移がマルコフ性を満たすものをいう。
MDP は不確実性を伴う意思決定のモデリングにおける数学的枠組みとして、強化学習など動的計画法が適用される幅広い最適化問題の研究に活用されている。
MDP は少なくとも1950年代には知られていたが、研究の中核は1960年に出版された Ronald A. Howard の "Dynamic Programming and Markov Processes" に起因する。
MDP はロボット工学や自動制御、経済学、製造業を含む幅広い分野で用いられている。
概要.
マルコフ決定過程は離散時間における確率制御過程 (stochastic control process) である。
各時刻において過程 (process) はある状態 (state) を取り、意思決定者 (decision maker) はその状態において利用可能な行動 (action) を任意に選択する。
その後過程はランダムに新しい状態へと遷移し、その際に意思決定者は状態遷移に対応した報酬 (reward) を受けとる。
遷移後の状態 formula_1 、および得られる報酬の値 formula_2 は現在の状態 formula_3 と行動 formula_4 のみに依存し、formula_3 と formula_4 が与えられたもとでそれより過去の状態および行動と条件付き独立となる。
言い換えると、マルコフ決定過程の状態遷移はマルコフ性を満たす。
マルコフ決定過程はマルコフ連鎖に（選択可能な）行動、および（行動を計画する動機を与える）報酬を追加し拡張したものであると解釈できる。
逆に言えば、各ステップにとる行動がそのステップにおける状態のみ依存するとき、マルコフ決定過程は等価なマルコフ連鎖に置き換えることが出来る。
定義.
有限マルコフ決定過程 (finite Markov decision process; finite MDP) は4つの要素の組 formula_7で表される。ここで各要素はそれぞれ次を意味する。
遷移関数 formula_12 は状態 formula_3 にあり行動 formula_4 を取ったときの状態 formula_1 への状態遷移確率 formula_16 である。
また報酬関数 formula_17 は状態 formula_3 から formula_1 に行動 formula_4 を伴い遷移する際に得られる即時報酬 (immediate reward) 、またはその期待値 formula_21 を表す。
問題設定.
MDP における基本的な問題設定は、現在の状態が formula_3 が与えられたときに意思決定者の取る行動 formula_23 を既定する方策 (policy) を求めることである。
方策は通常 formula_24 の条件付き分布 formula_25 として規定され、状態 formula_3 に 行動 formula_4 を取る確率を formula_28 と表記する。
方策を求める際に用いられるゴール（目的関数）は、典型的には現在時刻から無限区間先の未来までにおける「割引された」報酬の累積値が用いられる:
formula_29
ここで formula_30 は割引率 (discount rate) と呼ばれる値であり、現在の報酬と未来の報酬との間における重要度 (importance) の差異を表している。
状態が確率的に遷移することから上の値は確率変数となるため、通常はその期待値が用いられる。
アルゴリズム.
MDP は線形計画法または動的計画法で解くことができる。ここでは後者によるアプローチを示す．
いま，ある（定常な）方策 formula_31 を採用した場合における割引報酬和 formula_32 は現在の状態 formula_3 のみに依存し、これを 状態価値関数 (state-value function) と呼ぶ（formula_34 は方策 formula_31 の下での条件付き期待値）。
この状態価値関数 formula_36 は次式を満たす。
formula_37
ただし formula_38 は状態 formula_3 において方策 formula_31 を採用した場合における即時報酬の期待値である。
任意の formula_41 および formula_42 に対し formula_43 を満たす方策 formula_44 を最適方策 (optimal policy) と呼ぶ。
formula_44を採用したときの状態価値関数の最大値 formula_46 は次のベルマン方程式を満たす．
formula_47
価値反復法.
価値反復法 (value iteration)は後ろ向き帰納法 (backward induction) とも呼ばれ、ベルマン方程式を満たす価値関数を繰り返し計算により求める。 ロイド・シャープレー が1953年に発表したに関する論文には価値反復法の特殊な場合が含まれるが、このことが認知されたのは後になってからである．
ステップ formula_48における価値関数の計算結果を formula_49 と表記すると、価値反復法における更新式はつぎのように記述される:
formula_50
上式をすべての状態において値が収束するまで繰り返したときの値を formula_51 とし、最適方策 formula_44 を次式で求める。
formula_53
方策反復法.
方策反復法 (policy iteration)では、方策固定の下で行われる価値関数の更新 (policy evaluation) と、価値関数固定のもとで行われる方策の更新 (policy improvement) を交互に行うことで最適方策を求める。
これらの操作を formula_31 がすべての状態に対し変化しなくなるまで繰り返すことで、最適方策を得る。
方策反復法は離散値を取る方策の値が変化しなくなるという明確な終了条件を持つため有限時間でアルゴリズムが終了するという利点を持つ。
拡張と一般化.
部分観測マルコフ決定過程.
MDP では方策 formula_57 を計算する際に現在の状態 formula_3 が既知であることを仮定している。
実際には状態観測に不確実性が伴う場合などこの仮定が成り立たない場合が多く、このような場合の一般化として部分観測マルコフ決定過程 (Partially Observable Markov Decision Process; POMDP) が用いられる。
強化学習.
状態遷移確率 formula_59 や報酬関数 formula_60 が未知の場合，環境との相互作用を通じてこれらの情報を得ながら行動を決定する必要がしばしば生じる．このような問題は強化学習の枠組みで議論される．
強化学習における代表的な学習アルゴリズムはQ学習と呼ばれるものである。
Q学習では、行動価値関数 (action-value function) と呼ばれる関数 formula_61 に着目する。ここで formula_61 は次のように定義される:
formula_63
いま，最適方策のもとでの行動価値関数 formula_64 は formula_65 を満たす。
すなわち、formula_66 を学習することができれば（モデルのパラメータを直接求めることなく）最適方策を獲得することができる。
Q学習では、各試行における遷移前後の状態と入力、および試行で得られる即時報酬の実現値をもとに formula_67 の値を逐次更新する。
実際の学習プロセスでは、すべての状態を十分サンプリングするため確率的なゆらぎを含むよう学習時の行動が選択される。
強化学習では最適化に必要なパラメータの学習を状態遷移確率・報酬関数を介することなくおこなうことが出来る（価値反復法や方策反復法ではそれらの明示的な仕様（各状態間の遷移可能性，報酬関数の関数形など）を与える必要がある）。
状態数（および行動の選択肢）が膨大な場合、強化学習はしばしばニューラルネットワークなどの関数近似と組み合わせられる。
学習オートマトン.
機械学習理論における MDP のもう一つの応用は学習オートマトン (Learning Automata) と呼ばれる。
これは環境が確率的な挙動を示す場合における強化学習の一つでもある。
学習オートマトンに関する最初の詳細な論文は 1974 年に Narendra と Thathachar によりまとめられた（そこでは有限状態オートマトンと明示的に記載されている）。
強化学習と同様，学習オートマトンのアルゴリズムも確率や報酬が未知の場合の問題を解くことができる。
Q学習の違いは，価値関数ではく学習の結果を探すために行動の確率を直接求めることである。
学習オートマトンは収束性が解析学の要領で厳密に証明されている．
制約付きマルコフ決定過程.
制約付きマルコフ決定過程 (Constrained Markov Decision Process; CMDP) はマルコフ決定過程の拡張である。
MDP と CMDP には3つの基本的な違いがある:
CMDP の応用例は数多く存在し、最近ではロボット工学におけるモーションプランニングに用いられている。