マルコフ決定過程(Markov decision process)

今回はマルコフ決定過程(Markov decision process)を紹介します。

マルコフ決定過程とは

マルコフ決定過程は確率過程の一種で、強化学習のタスクとしてよく用いられます。
Markov decision processの頭文字をとってMDPと呼ばれます。
マルコフ決定過程は、以下の要素から構成されます。

状態の集合\(S\)
行動の集合\(A\)
状態遷移関数\(P(s_{t+1}|s_{t}, a_{t})\)、この\(P(s_{t+1}|s_{t}, a_{t})\)は状態\(s_t \in S\)において行動\(a_t \in A\)を行った時の\(s_{t+1} \in S\)への遷移確率
報酬関数\(R(s_{t}, a_{t})\)、\(R(s_{t}, a_{t})\)は状態\(s_t\)において行動\(a_t\)を行った時に得られる報酬。（正確には報酬の期待値）

マルコフ決定過程の特徴は、
状態遷移関数\(P(s_{t+1}|s_{t}, a_{t})\)と報酬関数\(R(s_{t}, a_{t})\)ともに現在の状態\(s_t\)と行動\(a_t\)のみに依存するということです。
(これをマルコフ性といいます。)

つまり、次の状態への遷移や得られる報酬が、過去の状態\(s_0, \cdots , s_{t-1}\)、行動\(a_0, \cdots , a_{t-1}\)に依存せず、現在の状態\(s_t\)、行動\(a_t\)のみによって決定されるということです。

特に状態の集合\(S\)、行動の集合\(A\)が有限の場合、有限MDPといいます。