マルコフ決定過程とは

マルコフ決定過程（MDP）は、強化学習で扱う問題を数式で表すための枠組みです。1957年のリチャード・ベルマンの論文などで定式化が進みました。

構成要素

マルコフ決定過程は、主に次の要素で表します。

• 状態：エージェントが置かれている状況（盤面、ロボットの位置など）
• 行動：各状態でエージェントが選べる行動
• 状態遷移確率：ある状態である行動をとったとき、次にどの状態へ移るかの確率
• 報酬：行動の結果として環境から受け取る数値
• 割引率：将来の報酬を、現在から見てどれだけ割り引くかを表す0以上1以下の値

エージェントは、状態に応じて行動を選ぶ規則（方策）に従って動きます。目標は、将来にわたって受け取る報酬を割り引いて足し合わせた値（収益）の期待値が最大になる方策を見つけることです。

マルコフ性

「マルコフ」は、次の状態の確率が現在の状態と行動だけで決まり、それより前にどのような経緯をたどったかには左右されない、という性質（マルコフ性）を指します。すごろくで次に止まるマスは、いまのマスと出た目で決まり、そこまでの道のりには関係しません。

この仮定があるので、価値をいまの状態だけの関数として考えられます。「いまの状態にどれだけの価値があるか」を表すのが状態価値関数、「いまの状態でこの行動をとる価値」を表すのが行動価値関数です。これらの価値は、次の状態の価値と結び付けたベルマン方程式で計算します。

強化学習との関係

状態遷移確率と報酬がすべてわかっていれば、動的計画法で最適な方策を計算できます。強化学習は、これらがわからない場合でも、試行錯誤で得た経験から最適な方策に近づく方法と位置づけられます。Q学習やSARSAは、その代表的な手法です。

センサーの情報だけでは状態を完全には観測できないこともあります。このような問題は、部分観測マルコフ決定過程（POMDP）として扱われます。

覚え方

「次の一歩は、いまの場所と行動だけで決まる」と覚えます。