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

はじめに

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

不動点方程式

　状態価値関数$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)$に対し、厳密に成り立つことが知られており、ベルマン最適方程式と呼ばれる。これらについては不動点方程式の形に変形することはできないが、やはり、唯一解が存在することが知られている。

参考文献

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