マルコフ決定過程

マルコフ決定過程が扱う問題

マルコフ決定過程(MDP)は、逐次的な意思決定を定式化した古典的な枠組みです。逐次的な意思決定とは、判断を一度で終えずに、続けて重ねていく問題のことです。強化学習の教科書であるSutton & Bartoの第2版(2018年)は、第3章§3.1でMDPを次のように説明しています。

> MDPs are a classical formalization of sequential decision making, where actions influence not just immediate rewards, but also subsequent situations, or states, and through those future rewards.

この説明によると、MDPで選ぶ行動は、すぐに得られる報酬だけでなく、その後の状況(状態)にも影響します。そして状態を通じて、将来の報酬にも影響します。いまの行動が後の状態と報酬に効いてくるという点が、MDPが表そうとしている問題の特徴です。

有限MDPを組み立てる要素

同じ節では、有限MDPを扱っています。有限MDPでは、次の3つの集合がすべて有限であるとします。

• 状態の集合 S
• 行動の集合 A
• 報酬の集合 R

力学関数 p(s',r|s,a)

有限MDPの振る舞いは、力学関数 p で表されます(式3.2)。

p(s',r|s,a) = Pr{St=s', Rt=r | St-1=s, At-1=a}

この式は、直前の時刻の状態が s で、そこで行動 a を選んだとき、次の時刻に状態 s' になり、報酬 r を受け取る確率を定めています。式の各記号の意味は次のとおりです。

• s:直前の時刻 t-1 の状態 St-1
• a:直前の時刻 t-1 に選んだ行動 At-1
• s':次の時刻 t の状態 St
• r:次の時刻 t に受け取る報酬 Rt

条件の側に置かれているのは、直前の状態 s と行動 a だけです。次の状態と報酬の確率は、この2つを与えて決まる形で書かれています。

強化学習のほかのキーワードとの位置関係

G検定シラバス2024では、マルコフ決定過程は中項目9. 強化学習のキーワードの1つです。同じ中項目には、割引率・状態価値関数・行動価値関数・Q学習・SARSA・方策勾配法・REINFORCE・Actor-Critic・バンディットアルゴリズム・ε-greedy方策・UCB方策も並んでいます。割引率・状態価値関数・行動価値関数・Q学習の詳しい内容は、それぞれの語の説明を参照してください。