強化学習：モンテカルロ法

環境モデル$${Pr(s',r|s,a)}$$が与えられていない場合、エージェントと環境のやり取り（エピソード）をシミュレーションし、そこで観測された状態全ての平均利得を計算する。

First-visit MC

エピソードにおいて、状態$${s}$$を最初に観測した時に計算される総利得を用いて価値関数の推定値を更新する。
　各エピソードが終了してから、各時刻$${t}$$での利得$${G_t}$$を計算し、これを目的利得として、学習率を$${\alpha}$$を用いて、推定価値を以下のように更新する。
$${\nu(s_t)_{new}= \nu(s_t)+\alpha(G_t - \nu(s_t))}$$

モンテカルロ法では、ポリシーの更新は、ランダムなポリシーを初期値にして、行動価値関数を通じてポリシーを評価する。
$${\pi(s)\stackrel{\text{def}}{=}{\text{argmax}}_a q(s,a)}$$と、行動価値関数を最大化する行動を選ぶと定義することもできるが、局所解に陥る可能性を回避するために、微小な$${1 \gg \epsilon \gt 0 }$$を入れて、状態$${s}$$において最適でない全ての行動を$${\displaystyle{\frac{\epsilon}{|A(s)|}}}$$の確率で選び、最適行動は、$${\displaystyle{1-\frac{(|A(s)|-1)\epsilon}{|A(s)|}}}$$と、１からずらした確率で選ぶようにする。