おさらい

モンテカルロ法の説明のために、これまでまとめてきた方法について概要を示します．
以下にこれまで何度も出てきたバックアップ線図を示します．

f:id:shirakonotempura:20190126165021p:plain

状態 $s$ から方策 $a$ をとり、報酬 $R^a_{ss'}$ を得て状態 $s+1$ に遷移している様子を描いています．行動 $a$ を取る確率は方策 $\pi(s,a)$ で決まり、行動 $a$ をとったあとに状態 $s$ から状態 $s+1$ への遷移は遷移確率 $P^a_{ss'}$ によって確率的に決まります．つまり図中に描き切れないほど無数の枝分かれが存在します．

この枝分かれは、エピソードの終着点（Terminalとか言われます）まで繰り返されます．終着点がない場合は、無限に繰り返されることになります．（実際に計算するときは、もう十分だと考える未来まで枝分かれを考慮し、打ち切っていました）．

上のバックアップ線図をもとに、方策状態 $\pi$ に従った場合の状態状態 $s$ の価値を数式で表すと、以下のように書けます．

$$V^\pi (s) = \sum_{a} \pi (s,a) \sum_{s'}P^a_{ss'}[R^a_{ss'} + \gamma V^\pi (s')]$$

この式は、ある状態の価値はその後の状態の価値を用いて表すことができるということを示しています．これをブートストラップと呼びます．価値関数のブートストラップ性を利用して、状態価値関数を反復的に求めることができ、さらにそれを利用して前回は最適な方策を決めることができました．

バックアップ線図で書いたような、枝分かれを確率に従って辿っていき、価値を計算する方法を動的計画法（Dynamic Programming）と呼びます．

動的計画法の問題点

先の式の $[R^a_{ss'} + \gamma V^\pi (s')$ ]の部分は、枝分かれを進んで終着点にたどり着くまでに得られる報酬の総和です．それに方策および遷移確率を乗じているので、先の式で計算しているものは、全ての枝分かれを考慮した報酬の期待値となります．

前述のように動的計画法を使って、最適方策を求めることができましたが、ひとつ大きな制約があります．それは環境のダイナミクスが既知であるということです．

環境のダイナミクスが既知というのは、どういう行動をしたら何が起こるかということを把握できているということを意味します．Grid Worldの例で言えば、右に動くという行動を選択すれば、（遷移確率に従い）右に動こうとするし、グリッドAやBに到達すればA'、B'にワープするということを完全に分かっている状況のことを言います．

現実世界の環境では、行動とその後に起こることを完全に分かっている状況は決して多くありません．仮にあらゆる行動に対して起こりうる変化を全て把握できるとしても、それらをすべてモデリングしておくことは現実的ではありません．
もちろん、学習の対象によっては環境のダイナミクスが既知のケースもあるはずですので、これまでの方法が全く無意味というものではありません．

モンテカルロ法の登場

前段の説明が長くなりましたが、環境のダイナミクスが既知でないくても、これまでやってきたような価値の推定・方策の改善を行う方法がモンテカルロ法になります．

強化学習におけるモンテカルロ法では、エピソードに従ってエージェントは行動をとり報酬を得ます．各状態で実際に得られた報酬の平均をとることで期待値を計算します．

モンテカルロ法のイメージは、元の記事を参照ください．

モンテカルロ法による状態価値推定アルゴリズム

Sutton本5.1章に記載されている、モンテカルロ法を用いた状態価値推定アルゴリズムを以下に示します．これは、初回訪問（First Visit）モンテカルロ法と呼ばれるアルゴリズムになります．

$Initialize:$
$\qquad \pi \leftarrow \;policy \;to \;be \;evaluated$
$\qquad V \leftarrow \;an \;arbitrary \;state-value \;function$
$\qquad Returns(s) \leftarrow \;an \;empty \;list, \;for \;all \; s \in S$

$Repeat \;forever:$
$\qquad \;Generate \;an \;episode\; using \;\pi$
$\qquad \;For \;each \;state \;s \;appearing \;in \;the\;episode$
$\qquad \qquad \;G \leftarrow \;return \;following \;the \;first \;occurrence \;of \;s$
$\qquad \qquad \;Append \;G \;to \; Returns(s)$
$\qquad \qquad \;V(s) \leftarrow \;average(Return(s))$