はじめに

前回はモンテカルロ法を用いた行動価値関数の評価と方策改善について紹介しました．

強化学習：モンテカルロ法（行動価値評価） - 他力本願で生き抜く（本気）

その際、開始点探査（ES、Exploring Starts）という仮定をおいていましたが、今回はそれを仮定せずにモンテカルロ法で方策改善を行うことを紹介します．

これは私の学習ノートです．詳しく知りたい方は、以下の記事を呼んだ方が身になると思われます．

yamaimo.hatenablog.jp

モンテカルロ法 without ES

Sutton本の5.4章の冒頭で、突如『どうすれば非現実なExploring Startsの仮定を避けられるのだろうか』と出てきます．

これを読んで、そもそもなぜ、ESを外す必要があるだろうと思ったのですが、5.2章によれば、一般的に信頼性がある仮定ではないようです．

エピソードの中で、起こりうる状態行動対がちゃんと選択されればいいけど、選択されない可能性があるから、全部選択されるルールを設けてしまおう！としたのが開始点探査の仮定です．

私の頭では、それでそんなに問題がないような気もしますが、全ての状態を開始点として網羅させるというのは、実際には起こりえないような状況まで仮定してしまっているから良くない、ということでしょうか．難しい・・．

若干消化不良ですが、とにかく非現実なこの仮定を外す方法を考えていきます．

方策オン型（On-policy）と方策オフ型（Off-policy）手法

開始点探査の仮定を取り除く方法として、方策オン型と方策不型と呼ばれる２つの方法が挙げられます．

順に説明していきますが、方策オフ型は複雑すぎて私の知能では理解がおよびませんでしたので、言葉の説明だけにとどめています．ご了承ください．（詳細はSutton本：5.5～5.7章をご覧ください）

方策オン型モンテカルロ

方策オン型モンテカルロではが次の行動を起こす際に使用する方策 $\pi$ に、評価・改善対象の方策を使用します．改善対象の方策を使用することを方策オン（On-policy）と呼んでいます．方策オン型では、方策 $\pi$ を確定的なものからソフトなもの（選ばれる行動は確率に従う）に変更して、任意の状態行動対 $(s,a) \in \;S × /; A(s)$ について、 $\pi(s,a) \gt 0$ であることを保証する方法です．
こうすることで、開始探査点の仮定を取り除いても任意の状態行動対が観測されるようになります．

ソフトなものと言っていますが、具体的にはε-Greeedy方策を指しています．確率的なものであれば何でもいいと思うで、例えばとか、ここでは、という方が正しいかもしれません．

$A^*$ をgeedyな行動としたとき、 $0 \lt \epsilon \lt 1$ の $\epsilon$ に対して以下のように方策 $\pi(s,a)$ が決められます．

$\pi (s,a) = \left \{ \begin{array}{} 1 - \epsilon + \frac{\epsilon}{|A(s)|} \quad (if\;a = A^*)\\ \frac{\epsilon}{|A(s)|} \quad \qquad \;\;\; (otherwise)\\ \end{array} \right.$

以下にε-Greedy方策を用いた、方策オン型モンテカルロ法のアルゴリズムを示します

On-policy first-visit MC control(for ε-soft policies)
Initialize, for all $s \in S$ , $a \in A(s)$
$\qquad Q(s,a) \leftarrow arbitrary$
$\qquad Returns(s,a) \leftarrow empty \; list$
$\qquad \pi(s,a) \leftarrow an \;arbitrary \;\epsilon-soft \;policy$

Repeat forever:
$\qquad (a) \;Generate \;an \;episode \;using \pi$
$\qquad (b) \;For \;each \;pair \;s,a \;appearing \;in \;the \;episode:$
$\qquad \qquad G \leftarrow \;return \;following \;the \;first \;occurrence \;of \;s,a$
$\qquad \qquad Append \;G \;to \;Returns(s,a)$
$\qquad \qquad Q(s,a) \leftarrow \;average(Returns(s,a)$
$\qquad For \;each \;s \;in \;the \;episode:$
$\qquad \qquad A^* \leftarrow arg max_{a} Q(s,a)$
$\qquad \qquad For \;all \;a \in \;A:$

$\qquad \qquad \qquad \pi(s,a) \leftarrow \left \{ \begin{array}{} 1 - \epsilon + \frac{\epsilon}{|A(s)|} \quad (if\;a = A^*)\\ \frac{\epsilon}{|A(s)|} \quad \qquad \;\;\; (otherwise)\\ \end{array} \right.$

方策オフ型モンテカルロ

方策オン型モンテカルロでは、評価・改善用の方策 $\pi$ とは別の方策 $\pi'$ を使って、状態行動対の行動を観測し、その観測結果を使って方策 $\pi$ の評価・改善を行う方法です．たとえ、状態行動対を作り出す方策 $\pi$ が確定的なものであったとしても、 $\pi'$ がソフトなものであれば、開始探査点の仮定を取り除いても任意の状態行動対が観測されるというものです．