R.S. Sutton 著 強化学習 2nd ed の "§5.4 Monte Carlo Control without Exploring Starts" （方策オン型モンテカルロ法）でつまずいたので、特に数式の理解についてメモを残しておきます。

方策オン型モンテカルロ法とは

モンテカルロ法では様々な状態 s と、その状態で取りうる行動 A(s) を選択した際得られた収益から行動価値関数を更新し、より良い選択ができるよう学習を行います。したがって、様々な状態と行動の組み合わせを試して比較することが重要となるのですが、これを実現するためのひとつの方法が "Monte Calro with Exploring Starts (Monte Calro ES)"と呼ばれる方法です。名前の通り、開始点において方策を固定するのではなく、あらゆる状態行動対を探索し、得られる収益を評価します。
一方、無限の探索を必要とするためこの方法は現実には即しません（特に、実在する環境との相互作用で学習する場合など）。そこで代わりとなるのが、方策オン型モンテカルロ法と、方策オフ型モンテカルロ法です。本記事では前者を扱います。
方策オン型モンテカルロ法は、決定論的な方策は採用せず、常に全ての行動を選択できる余地を残した方策を採用しています。

数式の理解

方策オン型モンテカルロ法の方策（ここではε-greedy 法）は以下式のように表されます。下式の「方策」を採用しているため、本法は「方策オン型」モンテカルロ法と呼ばれます。
　

\begin{equation}
\pi(s|a)= \left \{
\begin{array}{l}
1-\epsilon+\frac{\epsilon}{|A(s)|}　(a\in A {\rm\ is\ greedy}) \\
\frac{\epsilon}{|A(s)|}　(a\in A {\rm\ is\ non-greedy}) 
\end{array}
\right.
\end{equation}

　
まず、この式で一見確率の和が1となっていないことにつまずきました。ここで注意していただきたいことは non-greedy である「全て」の行動ではなく、「それぞれ」の行動をとる確率が $\frac{\epsilon}{|A(s)|}$ であるということです。そう考えると、non-greedy な行動は $(|A(s)|-1)$ だけ存在しますので、「全て」の non-greedy な行動をとる確率は下式のようになります。
　

\frac{\epsilon}{|A(s)|}(|A(s)|-1)

　
上式と greedy な行動をとる確率の和を求めると確かに1となります。

上で紹介した ε-greedy 法は ε-soft 法の一例で、 ε-soft 法は $\pi(s|a)\geq\frac{\epsilon}{|A(s)|}>0$ と定義されます。ここでの関心は、ε-greedy 法が ε-soft 法に対して方策改善となりえるかということです。方策改善定理によると、$q_{\rm \pi}(s,\pi'(s))\geq v_{\rm \pi}(s)$ が成立すれば、$v_{\rm \pi'}(s)\geq v_{\rm \pi}(s)$ が成立し、方策 $\pi'$ (ここではε-greedy)は方策 $\pi$ (ここではε-soft)の改善ということができました。これを証明していきます。

\begin{equation}
\begin{split}
q_{\rm \pi}(s,\pi'(s))&=\sum_{a}\pi'(a|s)q_{\rm \pi}(s,a)\\
&=\frac{\epsilon}{|A(s)|}\sum_{a}q_{\rm \pi}(s,a)+(1-\epsilon)\max_{a}q_{\rm \pi}(s,a)
\end{split}
\end{equation}

　
1段目から2段目への式変形でひっかかりました。あれ? greedy な方策をとる確率って $(1-\epsilon)$ じゃなく $(1-\epsilon+\frac{\epsilon}{|A(s)|})$ じゃなかったけ、と。しかし、ここはよくよく考えてみると、2段目第1項の中に $\frac{\epsilon}{|A(s)|}\max_{a}q_{\rm \pi}(s,a)$ が含まれていることが分かるかと思います。
続きます。
　

\begin{equation}
\begin{split}
&\geq\frac{\epsilon}{|A(s)|}\sum_{a}q_{\rm \pi}(s,a)+(1-\epsilon)\sum_{a}\frac{\pi(a|s)-\frac{\epsilon}{|A(s)|}}{1-\epsilon}q_{\rm \pi}(s,a)\\
&=\frac{\epsilon}{|A(s)|}\sum_{a}q_{\rm \pi}(s,a)-\frac{\epsilon}{|A(s)|}\sum_{a}q_{\rm \pi}(s,a)+\sum_{a}\pi(a|s)q_{\rm \pi}(s,a)\\
&=v_{\pi}(s)
\end{split}
\end{equation}

　
2段目と3段目の不等式にも、ん？となりました。ここで、3段目第2項の総和記号内は「ある状態 $s$ において取りうる可能性のある行動 $a$ をとったときに得られる収益、つまり行動価値関数が、その行動の選択確率によって重みづけされている状態」となります。$(\pi(a|s)-\frac{\epsilon}{|A(s)|})/(1-\epsilon)$ の部分は $a$ について和をとると1となり、第2項は行動価値関数が最大にならない行動も含めた重みづけ和ですので、 $(1-\epsilon)\max_{a}q_{\rm \pi}(s,a)$ 以下の値となり、不等式が成立するという寸法です。ただし、行動価値関数が多くの場合負となることを考えると、$(\pi(a|s)-\frac{\epsilon}{|A(s)|})/(1-\epsilon)$ が負の値をとってしまうことで、不等式が成立しなくなる可能性があります。ですので、上式が「非負」であることを保証してあげる必要があるのですが、これは方策 $\pi$ が ε-soft であることによって満足されます（ε-soft 方策：$\pi(s|a)\geq\frac{\epsilon}{|A(s)|}$）。それ以下の式展開は特に問題は無いと思います。以上で ε-greedy 方策は ε-soft 方策の改善となることが示されました。

まとめ

方策オン型モンテカルロ法の数式理解でつまずいたのでメモを残しました。以下3点がポイントです

・Non-greedyな「それぞれ」の行動をとる確率が $\frac{\epsilon}{|A(s)|}$である
・$\frac{\epsilon}{|A(s)|}\sum_{a}q_{\pi}(s,a)$ の中に $\frac{\epsilon}{|A(s)|}\max_{a}q_{\rm \pi}(s,a)$ が含まれている
・ε-soft 方策という概念を導入することで、ε-greedy 方策を選択することが方策改善となることが示される

最後までご覧いただきありがとうございました。誤りなどありましたらご指摘頂けますと幸いです。