第1講で定義した強化学習の問題を収める器がマルコフ決定過程（MDP）だ。ほぼすべての強化学習の問題はMDPとして形式化される。マルコフ連鎖から始めて報酬を乗せ、行動を加える形で、一層ずつ積み上げていく。シルバーは講義を通してひとつの例、「学生」を引っ張っていくが、私たちもその例に従う。
講義スライド: PDF
マルコフ性とマルコフ過程
状態がマルコフであるとは、未来を定めるのに今の状態だけで十分だという意味だ（第1講）。過去をすべて知っていても、今より良い予測はできない。
$$\mathbb{P}[S_{t+1} \mid S_t] = \mathbb{P}[S_{t+1} \mid S_1, \dots, S_t]$$状態のあいだを行き来する確率を集めると遷移行列 $\mathcal{P}$ になる。$\mathcal{P}_{ss'} = \mathbb{P}[S_{t+1}=s' \mid S_t=s]$ である。状態集合 $\mathcal{S}$ とこの $\mathcal{P}$ だけからなる、記憶のないランダム過程がマルコフ過程（マルコフ連鎖）だ。
ここでシルバーの学生の例が登場する。状態は授業1、授業2、授業3、合格、パブ、Facebook、そして睡眠だ。学生は確率的にこれらの状態を行き来する。授業中にFacebookにはまることもあれば、合格を目前にしてパブに立ち寄り、前の授業へ戻ってしまうこともある。この行き来の確率が遷移行列であり、「睡眠」は一度入ると出られない終了状態だ。
学生のマルコフ連鎖。「▶ エピソードのサンプリング」を押すと、授業1から出発して遷移確率に従いランダムに状態をたどり、「睡眠」で終わる。回すたびに違う経路が出る。
マルコフ報酬過程（MRP）
マルコフ過程に報酬と割引率を加えるとMRPだ。各状態に報酬 $\mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t=s]$ を割り当て、割引率 $\gamma \in [0,1]$ を置く。学生の例なら、授業はつらいので負の報酬、パブは束の間楽しいので小さな正の報酬、合格は大きな正の報酬を与える、という具合だ。
リターン（収益）は、今から受け取る報酬の割引和だ。
$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$$\gamma$ が0に近ければ目先の報酬だけをつかむ近視眼的なもので、1に近ければ遠い未来まで見通す。割引を置く理由はいくつもある。無限に続く和を収束させ、遠い未来の不確実性を反映し、数学をすっきりさせる。
価値関数はリターンの期待値、すなわちその状態から出発したときに今後受け取る報酬の平均だ。
$$v(s) = \mathbb{E}[G_t \mid S_t = s]$$これを一歩と次の状態の価値に分割したものがベルマン方程式だ。
$$v(s) = \mathcal{R}_s + \gamma \sum_{s'} \mathcal{P}_{ss'}\, v(s')$$今受け取る報酬に、行ける次の状態たちの価値を確率で重みづけして足したものだ。ここには最大値がない。だから線形方程式であり、手で解ける。すべての状態をまとめてベクトルで書くとこうなる。
$$v = \mathcal{R} + \gamma \mathcal{P} v$$$v$ を片側に集めると
$$(I - \gamma \mathcal{P})\,v = \mathcal{R}$$となり、逆行列を掛ければ一度に解ける。
$$v = (I - \gamma \mathcal{P})^{-1}\mathcal{R}$$ただし逆行列の計算は状態数 $n$ に対して $O(n^3)$ なので、この直接解法は状態の少ないMRPでしか使えない。大きなMRPは、これから見る反復法（動的計画法、モンテカルロ、TD）で解く。そして後のMDPで最大値が割り込む瞬間、この線形解法は崩れ、反復法が必ず必要になる。
同じ連鎖に、各状態の報酬が付いた。割引率 γ を変えながらエピソードを取り出すと、同じ経路でもリターン G がどう変わるかが見える。γ が小さいほど目先の報酬だけを、大きいほど遠い未来まで反映する。
マルコフ決定過程（MDP）
MRPに行動を加えるとMDPだ。もはや状態がひとりでに流れていくのではなく、各状態でエージェントが行動を選び、その選択が遷移と報酬を変える。学生の例で言えば、Facebookにはまるか授業を受けるか、パブに行くか勉強するかを学生が決めるのだ。
行動を選ぶ規則が方策 $\pi(a \mid s) = \mathbb{P}[A_t = a \mid S_t = s]$ だ。方策を固定すると二つの価値が測れる。状態価値 $v_\pi(s)$ はその状態で方策 $\pi$ に従うときの期待リターンであり、行動価値 $q_\pi(s,a)$ はその状態で行動 $a$ をとった後に方策に従うときの期待リターンだ。
二つは互いを通して定義され、これがベルマン期待方程式だ。
$$v_\pi(s) = \sum_a \pi(a\mid s)\, q_\pi(s,a), \qquad q_\pi(s,a) = \mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_\pi(s')$$シルバーがベルマン方程式を説明するバックアップ図だ。明るく大きな円が状態、黒い点が行動だ。上の式を図に移したもので、状態 $s$ の価値 $v_\pi(s)$ は方策 $\pi$ で各行動を選んだ後の行動価値 $q_\pi(s,a)$ を平均した値であり、行動価値は報酬 $r$ を受け取り、遷移確率 $\mathcal{P}$ に従って到達した次の状態たちの価値 $v_\pi(s')$ をたどり戻した値だ。価値が下から上へバックアップされていく流れを描いたわけだ。
これで状態ごとに行動を直接選ぶ。授業1から出発して「勉強」と「Facebook」のどちらかを押すと、その行動の報酬を受け取り次の状態へ行く。「パブ」は結果が確率的なので、どこへ跳ぶか分からない。方策とは結局、各状態でどのボタンを押すかを定める規則だ。
最適価値とベルマン最適方程式
私たちが求めるのは、どんな方策でもなく最も良い方策だ。最適状態価値 $v_*(s) = \max_\pi v_\pi(s)$ と最適行動価値 $q_*(s,a) = \max_\pi q_\pi(s,a)$ は、到達しうる最善の価値だ。
$q_*$ が分かれば最適方策はただで手に入る。各状態で $q_*(s,a)$ が最も大きい行動を決定的に選べばよい。どのMDPにも、このような決定的最適方策が一つ以上存在する。
期待値の場所に最大値が入るとベルマン最適方程式だ。
$$v_*(s) = \max_a \left( \mathcal{R}_s^a + \gamma \sum_{s'}\mathcal{P}_{ss'}^a\, v_*(s') \right)$$$\max$ のせいで非線形なので、先のMRPのように一度には解けない。反復法が必要で、それが次の講義の動的計画法だ。
拡張
シルバーは最後に拡張を挙げる。無限・連続状態、部分観測（POMDP）、割引なしの平均報酬といった場合だ。骨組みは同じで、扱いが少しずつ厄介になるだけだ。
次の講義では、MDPを完全に知っていると仮定し、これらのベルマン方程式を反復で解いて最適方策を見つける動的計画法へ入る。