迷路を方策勾配法で解く - TadaoYamaokaの開発日記

最近買った「つくりながら学ぶ！深層強化学習」という強化学習の本で、迷路を方策勾配法で解くという内容が記載されていたが、数式展開がなく自分で式を導出するのに苦労したのでメモを残しておく。
<br />

この本の迷路の問題の内容は、Webにも掲載されている。
第5回⽅策勾配法で迷路を攻略｜Tech Book Zone Manatee

表形式のパラメータの更新則として以下の式が記載されている。
$\displaystyle \theta_{s,a_j}=\theta_{s,a_j}+\eta\cdot\Delta\theta_{s,a_j} \\ \Delta\theta_{s,a_i}=(N(s,a_j)-p(s,a_j)N(s,a))/T$
なお、書籍とWeb記事では、2つ目の式の符合が誤っている。
引用されている論文と式が違うので、まずここで躓いたのだが、正誤表に符合の誤りについて記載されていた。

さて、問題は2つ目の式の導出である。

以下では、方策勾配定理から書籍の式を導出するまでをできるだけ省略しないで行う。
方策勾配定理の近似式については引用されている論文やこれからの強化学習を参照。

式の導出

出発点となる方策勾配定理は、以下の式で表される。
$\displaystyle \Delta\theta_{s,a} \sim \frac{1}{N} \sum_{i=1}^N \frac{1}{T} \sum_{t=1}^T \frac{\partial}{\partial \theta_{s_t,a_t}} \log p_{\theta_{s_t,a_t}}(a_t^i|s_t^i)z_T^i$

ここで、添え字iはエピソードの番号を表しているが、1エピソードごとに更新するため、この問題では添え字iのシグマは削除できる。
報酬 $z_T^i$ は、ゴールにたどり着いた場合に、たどった経路すべてに割引なしで報酬1を与えるため、この式で常に1となる。
また、状態 $s_t$ と行動 $a_t$ は、1エピソードで同じ状態を通ることがあるため、状態 $s$ と行動状態 $a$ にまとめて記述する。

よって、式は以下のように記述できる。
$\displaystyle \Delta\theta_{s,a} \sim \frac{1}{T} \frac{\partial}{\partial \theta_{s,a}} \log p_{\theta_{s,a}}(a|s)$

ここで、方策 $p_{\theta_{s,a}}$ は、この問題ではSoftmax方策を採用しているため、
$\displaystyle p_{\theta_{s,a}}(s|a) = \frac{e^{\theta_{s,a}}}{\sum_j e^{\theta_{s,a_j}}}$
で与えらえる。

ここから、対数の公式と微分の公式を使って式を展開する。
$\displaystyle \begin{eqnarray} \Delta\theta_{s,a} &\sim& \frac{1}{T} \frac{\partial}{\partial \theta_{s,a}} \log p_{\theta_{s,a}}(a|s) \\ &=& \frac{1}{T} \frac{\partial}{\partial \theta_{s,a}} \log \frac{e^{\theta_{s,a}}}{\sum_j e^{\theta_{s,a_j}}} \\ &=& \frac{1}{T} \frac{\partial}{\partial \theta_{s,a}} (\log e^{\theta_{s,a}} - \log \sum_j e^{\theta_{s,a_j}}) \\ &=& \frac{1}{T} \frac{\partial}{\partial \theta_{s,a}} (\theta_{s,a} - \log \sum_j e^{\theta_{s,a_j}}) \\ &=& \frac{1}{T} (N_1 - \frac{\frac{\partial}{\partial \theta_{s,a}} \sum_j e^{\theta_{s,a_j}}}{\sum_j e^{\theta_{s,a_j}}}) \\ &=& \frac{1}{T} (N_1 - N_0 \frac{e^{\theta_{s,a}}}{\sum_j e^{\theta_{s,a_j}}}) \end{eqnarray}$

ここで、 $N_1$ は、当該エピソードで状態 $s$ で行動 $a$ をとった回数、 $N_0$ は、当該エピソードで状態 $s$ を通った回数を表す。

式の展開で4行目から5行目への展開は、微分の連鎖則を使用している。
つまり、
$\displaystyle \begin{eqnarray} \frac{\partial}{\partial x} \log f(x) &=& \frac{\partial \log f(x)}{\partial f(x)} \frac{\partial f(x)}{\partial x} \\ &=& \frac{1}{f(x)} \frac{\partial f(x)}{\partial x} \end{eqnarray}$
を利用した。

式の5行目から6行目で、
$\displaystyle \frac{\partial}{\partial \theta_{s,a}} \theta_{s,a} = N_1$
となっているが、これは、1つのエピソードで状態 $s$ で行動 $a$ をとることが複数あるため、偏微分の結果は1だが、 $N_1$ 回足す必要があるためである。

また、式の6行目から7行目で、
$\displaystyle \frac{\partial}{\partial \theta_{s,a}} \sum_j e^{\theta_{s,a_j}} = N_0 e^{\theta_{s,a}}$
となっているが、これは、1つのエピソードで状態 $s$ を複数とることがあり、行動 $a$ 以外を取った場合も $\sum_j$ の中に含まれているため、 $N_0$ 回足す必要があるためである。
（補足：指数の微分が指数になる部分の式の展開は省略している。）

さらに、式を展開すると、Softmaxの定義から、
$\displaystyle \begin{eqnarray} \Delta\theta_{s,a} &\sim& \frac{1}{T} \frac{\partial}{\partial \theta_{s,a}} \log p_{\theta_{s,a}}(a|s) \\ &=& \frac{1}{T} (N_1 - N_0 \frac{e^{\theta_{s,a}}}{\sum_j e^{\theta_{s,a_j}}}) \\ &=& \frac{1}{T} (N_1 - N_0 p_{\theta_{s,a}}(a|s)) \end{eqnarray}$
となり、書籍の式が導出できた。