強化学習 〜ベルマン最適方程式〜

はじめに

　先のページでベルマン方程式の導出を行った。この議論に追記を行い、ベルマン最適方程式を示す。

不動点方程式

　状態価値関数$V(s)$に対し、次のベルマン方程式が成り立つことを見た。 $$\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}$$ ここで、右辺第1項,第2項に対し $$\begin{eqnarray} \eta^{V}(s)&\equiv&\sum_{s^{\prime},a}P(s^{\prime}|s,a)\pi(a|s)r(s,a,s^{\prime}) \\ M^{V}(s,s^{\prime})&\equiv&\sum_{a}P(s^{\prime}|s,a)\pi(a|s) \end{eqnarray}$$ を定義すると $$\begin{equation} V(s)=\eta^{V}(s)+\gamma \sum_{s^{\prime}}M^{V}(s,s^{\prime})V(s^{\prime}) \end{equation}$$ を得る。いま、状態が$D$個に離散化されている場合を考えると、$V(s)$は$D$次元ベクトル$\vec{V}$の第$s$番目の成分と見ることができる。$M^{V}(s,s^{\prime})$は行列$M^{V}$の$(s,s^{\prime})$成分である。従って、次式を得る。 $$\begin{equation} \vec{V}=\vec{\eta}^{\;V}+\gamma M^{V}\vec{V} \end{equation}$$ この式の右辺を眺めると、平行移動と線形変換の組み合わせ、すなわち、アフィン変換であることが分かる。このアフィン変換をベルマン作用素と呼ぶ。ベルマン作用素を$T^{V}$で表すと $$\begin{equation} \vec{V}=T^{V}\vec{V} \end{equation}$$ となる。これは、変換後の自身が自身に等しくなることから不動点方程式であり、$0<\gamma<1$のとき唯一解$\vec{V}$を持つことが知られている。

　次に、行動価値関数$Q(s,a)$について考える。$Q(s,a)$のベルマン方程式は次式であった。 $$\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}$$ ここで $$\begin{eqnarray} \eta^{Q}(s,a)&\equiv&\sum_{s^{\prime}}P(s^{\prime}|s,a)r(s,a,s^{\prime}) \\ M^{Q}(s,a,s^{\prime},a^{\prime})&\equiv&P(s^{\prime}|s,a)\pi(a^{\prime}|s^{\prime}) \end{eqnarray}$$ を導入すると $$\begin{equation} Q(s,a)=\eta^{Q}(s,a)+\gamma\sum_{s^{\prime},a^{\prime}}M^{Q}(s,a,s^{\prime},a^{\prime})Q(s^{\prime},a^{\prime}) \end{equation}$$ を得る。今度は状態だけでなく行動も$D^{\prime}$個に離散化されている場合を考える。このとき$Q(s,a)$は$D\times D^{\prime}$次元のベクトルになる。$(s,a)$を1つの添え字で表せば、状態価値関数のときと同じ議論を繰り返すことができ、次式を得る。 $$\begin{equation} \vec{Q}=\vec{\eta}^{\;Q}+\gamma M^{Q}\vec{Q} \end{equation}$$ 右辺はアフィン変換であり、ベルマン作用素$T^{Q}$を使うと $$\begin{equation} \vec{Q}=T^{Q}\vec{Q} \end{equation}$$ と書くことができる。これも不動点方程式であり、$0<\gamma<1$のとき唯一解$\vec{Q}$を持つことが知られている。

ベルマン最適方程式

　$V(s)$と$Q(s,a)$のベルマン方程式を再度示す。 $$\begin{eqnarray} 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]\\ 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{eqnarray}$$ これらは、方策$\pi$を用いて、ある状態に対する行動を選択している。いま、方策$\pi$を介さずに、最適な行動を直接選択することを考える。上式の$\sum_{a}\pi(a|s)$を形式的に$\max_a$で置き換えると次式を得る。 $$\begin{eqnarray} V^{*}(s)&=&\max_{a}\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma V^{*}(s^{\prime})\right]\\ Q^{*}(s,a)&=&\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime})\right] \end{eqnarray}$$ これらは、最適状態価値関数$V^{*}(s)$と最適行動価値関数$Q^{*}(s,a)$に対し、厳密に成り立つことが知られており、ベルマン最適方程式と呼ばれる。これらについては不動点方程式の形に変形することはできないが、やはり、唯一解が存在することが知られている。

