強化学習：方策勾配法

強化学習法における、状態から行動を決める方策を、パラメータ$${\theta}$$を用いて更新していく方法を、方策勾配法と呼ぶ。
方策勾配法を行うにあたっては、方策$${\pi_{\theta}(a|s)}$$が$${\theta}$$に関して微分可能であることが条件となる。
目的関数$${J(\theta)}$$を、期待収益$${E_{\pi}[G_t|s_t]}$$とすると、報酬を最大にしたいので、勾配上昇法で最適化する。よって、学習率を$${\eta}$$とし、$${\theta}$$の更新は
$${\theta_{t+1}=\theta_{t}+\eta {\bm \nabla}_{\theta}J(\theta)}$$
で与えられる。
$${E_{\pi}[G_t|s_t]}$$は状態価値関数であり、$${G_t=R_t + \gamma G_{t+1}}$$から、
$${\nu_{\pi}(s)=E_{\pi}[G_t|s_t]=\sum_{a\in A}\pi(a|s)\sum_{s'\in S}Pr(s’,r|s,a)[r+\gamma \nu^{\pi}(s')]}$$
となる。
これを用いて、
$${{\bm \nabla}_\theta \nu_{\pi}(s)=\sum_{a\in A}{\bm \nabla}_{\theta}\pi(a|s)\sum_{s'\in S}Pr(s’,r|s,a)[r+\gamma \nu^{\pi}(s')] + \sum_{a\in A}\pi(a|s)\sum_{s'\in S}Pr(s’,r|s,a)[r+\gamma {\bm \nabla}_{\theta}\nu^{\pi}(s')]}$$
となり、
$${{\bm \nabla}_\theta \nu_{\pi}(s’)=\sum_{a\in A}{\bm \nabla}_{\theta}\pi(a|s')\sum_{s''\in S}Pr(s'',r|s',a)[r+\gamma \nu^{\pi}(s'')] + \sum_{a\in A}\pi(a|s')\sum_{s''\in S}Pr(s'',r|s',a)[r+\gamma {\bm \nabla}_{\theta}\nu^{\pi}(s'')]}$$
が成立する。
さらに、行動価値関数$${q_{\pi}(s,a)}$$が、
$${q_{\pi}(s,a)=\sum_{s'\in S}Pr(s',r|s,a)[r+\gamma \nu_{\pi}(s')]}$$で与えられることから、

$${{\bm \nabla}_\theta \nu_{\pi}(s)=\sum_{a\in A}{\bm \nabla}_{\theta}\pi(a|s) q_{\pi}(s,a)}$$
$${ + \gamma\sum_{a,a'\in A,s'\in S} \pi(a|s){\bm \nabla}_{\theta}\pi(a'|s') Pr(s'|s,a)q_{\pi}(s',a')}$$
$${ + \gamma^2\sum_{a,a'\in A,s',s''\in S} \pi(a|s)\pi(a'|s'')Pr(s'|s,a)Pr(s''|s',a) {\bm \nabla}_{\theta}\nu_{\pi}(s'')}$$
$${=\sum_{a\in A}{\bm \nabla}_{\theta}\pi(a|s) q_{\pi}(s,a)}$$
$${+\gamma\sum_{a \in A, s' \in S}\pi(a|s)Pr(s'|s,a)\sum_{a'\in A}{\bm \nabla}_{\theta}\pi(a'|s') Pr(s'|s,a)q_{\pi}(s',a')}$$
$${ + \gamma^2\sum_{a\in A,s'\in S} \pi(a|s)Pr(s'|s,a)\sum_{s''\in S, a'\in A}\pi(a'|s'')Pr(s''|s',a') {\bm \nabla}_{\theta}\nu_{\pi}(s'')}$$
ここで、見易さのために
$${f(s)=\sum_{a\in A}{\bm \nabla}_{\theta}\pi(a|s) q_{\pi}(s,a)}$$
$${P_{\pi}^1(s'|s)=\sum_{a\in A}\pi(a|s)Pr(s'|s,a)}$$
$${P_{\pi}^2(s''|s)=\sum_{s'\in S}\sum_{a\in A}\pi(a|s)Pr(s'|s,a)\sum_{a'\in A}\pi(a'|s'')Pr(s''|s',a')}$$
を導入する。
これによって、上式は、
$${{\bm \nabla}_\theta \nu_{\pi}(s)=f(s) + \gamma \sum_{s'\in S}P_{\pi}^1(s'|s)f(s') + \gamma^2\sum_{s'\in S}P_{\pi}^2(s'|s){\bm \nabla}_{\theta}\nu_{\pi}(s')}$$となり、
$${{\bm \nabla}_\theta \nu_{\pi}(s)=\sum_{s'\in S}\sum_{t=0}^{\infty}\gamma^{t}Pr_{\pi}^{t}(s'|s)f(s')}$$
で与えられる。
ここで、状態$${s}$$から状態変化を続けて$${s''}$$まで到達する全ての確率$${\sum_{t=0}^{\infty}Pr_{\pi}^{t}(s'|s)}$$を$${{\mathcal Pr}_\pi(s')}$$と記せば、
$${{\bm \nabla}_\theta \nu_{\pi}(s)=\sum_{s'\in S}{\mathcal Pr}_\pi(s')\sum_{a\in A}{\bm \nabla}_{\theta}\pi(a|s) q_{\pi}(s,a)}$$
となる。
ここで、$${{\bm \nabla}_{\theta}\log\pi_{\theta}(a|s)=\displaystyle{\frac{\partial \pi}{\partial {\bm \theta}} \frac{1}{\pi} }}$$を用いて、
方策勾配法の期待報酬のパラメータ微分は、以下のように表されることになる。
$${{\bm \nabla}_\theta J(\theta)=\sum_{s\in S}{\mathcal Pr}(s)\sum_{a \in A}\pi_\theta(a|s){\bm \nabla}_{\theta}\log \pi_{\theta}(a|s) q_{\pi}(s,a) = E_{\pi_\theta}[{\bm \nabla}_{\theta}\log \pi_{\theta}(a|s) q_{\pi}(s,a) ]}$$
ただし、この計算は解析的には不可能であり、実際にはエピソード数$${N}$$と更新数$${T}$$から、
$${{\bm \nabla}_\theta J(\theta)\sim \displaystyle{ \frac{1}{N} \sum_{n=1}^{N}\frac{1}{T}\sum_{t=1}^{T}{\bm \nabla}_{\theta}\log \pi_{\theta} (a^{(n)}_t|s^{(n)}_t) q_{\pi}(s^{(n)}_t,a^{(n)}_t)}}$$
と近似される。