#はじめに
JDLA E資格試験で出題される強化学習の価値関数とベルマン方程式について解説した記事です。
E資格試験の機械学習パートでは、価値関数やベルマン方程式の式について出題されます。
なお、他パートの具体的な解説については、下記をご覧ください。
[E資格試験に関する私の投稿記事リスト][link-1]
[link-1]:https://qiita.com/fridericusgauss/items/5a97f2645cdcefe15ce0
強化学習の基礎については下記の記事をご覧ください。
[強化学習の基礎][link-2]
[link-2]:https://qiita.com/fridericusgauss/items/baf720e21f6811bd8908
###目次
#周辺化と条件付き期待値
ベルマン方程式では、同時確率、条件付き確率や条件付き期待値の性質を理解しておく必要があります。
###条件付き確率の周辺化
同時確率分布$P(X,Y)$を確率変数$Y$で周辺化するとは、$Y$の全ての状態について$P(X,Y)$の総和を取り、周辺分布$P(X)$を求めることです。
$P(X,Y)$の確率変数$Y$に関する周辺化は式(1)で表されます。
P(X) = \sum_{y\in \Omega_{Y}} P(X,Y=y)
\tag{1}
###条件付き期待値
条件付き期待値とは、__条件確率$P(X|Y=y)$の$X$に関する期待値__で、$\mathbb{E}[X|Y=y]$と表されます。
$\mathbb{E}[X|Y=y]$の定義は、式(2)で表されます。
\mathbb{E}[X|Y=y] = \sum_{x\in \Omega_{X}} xP(X=x|Y=y)
\tag{2}
条件付き期待値$\mathbb{E}[X|Y=y]$を確率変数$Y$で周辺化するとは、$Y$の全ての状態について$\mathbb{E}[X|Y=y]$と確率$P(Y=y)$の積の総和を取り、期待値$\mathbb{E}[X]$を求めることです。
$\mathbb{E}[X|Y=y]$の確率変数$Y$に関する周辺化は式(3)で表されます。
\mathbb{E}[X] = \sum_{y\in \Omega_{Y}} \mathbb{E}[X|Y=y]P(Y=y)
\tag{3}
【折り畳み】式(3)の導出
#価値関数
###状態価値関数
状態価値関数とは、__状態$s$における収益の期待値__で、単に価値関数とも呼ばれることがあります。
状態価値関数$V$は式(4)で表されます。
V(s)=\mathbb{E}[G(t)|s(t)=s]
\tag{4}
###行動価値関数
行動価値関数とは、状態$s$において行動$a$を選択した場合の収益の期待値__で、$Q$値とも呼ばれます__。
行動価値関数$Q$は式(5)で表されます。
Q(s,a)=\mathbb{E}[G(t)|s(t)=s,a(t)=a]
\tag{5}
###状態価値関数と行動価値関数の関係式
状態価値関数$V$と行動価値関数$Q$の関係式を求めます。
行動価値関数$Q$（式(5)）を行動$a$について周辺化すると、下記で表されます。
\begin{align}
&\sum_{a\in A} \mathbb{E}[G(t)|s(t)=s,a(t)=a]P(a(t)=a|s(t)=s)\\
&=\mathbb{E}[G(t)|s(t)=s]
\end{align}
ここで、式(4)、式(5)から、式(6)の関係式が得られます。
\sum_{a\in A} Q(s,a)\pi(a|s)=V(s)
\tag{6}
ただし、$\pi(a|s)$は確率的方策で、式(7)とします。
\pi(a|s)=P(a(t)=a|s(t)=s)
\tag{7}
したがって、__状態価値関数$V$は、行動価値関数$Q$を行動$a$について周辺化したもの__です。
###収益の再帰的表記
ベルマン方程式では、収益の再帰的表記を利用するため、求めておきます。
収益$G$の再帰的表記は式(8)で表されます。
\begin{align}
G(t)&=\sum_{k=0}^{\infty}\gamma^kr(t+k+1)\\
&=r(t+1)+\sum_{k=1}^{\infty}\gamma^kr(t+k+1)\\
&=r(t+1)+\gamma\sum_{k=0}^{\infty}\gamma^kr(t+k+2)\\
&=r(t+1)+\gamma G(t+1)
\end{align}
\tag{8}
#状態価値関数のベルマン方程式
状態価値関数$V$のベルマン方程式を求めます。
これを求めるには、状態価値関数$V$の再帰的表記を目指せば良いです。
これ以降では、$(s(t)=s,a(t)=a,s(t+1)=s^{\prime})=(s,a,s^{\prime})$と表記します。
行動価値関数$V$は式(6)の関係式から、式(9)で表されます。
\begin{align}
V(s)
&=\sum_{a\in A} \mathbb{E}[G(t)|s,a]\pi(a|s)
\end{align}
\tag{9}
また、$\mathbb{E}[G(t)|s,a]$が次の状態$s^{\prime}$について周辺化したものだとみなすと、式(10)で表されます。
\begin{align}
\mathbb{E}[G(t)|s,a]
&=\sum_{s^{\prime}\in S}\mathbb{E}[G(t)|s,a,s^{\prime}]P(s^{\prime}|s,a)
\end{align}
\tag{10}
なお、$P(s^{\prime}|s,a)$は__状態遷移確率__です。
よって、行動価値関数$V$（式(9)）は式(11)に変形できます。
\begin{align}
V(s)
&=\sum_{a\in A} \sum_{s^{\prime}\in S}\mathbb{E}[G(t)|s,a,s^{\prime}]P(s^{\prime}|s,a)\pi(a|s)\\
&=\sum_{a\in A} \pi(a|s)\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\mathbb{E}[G(t)|s,a,s^{\prime}]
\end{align}
\tag{11}
式(11)の形は非常に理解がしやすいです。
状態価値関数$V(s)$は、収益の条件付き期待値を$s^{\prime}$と$a$について周辺化した期待値であることを表しています。
つまり、__状態$s$の価値は、次の行動$a$と次の状態$s^{\prime}$の全てについて総和を取った収益の期待値__ということです。
ここで、式(8)の再帰的表記を使うと、式(11)は式(12)に変形できます。
\begin{align}
V(s)
&=\sum_{a\in A} \pi(a|s)\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\mathbb{E}[r(t+1)+\gamma G(t+1)|s,a,s^{\prime}]\\
&=\sum_{a\in A} \pi(a|s)\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(\mathbb{E}[r(t+1)|s,a,s^{\prime}]+\gamma \mathbb{E}[G(t+1)|s,a,s^{\prime}]\right)
\end{align}
\tag{12}
ここで，$G(t+1)$は状態$s(t+1)=s^{\prime}$から状態$s(t+2)=s^{\prime\prime}$となった時点以降の収益です。
マルコフ性を仮定しているため、$G(t+1)$に関連する状態遷移は状態$s$と行動$a$には依存しません。
このため、式(12)の条件付き期待値$\mathbb{E}[G(t+1)|s,a,s^{\prime}]$は下記となります。
\mathbb{E}[G(t+1)|s,a,s^{\prime}] = \mathbb{E}[G(t+1)|s^{\prime}]=V(s^{\prime})
したがって、式(12)を変形すると、式(13)のベルマン方程式が得られます。
V(s)=
\sum_{a\in A} \pi(a|s)\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(\mathbb{E}[r(t+1)|s,a,s^{\prime}]+\gamma V(s^{\prime})\right)
\tag{13}
他にも様々な表記があります。
例えば、下記のように変形した表記もあります。
\begin{align}
V(s)
&=\sum_{a\in A} \pi(a|s)\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(R(s,a,s^{\prime})+\gamma V(s^{\prime})\right)\\
&=\sum_{a\in A} \sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\pi(a|s)\left(R(s,a,s^{\prime})+\gamma V(s^{\prime})\right)\\
&=\sum_{a\in A} \sum_{s^{\prime}\in S}P(s^{\prime}|s,a)P(a|s)\left(R(s,a,s^{\prime})+\gamma V(s^{\prime})\right)\\
&=\sum_{s^{\prime}\in S}\left(\sum_{a\in A} P(s^{\prime},a|s)\right)\left(R(s,a,s^{\prime})+\gamma V(s^{\prime})\right)\\
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s)\left(R(s,a,s^{\prime})+\gamma V(s^{\prime})\right)\\
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s)R(s,a,s^{\prime})+\gamma \sum_{s^{\prime}\in S}P(s^{\prime}|s)V(s^{\prime})\\
&=R^{\pi}(s)+\gamma \sum_{s^{\prime}\in S}P(s^{\prime}|s)V(s^{\prime})
\end{align}
ただし、変形過程で下記のように置きました。
\begin{align}
R(s,a,s^{\prime})&=\mathbb{E}[r(t+1)|s,a,s^{\prime}]\\
R^{\pi}(s)&=\sum_{s^{\prime}\in S}P(s^{\prime}|s)R(s,a,s^{\prime})
\end{align}
#行動価値関数のベルマン方程式
行動価値関数$Q$のベルマン方程式を求めます。
これを求めるには、状態価値関数$V$のベルマン方程式から変形すれば良いです。
式(13)に式(6)を適用すると、式(14)に変形できます。
\begin{align}
V(s)
&=\sum_{a\in A} \pi(a|s)\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(\mathbb{E}[r(t+1)|s,a,s^{\prime}]+\gamma \sum_{a^{\prime}\in A} Q(s^{\prime},a^{\prime})\pi(a^{\prime}|s^{\prime})\right)
\end{align}
\tag{14}
式(14)と式(6)を恒等的に比較すると、行動価値関数$Q$のベルマン方程式は式(15)で表されます。
\begin{align}
Q(s,a)
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(\mathbb{E}[r(t+1)|s,a,s^{\prime}]+\gamma \sum_{a^{\prime}\in A} Q(s^{\prime},a^{\prime})\pi(a^{\prime}|s^{\prime})\right)
\end{align}
\tag{15}
他にも様々な表記があります。
例えば、下記のように変形した表記もあります。
\begin{align}
Q(s,a)
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(R(s,a,s^{\prime})+\gamma \sum_{a^{\prime}\in A} Q(s^{\prime},a^{\prime})\pi(a^{\prime}|s^{\prime})\right)\\
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)R(s,a,s^{\prime})+\gamma \sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\sum_{a^{\prime}\in A} Q(s^{\prime},a^{\prime})\pi(a^{\prime}|s^{\prime})\\
&=R^{\pi}(s,a)+\gamma \sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\sum_{a^{\prime}\in A} Q(s^{\prime},a^{\prime})\pi(a^{\prime}|s^{\prime})
\end{align}
ただし、変形過程で下記のように置きました。
\begin{align}
R(s,a,s^{\prime})&=\mathbb{E}[r(t+1)|s,a,s^{\prime}]\\
R^{\pi}(s,a)&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)R(s,a,s^{\prime})
\end{align}
また、行動価値関数と状態価値関数の関係式（式(6)）を利用し、行動価値関数$Q$のベルマン方程式（式(15)）は下記のように表すこともあります。
\begin{align}
Q(s,a)
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(\mathbb{E}[r(t+1)|s,a,s^{\prime}]+\gamma V(s^{\prime})\right)\\
&=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a)\left(R(s,a,s^{\prime})+\gamma V(s^{\prime})\right)\\
&=R^{\pi}(s,a)+\gamma \sum_{s^{\prime}\in S}P(s^{\prime}|s,a)V(s^{\prime})
\end{align}
\tag{16}
ベルマン方程式のイメージについては下記の記事が参考になります。
[ベルマン方程式のイメージ][link-3]
[link-3]:https://qiita.com/triwave33/items/5e13e03d4d76b71bc802
一方で、ベルマン方程式の形は、導出を経験しないと覚えづらい面もあるため、ぜひできるようにしておきましょう。
各代表的なアルゴリズムについては、別途記事で解説する予定です。
[強化学習の価値ベースのアルゴリズム（Q学習とSarsa）][link-4]
[link-4]:https://qiita.com/fridericusgauss/items/f87984d4bcd0e143fef6
#おわりに
E資格向けの価値関数とベルマン方程式について解説しました。
なお、上記は、2021年2月時点における内容であることにご注意ください。
[E資格試験に関する私の投稿記事リスト][link-1]