参考文献

• 速習強化学習
• これからの強化学習

強化学習 〜方策勾配定理の導出〜

はじめに

　前回に引き続き、強化学習のテキスト「これからの強化学習」に出てくる方策勾配定理を導出する。自身のための覚書である。

最大化すべき目的関数

　状態価値関数$V(s)$は次式で定義された。 $$\begin{equation} V(s)={\bf E}\left[G_t|S_t=s\right] \end{equation}$$ いま、 方策を表す確率$\pi(a|s)$を、パラメータ$\theta$に依存する微分可能な関数でモデル化し、 時間ステップ$t=0$から始める状態価値関数を考える。 $$\begin{eqnarray} V(s_0)&=&{\bf E}\left[G_0|S_0=s_0\right] \\ &=&{\bf E}\left[\sum_{t=1}^{\infty}\gamma^{t-1}R_t|S_0=s_0\right] \\ &\equiv& J(\theta;s_0) \end{eqnarray}$$ これを$\theta$に関して最大化する。

方策勾配定理の導出

　先に見たように、状態価値関数$V(s)$と行動価値関数$Q(s,a)$の間には次式が成り立つ。 $$\begin{equation} V(s)=\sum_a \pi(a|s)Q(s,a) \end{equation}$$ $\pi(a|s)$が$\theta$に依存するとき、$V(s)$と$Q(s,a)$も$\theta$に依存する。従って次式が成り立つ。 $$\begin{equation} \frac{\partial V(s)}{\partial \theta}=\sum_a \left[\frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)+\pi(a|s)\frac{\partial Q(s,a)}{\partial \theta}\right] \label{eq0} \end{equation}$$ ここで、先に示した$Q(s,a)$についてのベルマン方程式 $$\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}$$ の両辺を$\theta$で微分する。上式の右辺第1項は$\theta$に依存しないことに注意すると $$\begin{equation} \frac{\partial Q(s,a)}{\partial \theta}=\gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a)\;\frac{\partial V(s^{\prime})}{\partial \theta} \end{equation}$$ を得る。これを、式($\ref{eq0}$)に代入する。 $$\begin{eqnarray} \frac{\partial V(s)}{\partial \theta} &=& \sum_a \left\{\frac{\partial \pi(a|s)}{\partial \theta}Q(s,a) + \pi(a|s) \left[ \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a)\;\frac{\partial V(s^{\prime})}{\partial \theta} \right] \right\}\\ &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a)\;\frac{\partial V(s^{\prime})}{\partial \theta} \end{eqnarray}$$ ここで、$f(s)\equiv\sum_a \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)$とした。再帰的に代入を繰り返す。 $$\begin{eqnarray} \frac{\partial V(s)}{\partial \theta} &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) \left[ f(s^{\prime}) + \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \gamma\;\sum_{s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime},a^{\prime}) \frac{\partial V(s^{\prime\prime})}{\partial \theta} \right]\\ &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) f(s^{\prime}) \\ &&+ \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \gamma\;\sum_{s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime},a^{\prime}) \frac{\partial V(s^{\prime\prime})}{\partial \theta} \\ &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) f(s^{\prime}) \\ &&+ \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \gamma\;\sum_{s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime},a^{\prime}) f(s^{\prime\prime})+\cdots \end{eqnarray}$$ ここで、 $$\begin{equation} \sum_a \pi(a|s)P(s^{\prime}|s,a)=\sum_a P(s^{\prime}|s,a)\pi(a|s)=P(s^{\prime}|s) \end{equation}$$ が成り立つから次式を得る。 $$\begin{equation} \frac{\partial V(s)}{\partial \theta} =f(s)+\gamma \sum_{s^{\prime}} P(s^{\prime}|s)f(s^{\prime}) +\gamma^2 \sum_{s^{\prime},s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime}) P(s^{\prime}|s)f(s^{\prime\prime})+\cdots \end{equation}$$ 右辺第2項の$P(s^{\prime}|s)$は1ステップで状態$s$から$s^{\prime}$へ遷移する確率、第3項の$\sum_{s^{\prime}}P(s^{\prime\prime}|s^{\prime}) P(s^{\prime}|s)$は2ステップで状態$s$から$s^{\prime\prime}$へ遷移する確率を表す。これを一般化し、$k$ステップで状態$s$から$x$へ遷移する確率を$P(s\rightarrow x,k)$と書くことにすると $$\begin{eqnarray} \frac{\partial V(s)}{\partial \theta} &=&f(s)+\gamma \sum_{x} P(s\rightarrow x,1)f(x) +\gamma^2 \sum_{x} P(s\rightarrow x,2)f(x)+\cdots \\ &=& \sum_{k=0}^{\infty}\gamma^{k}\sum_x P(s\rightarrow x,k)f(x) \end{eqnarray}$$ を得る。ただし、$k=0$のとき状態は変化しないので次式が成り立つことを用いた。 $$\begin{equation} \sum_x P(s\rightarrow x,0)f(x)=f(s) \end{equation}$$ ところで、$J(\theta;s_0)$は$V(s_0)$であったから $$\begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& \frac{\partial V(s_0)}{\partial \theta} \\ &=& \sum_{k=0}^{\infty}\gamma^{k}\sum_x P(s_0\rightarrow x,k)f(x) \end{eqnarray}$$ が成り立つ。$f(x)$を元の式に戻して $$\begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& \sum_s \left[\sum_{k=0}^{\infty}\gamma^{k}P(s_0\rightarrow s,k)\right]\sum_a \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)\\ &=& \sum_s d(s)\sum_a \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a) \end{eqnarray}$$ を得る。ここで、$d(s)\equiv \sum_{k=0}^{\infty}\gamma^{k}P(s_0\rightarrow s,k)$と置いた。上式をさらに変形すると $$\begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& \sum_{s,a} d(s)\pi(a|s)\frac{1}{\pi(a|s)} \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a) \label{eq1} \end{eqnarray}$$ を得る。ここで、右辺の$d(s)\pi(a|s)$は以下のように変形できる。 $$\begin{eqnarray} d(s)\pi(a|s) &=& \sum_{k=0}^{\infty}\gamma^{k}P(s_0\rightarrow s,k)\pi(a|s)\\ &=& \sum_{k=0}^{\infty}\gamma^{k}P(S_k=s|S_0=s_0)\pi(a|s)\\ &=& \sum_{k=0}^{\infty}\gamma^{k}P(S_k=s|S_0=s_0)\;P(A_k=a|S_k=s)\\ &=& \sum_{k=0}^{\infty}\gamma^{k}P(S_k=s, A_k=a|S_0=s_0) \end{eqnarray}$$ 上式は、時間ステップ$t=0$において$s_0$であった状態が、最終的に状態$s$・行動$a$に遷移する全てのステップを足し合わせた確率を表している。割引率$\gamma$により、ステップ数が多いほど確率が低くなることが考慮されている。以上の考察から、式($\ref{eq1}$)は期待値の記号を用いて表すことができる。 $$\begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& {\bf E}\left[\frac{1}{\pi(a|s)} \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)\right]\\ &=& {\bf E}\left[\frac{\partial \ln{\pi(a|s)}}{\partial \theta}Q(s,a)\right] \end{eqnarray}$$ 上式を方策勾配定理と呼ぶ。

参考文献

• https://www.slideshare.net/nishio/3-71708970
• これからの強化学習

強化学習 〜ベルマン方程式の導出〜

はじめに

　強化学習のテキスト「これからの強化学習」に出てくるベルマン方程式を導出する。自身のための覚書である。

収益

　時間ステップ$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}$$ とも書ける。これらが、行動価値関数についてのベルマン方程式である。