今回は、式$(1)$で表されるベルマン方程式の導出をする． $$ \begin{align} v_{\pi}(s) = \sum _{a} \pi(a|s) \sum _{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma v_{\pi}(s’) \right\} \end{align} $$

無限に続く式

　ベルマン方程式がどのようなものかを想像しやすいように，例え話をする． 本題ではないので読み飛ばしても問題はない． 強化学習において，終わりがないエンドレスな環境(連続タスク)を考えることがある． こういった無限に続く環境は，ある行動の価値を求めるためには，その行動をとってからの無限の手数の報酬を考慮する必要がある．計算機には無限を扱うことができず，厄介である．

しかし，数学には無限を解決する方法がある． 例えば式$(2)$だ．この式は無限に続く． $$ \begin{equation} x = \sqrt{1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + \sqrt{ 1 + \cdots}}}}}}} \end{equation} $$ このままでは計算が困難であるが，$x$の中には$x$自身が含まれているため，式$(3)$から式$(7)$のように変形し，$x$の値が求められる．

$$ \begin{align} x &= \sqrt{1 + x} \\ x^2 &= 1 + x \\ x^2 - x - 1 &= 0 \\ \therefore x &= \frac{1 \pm \sqrt{5}}{2} \\ \end{align} $$

　このように，無限に続く式の中に自分自身が入っていれば，工夫して計算が可能になりことがある． これの似たようなことを複数の変数で行ったものがベルマン方程式のイメージである¹．強化学習では，実際に式$(7)$に示すような無限につづく式が登場する． $$ \begin{align} G_t &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \cdots \end{align} $$

　無限限定の話をしたが，有限のエピソードタスクであったとしても，それが長いものであれば，計算量が膨大になってしまう．その場合もベルマン方程式は，現在の状態と次以降の状態の関係を示してくれる頼れる存在なのだ．

ベルマン方程式とは

　方程式，という名前から分かる通り，未知数を含む式である．未知数は，$v_\pi(s)$である．様々な$s$で$v_\pi(s)$についての方程式が立ち，連立方程式として解くことにより各値が求められる．

なお，この式を使って様々な問題を解くとき，組合せ爆発により，連立方程式の数が莫大になり，素直に解くことは厳しいことが多い．

しかし，この式をベースにすることで，動的計画法，モンテカルロ法，TD法，SARSA法，Q学習法などの強化学習のアルゴリズムの説明や導出が可能になる．

導出

　前回のマルコフ決定過程で出てきた状態価値関数と収益の式を思い出してもらいたい．式$(8)$$(9)$に示す．

$$ \begin{align} v_\pi(s) &= \mathbb{E}_\pi[G_t|S_t=s] \\ G_t &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \end{align} $$ $G_t$は無限に続くため，式$(10)$に変形できる． $$ \begin{align} G_t &= R_t + \gamma G_{t+1} \end{align} $$ これを状態価値関数の式に代入すると，式$(11)$になる． $$ \begin{align} v_\pi(s) &= \mathbb{E}_\pi[R_t+\gamma G_{t+1} |S_t=s] \\ \end{align} $$

期待値の線形性により，式$(12)$が成り立つ．

$$ \begin{align} \mathbb{E}_\pi[R_t+\gamma G_{t+1} |S_t=s] = \mathbb{E}_\pi[R_t |S_t=s] + \gamma \mathbb{E}_\pi[G_{t+1} |S_t=s] \\ \end{align} $$

式$(12)$の右辺の第一項目の$\mathbb{E}_\pi[R_t |S_t=s]$は，期待値の定義から次のように書ける．

$$ \mathbb{E}_\pi[R_t |S_t=s] = \sum _{a} \sum _{s’}\pi(a|s) p(s’|s,a)r(s,a,s’) $$

各関数について一度確認しよう．

• $\pi(a|s)$は，状態$s$で行動$a$をとる確率．
• $p(s’|s,a)$は，状態$s$で行動$a$をとったときに，状態$s’$に遷移する確率．
• $r(s,a,s’)$は，状態$s$で行動$a$をとったときに，状態$s’$に遷移したときに得られる報酬．

つまり，$\pi(a|s) p(s’|s,a)$は，状態$s$から行動$a$をしたときに，状態$s’$に遷移する確率である．そのときの報酬が$r(s,a,s’)$であり，確率に報酬を掛け算されたものの和が$\mathbb{E}_\pi[R_t |S_t=s]$である．

第二項目の$\mathbb{E}_\pi[G_{t+1} |S_t=s]$についても同様に考えると，式$(13)$$(14)$となる．

$$ \begin{align} \mathbb{E}_\pi[G_{t+1} |S_t=s] &= \sum _{a} \sum _{s’}\pi(a|s) p(s’|s,a) \mathbb{E}_\pi[G_{t+1} |S_{t+1}=s’] \\ &= \sum _{a} \sum _{s’}\pi(a|s) p(s’|s,a) v_\pi(s’) \end{align} $$

