はじめに
強化学習のテキスト
「これからの強化学習」に出てくるベルマン方程式を導出する。自身のための覚書である。
収益
時間ステップ$t$における収益$G_t$として、次式で定義される割引報酬和を考える。
\begin{equation}
G_t=\sum_{\tau=0}^{\infty}\gamma^{\tau}R_{t+1+\tau}
\end{equation}
ここで、$\gamma$は割引率と呼ばれる量であり、$0\leqq\gamma\leqq 1$を満たす。$R_t$は時間ステップ$t$における報酬を表す。上式を展開すると
\begin{equation}
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots
\end{equation}
となる。つまり収益$G_t$とは、次の時間ステップ$t+1$から未来に向かって得られる報酬の和である。
状態価値関数
状態価値関数$V(s)$は、時間ステップ$t$における状態を表す確率変数$S_t$の観測値が$s$である条件の下で計算される収益$G_t$の期待値である。
\begin{equation}
V(s)={\bf E}\left[G_t|S_t=s \right]
\end{equation}
行動価値関数
行動価値関数$Q(s,a)$は、確率変数$S_t$の観測値が$s$、行動を表す確率変数$A_t$の観測値がaである条件の下で計算される収益$G_t$の期待値である。
\begin{equation}
Q(s,a)={\bf E}\left[G_t|S_t=s,A_t=a \right]
\end{equation}
ところで、$S_t=s$のとき収益$G_t$が実現する確率$P(G_t|S_t=s)$と$S_t=s, A_t=a$のとき収益$G_t$が実現する確率$P(G_t|S_t=s,A_t=a)$の間にはベイズの定理から次式が成り立つ。
\begin{equation}
P(G_t|S_t=s)=\sum_a P(A_t=a|S_t=s)P(G_t|S_t=s,A_t=a)
\end{equation}
ここで、$P(A_t=a|S_t=s)$は、状態$s$のとき行動$a$が選択される確率であり、特に$\pi(a|s)$と表記される。これはエージェントの方策を決める確率である。上の関係式から、状態価値関数と行動価値関数の間には次式が成り立つ。
\begin{equation}
V(s)=\sum_{a}\pi(a|s)Q(s,a)
\end{equation}
ベルマン方程式
状態価値関数$V(s)$に式(2)を代入して
\begin{eqnarray}
V(s)&=&{\bf E}\left[G_t|S_t=s \right] \\
&=&{\bf E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots|S_t=s \right] \\
&=&{\bf E}\left[R_{t+1}|S_t=s \right] +\gamma{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s \right]
\end{eqnarray}
を得る。右辺第1項は
\begin{eqnarray}
{\bf E}\left[R_{t+1}|S_t=s \right] &=&\sum_{s^{\prime},a}P(S_{t+1}=s^{\prime},A_t=a|S_t=s)\;R_{t+1} \\
&=&\sum_{s^{\prime},a}P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)P(A_t=a|S_t=s)\;R_{t+1} \\
&=&\sum_{s^{\prime},a}P(s^{\prime}|s,a)\pi(a|s)\;r(s,a,s^{\prime})
\end{eqnarray}
となる。ここで、報酬関数$r(S_t,A_t,S_{t+1})$を導入した。これは現在の状態と行動、および次の状態から報酬が決定されることを表している。また、確率$P$は、確率変数ではなくその実現値に依存するものである。従って、確率変数を省略することができる。
次に、式(9)の第2項を考える。
\begin{equation}
{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s \right]
=
{\bf E}\left[R_{t+2}|S_t=s \right]+
\gamma{\bf E}\left[R_{t+3}|S_t=s \right]+\cdots
\end{equation}
これの右辺第1項は
\begin{eqnarray}
{\bf E}\left[R_{t+2}|S_t=s \right]
&=&
\sum_{s^{\prime\prime},s^{\prime},a^{\prime},a} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime},S_{t+1}=s^{\prime},A_t=a|S_t=s)\;R_{t+2} \\
&=&
\sum_{s^{\prime\prime},s^{\prime},a^{\prime},a} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})P(S_{t+1}=s^{\prime},A_t=a|S_t=s)\;R_{t+2} \\
&=&\sum_{s^{\prime},a} P(S_{t+1}=s^{\prime},A_t=a|S_t=s)\sum_{s^{\prime\prime},a^{\prime}}P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})\;R_{t+2} \\
&=&\sum_{s^{\prime},a} P(s^{\prime},a|s)\;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime} \right] \\
&=&\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime} \right]
\end{eqnarray}
となる。式(16)からの(17) への変形では、確率変数を省略し、式(10)を用いた。式(13)の他の項についても同様に計算することにより次式を得る。
\begin{eqnarray}
{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s \right]&=&\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\;{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_{t+1}=s^{\prime} \right] \\
&=&
\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\;V(s^{\prime})
\end{eqnarray}
式(19)から(20)への変形では$V(s)$の定義を用いた。最後に式(12)と(20)から次式を得る。
\begin{equation}
V(s)=\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\left[r(s,a,s^{\prime})+\gamma V(s^{\prime})\right]
\end{equation}
これを状態価値関数に関するベルマンの方程式と呼ぶ。
次に行動価値関数についてのベルマン方程式を求める。
\begin{eqnarray}
Q(s,a)&=&{\bf E}\left[G_t|S_t=s,A_t=a \right] \\
&=&{\bf E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots|S_t=s,A_t=a \right] \\
&=&{\bf E}\left[R_{t+1}|S_t=s,A_t=a \right] +\gamma{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s,A_t=a \right]
\end{eqnarray}
右辺第1項は
\begin{eqnarray}
{\bf E}\left[R_{t+1}|S_t=s,A_t=a \right]
&=&\sum_{s^{\prime}}P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+1} \\
&=&\sum_{s^{\prime}}P(s^{\prime}|s,a)\;r(s,a,s^{\prime})
\end{eqnarray}
右辺第2項は
\begin{equation}
{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s,A_t=a \right]
=
{\bf E}\left[R_{t+2}|S_t=s,A_t=a \right]+
\gamma{\bf E}\left[R_{t+3}|S_t=s,A_t=a \right]+\cdots
\end{equation}
これの右辺第1項は
\begin{eqnarray}
&&{\bf E}\left[R_{t+2}|S_t=s,A_t=a \right] \\
&=&
\sum_{s^{\prime\prime},s^{\prime},a^{\prime}} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime},S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+2} \\
&=&
\sum_{s^{\prime\prime},s^{\prime},a^{\prime}} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+2} \\
&=&\sum_{s^{\prime}}
\sum_{s^{\prime\prime},s^{\prime},a^{\prime}}
P(S_{t+2}=s^{\prime\prime}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime})
P(A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime}) \times\\
&&
\hspace{200pt}P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+2} \\
&=&\sum_{s^{\prime}}
P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)
\sum_{a^{\prime}}
P(A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})\times \\
&&
\hspace{200pt}\sum_{s^{\prime\prime}}
P(S_{t+2}=s^{\prime\prime}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime})\;R_{t+2} \\
&=&\sum_{s^{\prime}}
P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)
\sum_{a^{\prime}}
P(A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})
\;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime} \right] \\
&=&\sum_{s^{\prime}}
P(s^{\prime}|s,a)
\sum_{a^{\prime}}
\pi(a^{\prime}|s^{\prime})
\;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime} \right]
\end{eqnarray}
他の項についても同様な計算を行えば次式を得る。
\begin{eqnarray}
&&{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s,A_t=a \right]\\
&=&
\sum_{s^{\prime}}
P(s^{\prime}|s,a)\sum_{a^{\prime}}
\pi(a^{\prime}|s^{\prime})
\;{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime} \right] \\
&=&
\sum_{s^{\prime}}
P(s^{\prime}|s,a)\sum_{a^{\prime}}
\pi(a^{\prime}|s^{\prime})
\;Q(s^{\prime},a^{\prime}) \\
\end{eqnarray}
式(26)と(37)から最終的に次式を得る。
\begin{equation}
Q(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q(s^{\prime},a^{\prime})\right]
\end{equation}
式(6)を使えば
\begin{equation}
Q(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma\;V(s^{\prime})\right]
\end{equation}
とも書ける。これらが、行動価値関数についてのベルマン方程式である。
