はじめに
JDLA E資格試験で出題される、強化学習の方策ベースにおける方策勾配法や、そのアルゴリズムであるREINFORCEについて解説した記事です。
E資格試験の機械学習パートでは、方策勾配法や方策勾配定理の式、REINFORCEの特徴について出題されます。
なお、他パートの具体的な解説については、下記をご覧ください。
E資格試験に関する私の投稿記事リスト
目次
強化学習アルゴリズム
E資格試験の機械学習パートで出題される、強化学習アルゴリズムを大まかに分類すると下記表になります。
| モデル | 学習方式 | 価値推定方式 | 方策オン/オフ | アルゴリズム |
|---|---|---|---|---|
| モデルベース | 価値/方策ベース | ― | ― | 動的計画法 |
| モデルフリー | 価値ベース | 実績ベース | 方策オン/オフ | MC法 |
| モデルフリー | 価値ベース | TD学習 | 方策オフ | Q学習 |
| モデルフリー | 価値ベース | TD学習 | 方策オン | Sarsa |
| モデルフリー | 方策ベース | ― | ― | REINFORCE |
| モデルフリー | Actor-Critic | TD学習 | ― | A3C |
方策ベース
方策ベースは、価値を最大化する方策を得るために、方策勾配法を利用し、方策を改善する方法のカテゴリです。
REINFORCEやVanillaは、方策ベースに分類されます。
- 方策ベース：明示的な方策があり、現在の方策を改善するアルゴリズム。価値関数は内部的に有するが、行動選択に影響を与えない。まず「方策」を決めてからその「方策」の「価値」を高めるように「方策」を改善していく。
- 価値ベース：明示的な方策はなく、サンプルから学習し、最適な価値関数の値を逐次推定するアルゴリズム。「価値」を求めたうえでその「価値」を高めるような「方策」を選択する。（厳密には方策自身はあるが、価値関数が最大の方策を常に選択する）
価値関数の種類やベルマン方程式については、下記記事をご覧ください。
強化学習の価値関数とベルマン方程式
価値ベースのアルゴリズムについては、下記記事をご覧ください。
価値ベースのアルゴリズム
方策勾配法
問題設定
方策勾配法の問題設定を説明します。
強化学習の目的は、価値の最大化が達成できる行動方策を得ることです。
方策ベースでは、方策を方策関数としてモデル化し、方策を逐次改善していき、価値を最大化する方策を探索します。
まず、確率的方策$\pi$を、パラメータ$\theta \in \Theta$に依存する微分可能な関数$\pi(\theta)$としてモデル化します。
$\pi(\theta)$を方策関数と呼ぶことにします。
モデル化する方法は、tile coding(離散化)、ニューラルネットワークが挙げられます。
方策ベースの深層強化学習は、方策関数を深層学習でモデル化します。
1エピソード内のステップが$t=0,1,\cdots,T-1$とし、ステップ$t$のときの状態を$s(t)$、行動を$a(t)$、即時報酬を$r(t+1)=r(s(t),a(t))$、確率的方策を$\pi(a(t)|s(t);\theta)$、状態遷移確率を$P(s(t+1)|s(t),a(t))$とします。
方策$\pi(a(t)|s(t);\theta)$に従って1エピソードを行動した場合、その同時確率は式(1)で表されます。
\begin{align}
P(\tau)
&=P_{0}\prod_{t=0}^{T-1}P(s(t+1)|s(t),a(t))\pi(a(t)|s(t);\theta)\\
\tau &= \{s(0),a(0),s(1),a(1),\cdots,s(T-1),a(T-1),s(T)\}\\
P_{0}&=P(s(0))
\end{align}
\tag{1}
ただし、$P_{0}$は初期状態確率分布です。なお、エピソード終端であるステップ$t=T-1$において、最後の状態を得るので、状態のみ$s(T)$まで含まれることに注意してください。
目的関数
収益$G(t)$と、状態$s\in S$における状態価値関数$V(s)$は式(2)、(3)で表されます。
\begin{align}
G(t)
&=\sum_{k=0}^{T-1}\gamma^{k}r(t+k+1)
\tag{2}\\
V(s)
&=\mathbb{E}[G(t)|s(t)=s]
\tag{3}
\end{align}
ただし、$\gamma\in [0,1]$は割引率で、収益の総和範囲は1エピソードの終端に合わせています。
方策勾配法では、$t=0$の状態$s(0)=s_{0}\in S$（初期状態確率分布$P_0$から与えられる）から始めるときの状態価値関数$V(s_0)$を、目的関数$J(\theta;s_0)$とします。
よって、目的関数$J(\theta;s_0)$は式(4)で表されます。
\begin{align}
J(\theta;s_0)
&=V(s_0)\\
&=\mathbb{E}[G(0)|s(0)=s_0]\\
&=\mathbb{E}\left[\sum_{k=0}^{T-1}\gamma^{k}r(k+1)|s(0)=s_0\right]
\end{align}
\tag{4}
方策勾配法は、$J(\theta;s_0)$を最大化する方策関数$\pi(\theta)$を得ることが目的であるため、それを実現するパラメータ$\theta$を求めます。
なお、方策関数のパラメータ$\theta$を探索する（方策関数のモデルを逐次変えていく）ため、この最適化問題においては、$\theta$が最適化変数です。
よって、目的関数も$J(\theta;s_0)$と表記しています。
なお、これ以降では、$s_0$を割愛し、$J(\theta)$と表記することにします。
方策勾配法の更新式
方策勾配法は、目的関数$J(\theta)$の最大化問題を方策パラメータ$\theta$について、勾配法で解きます。
よって、方策勾配法の更新式は式(5)で表されます。
\begin{align}
\theta:&=\theta+\eta \boldsymbol{\nabla}J(\theta)\\
\boldsymbol{\nabla}J(\theta) &=\frac{\partial J(\theta)}{\partial \theta}
\end{align}
\tag{5}
ただし、$\eta>0$はステップサイズ（学習率）です。
また、最大化問題なので、勾配の係数の符号が$+$であることに注意してください。
方策勾配$\boldsymbol{\nabla}J(\theta)$の計算が問題となりますが、これは方策勾配定理で得られることが知られています。
方策勾配定理
方策勾配定理
方策勾配定理は上記の問題設定において、方策勾配$\boldsymbol{\nabla}J(\theta)$が得られる定理です。
方策勾配定理から、方策勾配$\boldsymbol{\nabla}J(\theta)$は式(6)、あるいは式(7)で与えられます。
\begin{align}
\boldsymbol{\nabla}J(\theta)&=\mathbb{E}[\boldsymbol{\nabla}\ln \pi(a|s;\theta)Q(s,a)]
\tag{6}\\
\boldsymbol{\nabla}J(\theta)&=\sum_{s \in S}d(s)\sum_{a \in A}\boldsymbol{\nabla} \pi(a|s;\theta)Q(s,a)
\tag{7}
\end{align}
ただし、$\ln x$は自然対数、$Q(s,a)$は状態$s\in S$において、行動$a \in A$を行うときの行動価値関数です。
また、$d(s)$は$s_0$から開始してから方策$\pi(a|s;\theta)$に従って行動したときに状態$s$を訪れる頻度で、式(8)で表されます。
\begin{align}
d(s)&=\sum_{k=0}^{T-1}\gamma^{k}P(s(k)=s|s_0)
\tag{8}
\end{align}
ただし、$P(s(k)=s|s_0)$は全ての行動で周辺化した状態遷移確率です。
方策勾配定理の導出
下記では方策勾配定理を導出します。
状態価値関数$V(s)$と行動価値関数$Q(s,a)$の関係式は式(9)です。
\begin{align}
V(s)&=\sum_{a\in A}\pi(a|s;\theta)Q(s,a)
\tag{9}
\end{align}
確率的方策$\pi(a|s;\theta)$が$\theta$に依存するため、状態価値関数$V(s)$と行動価値関数$Q(s,a)$も$\theta$に依存します。
よって、状態価値関数$V(s)$の$\theta$による偏微分$\boldsymbol{\nabla}V(s; \theta)$は、式(10)で表されます。
\begin{align}
\boldsymbol{\nabla}V(s; \theta)
&=\frac{\partial V(s; \theta)}{\partial \theta}\\
&=\sum_{a\in A}\left[\frac{\partial \pi(a|s;\theta)}{\partial \theta}Q(s,a) + \frac{\partial Q(s,a; \theta)}{\partial \theta}\pi(a|s;\theta)\right]\\
&=\sum_{a\in A}\left[\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a) + \frac{\partial Q(s,a; \theta)}{\partial \theta}\pi(a|s;\theta)\right]
\end{align}
\tag{10}
また、行動価値関数$Q(s,a)$のベルマン方程式は、式(11)で表されます。
\begin{align}
Q(s,a)
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)(r(s,a,s^{\prime})+\gamma V(s^{\prime}))
\end{align}
\tag{11}
よって、行価値関数$Q(s,a)$の$\theta$による偏微分は、式(12)で表されます。
\begin{align}
\frac{\partial Q(s,a; \theta)}{\partial \theta}
=\gamma\sum_{s^{\prime}\in S}P(s^{\prime}|s,a) \frac{\partial V(s^{\prime};\theta)}{\partial \theta} \\
=\gamma\sum_{s^{\prime}\in S}P(s^{\prime}|s,a) \boldsymbol{\nabla}V(s^{\prime}; \theta)
\end{align}
\tag{12}
式(12)を式(10)に代入すると、$\boldsymbol{\nabla}V(s; \theta)$は式(13)に変形できます。
\begin{align}
&\boldsymbol{\nabla}V(s; \theta)\\
&=\sum_{a\in A}\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a) + \left(\gamma\sum_{s^{\prime}\in S}P(s^{\prime}|s,a) \boldsymbol{\nabla}V(s^{\prime}; \theta)\right) \pi(a|s;\theta)\\
&=\sum_{a\in A}\left[\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a) + \gamma \pi(a|s;\theta) \sum_{s^{\prime}\in S}P(s^{\prime}|s,a) \boldsymbol{\nabla}V(s^{\prime}; \theta) \right]\\
&=\sum_{a\in A}\left[\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a)\right] +
\gamma \sum_{a\in A}\left[\pi(a|s;\theta) \sum_{s^{\prime}\in S}P(s^{\prime}|s,a) \boldsymbol{\nabla}V(s^{\prime}; \theta) \right]\\
&=f(s) + \gamma \sum_{s^{\prime}\in S} \left[ \left(\sum_{a\in A}\pi(a|s;\theta) P(s^{\prime}|s,a) \right) \boldsymbol{\nabla}V(s^{\prime}; \theta) \right]\\
&=f(s) +
\gamma \sum_{s^{\prime}\in S} \left[ P(s^{\prime}|s) \boldsymbol{\nabla}V(s^{\prime}; \theta) \right]
\end{align}
\tag{13}
ただし、計算過程で下記のように置きました。
f(s)=\sum_{a\in A}\left[\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a)\right]
式(13)は、$\boldsymbol{\nabla}V(s; \theta)$が再帰的に現れます。
そこで、ステップ$t$において、次の状態$s(t+1)$が取り得る拘束変数を$s^{\prime}(t+1)\in S$、ステップ$t+1$において、次の状態$s(t+2)$が取り得る拘束変数を$s^{\prime}(t+2)\in S$、$\cdots$と表します。
さらに、その拘束変数$s^{\prime}(h)$を変数にとるときの$\boldsymbol{\nabla}V(s^{\prime}(h); \theta)$を下記のように置きます。
\boldsymbol{v}(s^{\prime}(h))=\boldsymbol{\nabla}V(s^{\prime}(h); \theta)
このため、式(13)は$\boldsymbol{v}(s^{\prime}(h))$に関する漸化式として、式(14)で表せます。
\begin{align}
\boldsymbol{v}(s^{\prime}(h))
=f(s^{\prime}(h)) +
\gamma \sum_{s^{\prime}(h+1)\in S} \left[ P(s^{\prime}(h+1)|s^{\prime}(h)) \boldsymbol{v}(s^{\prime}(h+1)) \right]
\end{align}
\tag{14}
よって、$\boldsymbol{v}(s^{\prime}(h))$を再帰的に代入していくと、下記のような関係が続きます。
\begin{align}
&\boldsymbol{v}(s^{\prime}(h))\\
&=f(s^{\prime}(h)) +
\gamma \sum_{s^{\prime}(h+1)\in S} P(s^{\prime}(h+1)|s^{\prime}(h)) \\
&\left(f(s^{\prime}(h+1)) +
\gamma \sum_{s^{\prime}(h+2)\in S} \left[ P(s^{\prime}(h+2)|s^{\prime}(h+1)) \boldsymbol{v}(s^{\prime}(h+2)) \right]\right) \\
&=f(s^{\prime}(h)) +
\gamma \sum_{s^{\prime}(h+1)\in S} \left[ P(s^{\prime}(h+1)|s^{\prime}(h))f(s^{\prime}(h+1))\right] \\
&+ \gamma^2 \sum_{s^{\prime}(h+2)\in S} \sum_{s^{\prime}(h+1)\in S}\left[ P(s^{\prime}(h+2)|s^{\prime}(h+1))P(s^{\prime}(h+1)|s^{\prime}(h)) \boldsymbol{v}(s^{\prime}(h+2)) \right]\\
&=f(s^{\prime}(h)) +
\gamma \sum_{s^{\prime}(h+1)\in S} \left[ P(s^{\prime}(h+1)|s^{\prime}(h))f(s^{\prime}(h+1))\right] \\
&+ \gamma^2 \sum_{s^{\prime}(h+2)\in S} \sum_{s^{\prime}(h+1)\in S}\left[ P(s^{\prime}(h+2)|s^{\prime}(h+1))P(s^{\prime}(h+1)|s^{\prime}(h)) f(s^{\prime}(h+2)) \right]\\
&+ \gamma^3 \sum_{s^{\prime}(h+3)\in S} \sum_{s^{\prime}(h+2)\in S} \sum_{s^{\prime}(h+1)\in S}\\
&\left[ P(s^{\prime}(h+3)|s^{\prime}(h+2)) P(s^{\prime}(h+2)|s^{\prime}(h+1))P(s^{\prime}(h+1)|s^{\prime}(h)) \boldsymbol{v}(s^{\prime}(h+3)) \right]
\end{align}
これを繰り返したとき、第$u$項を表す一般項$F(u)$の無限級数で表せることに帰結します。
この一般項$F(u)$は式(15)で表せます。
\begin{align}
&F(u) \\
&=
\gamma^{u} \sum_{s^{\prime}(h+u)\in S}\cdots \sum_{s^{\prime}(h+1)\in S} \left[ P(s^{\prime}(h+u)|s^{\prime}(h+u-1))\cdots P(s^{\prime}(h+1)|s^{\prime}(h)) f(s^{\prime}(h+u)) \right]\\
&=
\gamma^{u} \sum_{s^{\prime}(h+u)\in S}\cdots \sum_{s^{\prime}(h+1)\in S} \left[ \prod_{j=1}^{u} P(s^{\prime}(h+j)|s^{\prime}(h+j-1)) f(s^{\prime}(h+u)) \right]
\end{align}
\tag{15}
ただし、$u=0$のとき、$F(0)=f(s^{\prime}(h))$とします。
$\boldsymbol{v}(s^{\prime}(h))$は一般項$F(u)$の無限級数なので、式(16)で表せます。
\begin{align}
&\boldsymbol{v}(s^{\prime}(h))\\
&=\sum_{u=0}^{\infty} F(u) \\
&=\sum_{u=0}^{\infty} \left(
\gamma^{u} \sum_{s^{\prime}(h+u)\in S}\cdots \sum_{s^{\prime}(h+1)\in S} \left[ \prod_{j=1}^{u} P(s^{\prime}(h+j)|s^{\prime}(h+j-1)) f(s^{\prime}(h+u)) \right] \right)\\
&=\sum_{u=0}^{\infty} \left(
\gamma^{u} \sum_{x\in S} \left[ P(s^{\prime}(h)\rightarrow x; u) f(x) \right] \right)
\end{align}
\tag{16}
式(16)をステップ$t$における状態が$s(t)=s$の場合に戻すと、$\boldsymbol{\nabla}V(s; \theta)$は式(17)で得られます。
\begin{align}
&\boldsymbol{\nabla}V(s; \theta)\\
&= \boldsymbol{v}(s)\\
&=\sum_{k=0}^{\infty} \left(
\gamma^{k} \sum_{x\in S} \left[ P(s\rightarrow x; k) f(x) \right] \right)\\
&= \sum_{k=0}^{\infty}
\left(\gamma^{k} \sum_{s\in S}
\left[ P(s_0 \rightarrow s; k) \sum_{a\in A}
\left[\frac{\partial \pi(a|s;\theta)}{\partial \theta}Q(s,a)\right]
\right] \right)\\
&=\sum_{s\in S} \left( \sum_{k=0}^{\infty} \gamma^{k} P(s_0 \rightarrow s; k) \right)
\sum_{a\in A}\left[\frac{\partial \pi(a|s;\theta)}{\partial \theta}Q(s,a)\right]\\
\end{align}
\tag{17}
ただし、$P(s\rightarrow x; k)$は、状態が$s(t)=s$から、$k$ステップを経て、任意の状態$s(t+k)=x \in S$へ遷移する同時確率を表します。
$k=0$のときは遷移していないため、下記が成立するとしています。
\sum_{x\in S}P(s\rightarrow x; 0) =1
これで、$\boldsymbol{\nabla}V(s; \theta)$が得られました。
ところで、目的関数は$J(\theta;s_0)=V(s_0)$だったので、$\boldsymbol{\nabla}J(\theta;s_0)$は下記のように変形すると、式(7)が導出されます。
\begin{align}
&\boldsymbol{\nabla}J(\theta;s_0)\\
&= \boldsymbol{\nabla}V(s_0)\\
&= \sum_{k=0}^{\infty} \left(\gamma^{k} \sum_{s\in S} P(s_0 \rightarrow s; k) f(s) \right)\\
&= \sum_{k=0}^{\infty}
\left(\gamma^{k} \sum_{s\in S}
\left[ P(s_0 \rightarrow s; k) \sum_{a\in A}
\left[\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a)\right]
\right] \right)\\
&=\sum_{s\in S} \left( \sum_{k=0}^{\infty} \gamma^{k} P(s_0 \rightarrow s; k) \right)
\sum_{a\in A}\left[\boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a)\right]\\
&= \sum_{s\in S} d(s) \sum_{a\in A} \boldsymbol{\nabla}\pi(a|s;\theta)Q(s,a)
\end{align}
ここで、$d(s)$は下記のように置きました。
d(s) = \sum_{k=0}^{\infty}\gamma^{k} P(s_0 \rightarrow s; k)
さらに、この式を変形すると、下記の式が得られます。
\begin{align}
\boldsymbol{\nabla}J(\theta;s_0)
&= \sum_{s\in S}\sum_{a\in A} d(s) \pi(a|s;\theta)\boldsymbol{\nabla} \ln \pi(a|s;\theta)Q(s,a)
\end{align}
ただし、下記の自然対数の微分を利用しました。
\begin{align}
\boldsymbol{\nabla} \ln \pi(\theta)
&= \frac{\partial \ln \pi(\theta)}{\partial \theta} \\
&= \frac{1}{\pi(\theta)}\frac{\partial \pi(\theta)}{\partial \theta} \\
&= \frac{\boldsymbol{\nabla}\pi(\theta)}{\pi(\theta)}
\end{align}
ここで、右辺の$d(s) \pi(a|s;\theta)$は以下のように変形できます。
\begin{align}
&d(s) \pi(a|s;\theta)\\
&= \sum_{k=0}^{\infty}\gamma^{k} P(s_0 \rightarrow s; k)\pi(a|s;\theta)\\
&= \sum_{k=0}^{\infty}\gamma^{k} P(s(k)=s|s(0)=s0)P(a(k)=a|s(k)=s)\\
&= \sum_{k=0}^{\infty}\gamma^{k} P(s(k)=s,a(k)=a|s(0)=s0)
\end{align}
このため、$d(s) \pi(a|s;\theta)$は、状態が$s(0)=s_0$から、最終ステップにおいて、状態$s$、行動$a$に遷移する確率です。
よって、$\boldsymbol{\nabla}J(\theta)$は、状態$s$、行動$a$に関する$\boldsymbol{\nabla}\ln \pi(a|s;\theta)Q(s,a)$の期待値であるため、下記の通り変形でき、式(6)が導出されました。
\begin{align}
&\boldsymbol{\nabla}J(\theta)\\
&= \sum_{s\in S}\sum_{a\in A} d(s) \pi(a|s)\boldsymbol{\nabla} \ln \pi(a|s;\theta)Q(s,a)\\
&=\mathbb{E}[\boldsymbol{\nabla}\ln \pi(a|s;\theta)Q(s,a)]
\end{align}
方策勾配定理の導出については、下記記事が参考になります。
方策勾配定理の導出
モンテカルロ法による勾配の近似
方策勾配定理により、方策勾配法における方策勾配$\boldsymbol{\nabla}J(\theta)$が期待値として与えられますが、実装上、この期待値を解析的に求めることはできません。
このため、実際には、この期待値を、状態と行動のサンプル$(s(n,t),a(n,t))$を用いたモンテカルロ法によって近似します。
モンテカルロ法によって近似した勾配は式(18)で表されます。
\begin{align}
&\boldsymbol{\nabla}J(\theta)\\
&=\mathbb{E}[\boldsymbol{\nabla}\ln \pi(a|s;\theta)Q(s,a)]\\
&\approx \frac{1}{N}\sum_{n=1}^{N}\frac{1}{T}\sum_{t=1}^{T}
\boldsymbol{\nabla}\ln \pi(a(n,t)|s(n,t);\theta)Q(s(n,t),a(n,t))
\end{align}
\tag{18}
サンプリング数$N$、エピソードの長さを$T$としています。
よって、状態と行動のサンプル$(s(n,t),a(n,t))$は、それぞれ$N\times T$個必要です。
REINFORCE
REINFORCEは方策ベースの方策勾配を用いるアルゴリズムの一つです。
E資格試験では、REINFORCEの方策勾配の式は問われませんが、工夫内容については問われます。
また、エピソード的タスクと連続タスクの二つがありますが、エピソード的タスクの場合に限って説明します。
- エピソード的タスク：タスクの開始状態へリセットするタイミングが決められているタスク（囲碁やゲーム）
- 連続タスク：明確なリセットタイミングがなく、断続的に動作し続けるタスク（ロボットなど）
REINFORCEでは、主に二つの工夫がされています。
一つ目が行動価値関数の近似です。
式(18)のモンテカルロ法によって方策勾配が得られますが、依然として行動価値関数$Q(s(n,t),a(n,t))$は未知です。
よって、REINFORCEでは実際に得られた収益$G(t)$、あるいは即時報酬$r(t+1)$で行動価値関数$Q(s(n,t),a(n,t))$を近似します。
二つ目がベースラインによる勾配推定精度の向上です。
行動価値関数$Q(s(n,t),a(n,t))$にベースライン$b$を加えることで、勾配の推定分散を小さくする効果を狙っています。
ベースライン$b$は行動価値関数$Q(s(n,t),a(n,t))$の平均です。
このため、REINFORCEにおける方策勾配は式(19)で表されます。
\begin{align}
\boldsymbol{\nabla}J(\theta)
&\approx \frac{1}{N}\sum_{n=1}^{N}\frac{1}{T}\sum_{t=1}^{T}
\boldsymbol{\nabla}\ln \pi(a(n,t)|s(n,t);\theta)(r(n,t+1)-b)\\
b
&= \frac{1}{N}\sum_{n=1}^{N}\frac{1}{T}\sum_{t=1}^{T} r(n,t+1)
\end{align}
\tag{19}
ただし、行動価値関数$Q(s(n,t),a(n,t))$の代わりに即時報酬$r(n,t+1)$を用いた場合です。
REINFORCEアルゴリズムの実際の手順や説明については下記記事が参考になります。
REINFORCEの実際の手順
おわりに
E資格向けの強化学習の方策ベースのアルゴリズムについて解説しました。
なお、上記は、2021年2月時点における内容であることにご注意ください。