輪読会「ゼロから作るDeep Learning④ 強化学習編」第３回

はじめに

てくますプロジェクトでは、てくますゼミと呼ばれる学習会を開催しています。

少人数であーだこーだ議論しながら、考える楽しさを分かち合うことを大切にしています。

現在は「ゼロから作るDeep Learning④ 強化学習編」という本を読み進めています。

リンク

今回は本書第３回の輪読会ということで、3章を読み進めました！

本記事では、今回の勉強会で学んだことをざっくりと紹介していきます。

学習内容

状態価値関数とベルマン方程式

前回の章では環境が決定的であり、エージェントの行動も決定的でした。

この章では確率的な振る舞いをするMDPにも対応できるように、ベルマン方程式を導入します。

さて、前回の章で定義した収益は、次のように式変形できます。

\(
\begin{eqnarray}
G_t &=& R_t + γR_{t+1} + γ^2R_{t+2} +… \\
&=& R_t + γ(R_{t+1} + γR_{t+2} +…) \\
&=& R_t + γG_{t+1}
\end{eqnarray}
\)

これを用いて、状態価値関数を式変形します。

\(
\begin{eqnarray}
v_π(s) &=& E_π[G_t|S_t=s] \\
&=& E_π[R_t +γG_{t+1}|S_t=s] \\
&=& E_π[R_t|S_t=s] + γE_π[G_{t+1}|S_t=s] \\
&=& \displaystyle \sum_{a, s’} π(a|s)p(s’|s, a)r(s, a, s’) + γ\displaystyle \sum_{a, s’} π(a|s)p(s’|s, a)v_π(s’) \\
&=& \displaystyle \sum_{a, s’} π(a|s)p(s’|s, a)\{r(s, a, s’) + γv_π(s’)\}
\end{eqnarray}
\)

この式をベルマン方程式と呼びます。

ベルマン方程式は、状態 \(s\) の状態価値関数と、その次に取りうる状態 \(s’\) の状態価値関数との関係性を表した式です。

2マスのグリッドワールドを例として考えましょう。

L1→L2の移動で報酬+1、壁にぶつかると報酬-1、それ以外の報酬は0
エージェントは左右ランダムに動く方策を取るものとします。
また、割引率は \(γ=0.9\) とします。

この例において、ベルマン方程式はどのようになるでしょうか？

今回の問題のように行動が決定論的な場合、ベルマン方程式は次のように簡単にできます。

\(
\begin{eqnarray}
v_π(L_1) &=& \displaystyle \sum_{a, s’} π(a|s)p(s’|s, a)\{r(s, a, s’) + γv_π(s’)\} \\
&=& \displaystyle \sum_{a} π(a|s)\{r(s, a, s’) + γv_π(s’)\}
\end{eqnarray}
\)

これを用いると、

\(v_π(L_1) = 0.5\{-1 + 0.9v_π(L_1)\} + 0.5\{1 + 0.9v_π(L_2)\}\)

\(v_π(L_2) = 0.5\{0 + 0.9v_π(L_1)\} + 0.5\{-1 + 0.9v_π(L_2)\}\)

これら２つの式を連立方程式として解くことで、
\(v_π(L_1)=-2.25, v_π(L_2)=-2.75\) が得られます。

ベルマン方程式を用いて、状態価値関数を求めることができました。

行動価値関数とベルマン方程式

状態価値関数の条件は、状態が \(s\) であることと方策 \(π\) でした。この条件に、行動が \(a\) であることも追加したものが、行動価値関数（Q関数）です。

\(q_π(s, a) = E_π[G_t|S_t=s, A_t=a]\)

状態価値関数と行動価値関数には次のような関係があります。

\(v_π(s) =\displaystyle \sum_{a}π(a|s)q_π(s, a)\)

行動価値関数も状態価値関数と同じようにベルマン方程式を作りましょう。

\(
\begin{eqnarray}
q_π(s, a) &=& E_π[G_t|S_t=s, A_t=a] \\
&=& E_π[R_t +γG_{t+1}|S_t=s, A_t=a] \\
&=& E_π[R_t|S_t=s, A_t=a] + γE_π[G_{t+1}|S_t=s, A_t=a] \\
&=& \displaystyle \sum_{s’} p(s’|s, a)r(s, a, s’) + γ\displaystyle \sum_{s’} p(s’|s, a)v_π(s’) \\
&=& \displaystyle \sum_{s’} p(s’|s, a)\{r(s, a, s’) + γv_π(s’)\} \\
&=& \displaystyle \sum_{s’} p(s’|s, a)\left\{r(s, a, s’) + γ\displaystyle \sum_{a’}π(a’|s’)q_π(s’, a’)\right\} \\
\end{eqnarray}
\)

ベルマン最適方程式

最適方策 \(π_\ast\) の場合に、ベルマン方程式はよりシンプルな形で書くことができます。これをベルマン最適方程式と呼びます。

状態価値関数におけるベルマン最適方程式

\(
\begin{eqnarray}
v_\ast(s) &=& \displaystyle \sum_{a, s’} π_\ast(a|s)p(s’|s, a)\{r(s, a, s’) + γv_\ast(s’)\} \\
&=& \displaystyle \underset{a}{max}\sum_{s’} p(s’|s, a)\{r(s, a, s’) + γv_\ast(s’)\} \\
\end{eqnarray}
\)

行動価値関数におけるベルマン最適方程式

\(
\begin{eqnarray}
q_\ast(s, a) &=& \displaystyle \sum_{s’} p(s’|s, a)\left\{r(s, a, s’) + γ\displaystyle \sum_{a’}π_\ast(a’|s’)q_\ast(s’, a’)\right\} \\
&=& \displaystyle \sum_{s’} p(s’|s, a)\left\{r(s, a, s’) + γ\displaystyle \underset{a’}{max}q_\ast(s’, a’)\right\}
\end{eqnarray}
\)

再び、2マスのグリッドワールドを考えましょう。

\(v_\ast(L_1)=max(-1+0.9v_\ast(L_1), 1+0.9v_\ast(L_2))\)
\(v_\ast(L_2)=max(0.9v_\ast(L_1), -1+0.9v_\ast(L_2))\)

この連立方程式を解くと、\(v_\ast(L_1)=5.26, v_\ast(L_2)=4.73\) が得られます。

最適方策を得る

最適行動価値関数や最適状態価値関数を用いて、最適方策 \(μ_\ast(s)\) は次の式で得られます。

\(
\begin{eqnarray}
μ_\ast(s) &=& \underset{a}{argmax}q_\ast(s, a) \\
&=& \underset{a}{argmax}\sum_{s’} p(s’|s, a)\{r(s, a, s’) + γv_\ast(s’)\}
\end{eqnarray}
\)
\(\underset{a}{argmax}\) は最大となる行動 \(a\) を返します。

さて、2マスのグリッドワールドを考えましょう。

状態L1における最適な行動を考えます。

左に進むとき、 \(-1 + 0.9v_\ast(L_1)=3.734\) となり、
右に進むとき、 \(1 + 0.9v_\ast(L_2)=5.257\) となります。

ゆえに、状態L1にいるときの最適な行動は右に進むことだと分かります。

同様にして、状態L2にいるときの最適な行動は左に進むことだと分かります。

以上より、最適方策を得ることができました。