方策勾配法（Policy Gradient）とは、パラメータを用いて方策を関数近似し、期待報酬（expected reward）を最大化するようにパラメータを更新する強化学習手法です。方策をパラメータ化することで、状態や行動が連続値である問題を扱うことが可能となります。
方策を表現するパラメータを\(\theta\)とすると、「現在のパラメータ\(\theta\)に対する期待収益\(\rho\)の勾配\(\frac{\partial\rho}{\partial\theta}\)」に基づいたパラメータ更新は下式で行われます。下式を用いたパラメータ更新を繰り返すことで、方策を最適化します。
$$\theta\ {\leftarrow}\ \theta+\alpha\frac{\partial\rho}{\partial\theta}$$
方策\(\pi_\theta\)のもとでの期待収益\(\rho(\pi_\theta)\)は、二つの方法で関数近似できます。
平均報酬和で定義する方法
方策\(\pi_\theta\)のもとでの期待収益\(\rho(\pi_\theta)\)を、\(\infty\)回サンプリングした報酬値の平均で表現できると仮定し、下式に示します。
\begin{eqnarray}
\rho(\pi_\theta)
&=& \underset{n\rightarrow\infty}{\lim}\frac{1}{n}E\left\{r_1+r_2+\cdots+r_n|\pi_\theta\right\} \\[7pt]
&=& \sum_{s}d^{\pi_\theta}(s)\sum_{a}\pi_\theta(s,a)R_s^a
\end{eqnarray}
$$d^{\pi_\theta}(s)=\underset{t\rightarrow\infty}{\lim}\text{Pr}\left\{s_t=s|s_0,\pi_\theta\right\}$$
ここで、\(\pi_\theta(s,a)\)は、方策\(\pi_\theta\)に従ったときに状態\(s\)で行動\(a\)を選択する確率であり、\(R_s^a\)は、状態\(s\)で行動\(a\)をとったときに与えられる報酬です。また、\(d^{\pi_\theta}(s)\)は、方策\(\pi_\theta\)に従った場合の状態\(s\)の定常状態分布です。
方策\(\pi_\theta\)のもとでの行動価値関数\(Q^{\pi_\theta}(s,a)\)は下式で表現されます。
$$Q^{\pi_\theta}(s,a)=\sum_{t=1}^{\infty}E\left\{r_t-\rho(\pi_\theta)|s_0=s,a_0=a,\pi_\theta\right\},\ \ \ {\forall}s\in\mathcal{S},\ {\forall}a\in\mathcal{A}$$
割引報酬和で定義する方法
方策\(\pi_\theta\)のもとでの期待収益\(\rho(\pi_\theta)\)を、割引報酬和で近似できると仮定します。
方策\(\pi_{\theta}\)のもとでの期待収益\(\rho(\pi_{\theta})\)、行動価値関数\(Q^{\pi_{\theta}}(s,a)\)は下式で表現されます。
$$\rho(\pi_{\theta})=E\left\{\sum_{t=1}^{\infty}{\gamma}^{t-1}r_t|s_0,\pi_\theta\right\}$$
$$Q^{\pi_{\theta}}(s,a)=E\left\{\sum_{k=1}^{\infty}\gamma^{k-1}r_{t+k}|s_t=s,a_t=a,\pi_\theta\right\}$$
$$d^{\pi_{\theta}}(s)=\sum_{s}d^\pi(s)\sum_{a}\frac{\partial\pi_{\theta}(s,a)}{\partial\theta}Q^{\pi_\theta}(s,a)$$
ここで、\(d^{\pi_{\theta}}(s)\)は、方策\(\pi_{\theta}\)に従った場合の状態\(s\)の割引状態分布です。
期待報酬\(\rho\)の勾配は以下の式で表現され、方策勾配定理（policy gradient theorem）と呼ばれます。
$$\frac{\partial\rho(\pi_{\theta})}{\partial{\theta}}=\sum_{s}d^{\pi}(s)\sum_{a}\frac{\partial\pi_{{\theta}}(s,a)}{\partial{\theta}}Q^{\pi_{\theta}}(s,a)$$
方策勾配定理の導出はComing soon…
確率的方策勾配法（Stochastic Policy Gradient）とは、確率的方策（stochastic policy）を最適化対象とした方策勾配法です。確率的方策\(\pi(a|s)\)は、状態\(s\)においてエージェントが選択する行動\(a\)の確率分布であり、下式で表現されます。
\begin{eqnarray}
\pi(a|s) = P\left( a|s \right)
\end{eqnarray}
まず、定常状態分布と方策の積\(d(s)\pi(a|s)\)が訪問する状態\(s\)とそこで選択される行動\(a\)に関する期待値に相当することを踏まえ、方策勾配定理を以下のように変形します。
\begin{eqnarray}
\frac{{\partial}J(\theta)}{\partial\theta}
&=& \sum_{s}d^{\pi}(s)\sum_{a}\frac{\partial\pi_{{\theta}}(s,a)}{\partial{\theta}}Q^{\pi_{\theta}}(s,a) \\[7pt]
&=& \sum_{s} \sum_{a} \pi_\theta(a|s) d(s) \frac{1}{\pi_\theta(a|s)} \frac{\partial\pi_\theta(a|s)}{\partial\theta} Q(s,a) \\[7pt]
&=& E\left[ \frac{1}{\pi_\theta(a|s)} \frac{\partial\pi_\theta(a|s)}{\partial\theta} Q(s,a) \right] \\[7pt]
&=& E\left[ \frac{\partial\log\pi_\theta(a|s)}{\partial\theta} Q(s,a) \right]
\end{eqnarray}
ただし、上式で表現される勾配を解析的に求めることはできないため、確率的方策\(\pi_\theta\)に基づいた行動によって得られるサンプルデータを用いて近似します。具体的には、エージェントが方策\(\pi_\theta\)に従い、\(T\)ステップの行動を\(M\)エピソード分選択する場合、モンテカルロ近似によって方策勾配定理は下式で表現されます。
\begin{eqnarray}
\frac{{\partial}J(\theta)}{\partial\theta} \simeq \frac{1}{M} \sum_{m=0}^{M-1} \frac{1}{T} \sum_{t=0}^{T-1} \frac{\partial\log\pi_\theta(a_t^m|s_t^m)}{\partial\theta} Q(s_t^m,a_t^m)
\end{eqnarray}
REINFORCEとは、行動価値を報酬で近似し、ベースラインを平均報酬とした強化学習手法です。
ベースライン
ここで、ベースラインとは、学習安定化のために更新パラメータ\({\nabla}J({\theta})\)の分散を小さくする工夫のことです。具体的には、方策勾配定理の右辺からベースライン\(B(s)\)を引きます。
$$E_{\pi_{{\theta}}}\left[{\nabla}\log\pi_{{\theta}}(a|s)\left\{Q^{\pi_{{\theta}}}(s,a)-B(s)\right\}\right]$$
\(B(s)\)を引いても勾配期待値は変わらず、分散だけが変わるため、方策パラメータの更新が安定します。
REINFORCE
前述の通り、行動価値を報酬で近似します。
$$Q^{\pi_{\theta}}(s_t,a_t)=r_{t+1}+q^{\pi_{\theta}}(s_{t+1},a_{t+1})\ {\approx}\ r_{t+1}$$
また、モンテカルロ法で得られる報酬の平均値をベースラインとし、REINFORCEにおける勾配期待値を得ます。
$${\nabla}J(\theta)\ {\approx}\ \frac{1}{M}\sum_{m=0}^{M-1}\frac{1}{T}\sum_{t=0}^{T-1}{\nabla}\log\pi_{\theta}(a_{t,m}|s_{t,m})\left\{r_{t,m}-\frac{1}{M}\sum_{m=0}^{M-1}\frac{1}{T}\sum_{t=0}^{T-1}r_{t,m}\right\}$$
決定的方策勾配法（Deterministic Policy Gradient; DPG）とは、。決定的方策\(\pi(s)\)は、任意の状態\(s\)に対して一意の行動\(a\)を返す関数であり、下式で表現されます。
\begin{eqnarray}
\pi(s) = a
\end{eqnarray}
DPGの方策勾配定理は、下式で表現されます。
\begin{eqnarray}
\frac{{\partial}J}{\partial\theta}(\pi_\theta)
&=& \int_{\mathcal{S}} d^{\pi_\theta}(s) \left. \frac{{\partial}Q^{\pi_\theta}(s,a)}{{\partial}a} \right|_{a=\pi_\theta(s)} ds \\[7pt]
&=& E_{s\ \sim\ d^{\pi_\theta}} \left[ \frac{\partial\pi_\theta(s)}{\partial\theta} \left. \frac{{\partial}Q^{\pi_\theta}(s,a)}{{\partial}a} \right|_{a=\pi_\theta(s)} \right] \\[7pt]
&=& E_{s\ \sim\ d^{\pi_\theta}} \left[ \frac{{\partial}Q^{\pi_\theta}\left(s, \pi_\theta(s)\right)}{\partial\theta} \right]
\end{eqnarray}
ここで、\(d^{\pi_\theta}(\cdot)\)は方策\(\pi_\theta\)のもとでの割引状態分布、\(Q^{\pi_\theta}(\cdot,\ \cdot)\)は方策\(\pi_\theta\)のもとでの行動価値関数です。つまり、方策勾配定理は、行動価値関数の勾配\(\nabla_\theta\ Q^{\pi_\theta}\left(s, \pi_\theta(s)\right)\)に対して、状態\(s\)についての期待値をとった形と一致しています。
ここで、SPGの方策勾配定理を再掲します。
\begin{eqnarray}
\frac{{\partial}J}{\partial\theta}
&=& \int_{\mathcal{S}} \rho^{\pi}(s) \int_{\mathcal{A}} \frac{\partial}{\partial\theta} \log\pi_\theta(a|s) Q^{\pi}(s,a) dads \\[7pt]
&=& E_{s\ \sim\ \rho^{\pi},\ a\ \sim\ \pi_\theta} \left[ \frac{\partial}{\partial\theta}\log\pi_\theta(a|s)Q^{\pi_\theta}(s,a) \right]
\end{eqnarray}
二つの方策勾配定理を比較すると、DPGでは状態空間について期待値をとっているのに対して、SPGでは状態空間と行動空間に対して期待値をとっています。したがって、方策勾配を推定するために必要なサンプル数は、DPGの方がSPGよりも小さくなります。
参考文献
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An Introduction. The MIT Press (1998).
Sutton, Richard S., David McAllester, Satinder Singh, and Yishay Mansour. “Policy gradient methods for reinforcement learning with function approximation.” Advances in neural information processing systems 12 (1999).