第二項目は，収益$G_{t+1}$の期待値であるため，状態$s$から行動$a$をしたときに状態$s’$に遷移する確率$\pi(a|s) p(s’|s,a)$に，その場合の収益$\mathbb{E}_\pi[G_{t+1} |S_{t+1}=s’]$を掛け算している．$\mathbb{E}_\pi[G_{t+1} |S_{t+1}=s’]$は状態価値関数$v_\pi(s’)$そのものであるため，置き換えることができる．

さて，これらをまとめると，次のようになる．

$$ \begin{align} v_\pi(s) &= \sum _{a} \sum _{s’}\pi(a|s) p(s’|s,a)r(s,a,s’) + \gamma \sum _{a} \sum _{s’}\pi(a|s) p(s’|s,a) v_\pi(s’) \\ &= \sum _{a} \sum _{s’}\pi(a|s) p(s’|s,a) \left\{ r(s,a,s’) + \gamma v_\pi(s’) \right\} \end{align} $$

以上でベルマン方程式の導出は終わりである．

行動価値関数を用いたベルマン方程式

　状態価値関数でベルマン方程式を示したが，今度は行動価値関数について導出する． $$ \begin{align} q_\pi(s,a) &= \mathbb{E}_\pi[G_t|S_t=s,A_t=a] \\ &= \mathbb{E}_\pi[R_{t} + \gamma G_{t+1} |S_t=s,A_t=a] \\ &= \mathbb{E}_\pi[R_{t} |S_t=s,A_t=a] + \gamma \mathbb{E}_\pi[G_{t+1} |S_t=s,A_t=a] \\ &= \sum _{s’} p(s’|s,a) r(s,a,s’) + \gamma \sum _{s’} p(s’|s,a) \mathbb{E}_\pi[G_{t+1} |S_{t+1}=s’] \\ &= \sum _{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma \mathbb{E}_\pi[G_{t+1} |S_{t+1}=s’] \right\} \\ &= \sum _{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma v_\pi(s’) \right\} \\ \end{align} $$ この式変形は，状態価値関数の式変形とよく似ている．$1$行ずつ説明すると，

• $2$行目，$G_t$を$R_{t+1}+\gamma G_{t+1}$に置き換えた．
• $3$行目，期待値の線形性より$2$項に分ける．
• $4$行目，期待値の定義に従いシグマ記号で表す．
  • 状態価値関数の場合と異なり，シグマに$a$が含まれないことに注目．
• $5$行目，括弧でくくる．
• $6$行目，状態価値関数$v$を使って表す．

さらに，式$(23)$であることを使うと，式$(24)(25)$と変形でき，状態価値関数$v$が消される． $$ \begin{align} v_\pi(s) = \sum_a \pi(a|s) q_\pi(s,a) \end{align} $$ $$ \begin{align} q_\pi(s,a) &= \sum_{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma v_\pi(s’) \right\} \\ &= \sum_{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma \sum_{a’} \pi(a’|s’) q_\pi(s’,a’) \right\} \\ \end{align} $$

状態価値関数における最適方程式

　式$(26)$のように，ベルマン方程式の方策$\pi$を最適方策$\pi^*$に置き換える．

$$ \begin{align} v_*(s) = \sum _{a} \sum _{s’}\pi_* (a|s) p(s’|s,a) \left\{ r(s,a,s’) + \gamma v_*(s’) \right\} \end{align} $$

ここで，$\pi_*$は最適方策であるため，状態$s$における行動$a$の確率$\pi_*(a|s)$は，1つの行動$a$だけが1で他は0であるはずである．よって式$(27)$のように書き換えることができる． $$ \begin{align} v_*(s) = \max _{a} \sum _{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma v_*(s’) \right\} \end{align} $$ これは，状態価値観数における最適方程式である．

行動価値関数における最適方程式

　状態価値関数の最適方程式と同様に，方策$\pi$における行動価値のベルマン方程式である式$(28)$を，最適方策$\pi^*$に置き換えると，式$(29)$となる． $$ \begin{align} q_\pi(s,a) &= \sum_{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma \sum_{a’} \pi(a’|s’) q_\pi(s’,a’) \right\} \\ \end{align} $$ $$ \begin{align} q_* (s,a) &= \sum _{s’} p(s’|s,a) \left\{ r(s,a,s’) + \gamma \max _{a’} q_* (s’,a’) \right\} \\ \end{align} $$

最適方策

　最後に，最適方策を返す関数$\mu_*$を定義する．$\mu_*(s)$は，状態$s$における，最適な行動を返すような関数である．これは，状態$s$における行動価値関数$q_*(s,a)$の最大値を取るような行動$a$を返すように定義すればよい．よって， $$ \begin{align} \mu_*(s) = \text{argmax} _{a} q_* (s,a) \end{align} $$ と表せる．ただし，$\text{argmax} _{x} f(x)$は，$f(x)$が最大となる$x$を返す．