3.1.2：状態価値関数のベルマン方程式の導出【ゼロつく4のノート】

はじめに

　『ゼロから作るDeep Learning 4 ――強化学習編』の独学時のまとめノートです。初学者の補助となるようにゼロつくシリーズの4巻の内容に解説を加えていきます。本と一緒に読んでください。

　この記事は、3.1.2節の内容です。状態価値関数についてのベルマン方程式を導出します。

【前節の内容】

www.anarchive-beta.com

【他の記事一覧】

www.anarchive-beta.com

【この記事の内容】

3.1.2 状態価値関数のベルマン方程式の導出

　状態価値関数についてのベルマン方程式を導出します。

・期待値の性質

　まずは、(離散型の)期待値$\mathbb{E}[x] = \sum_x x p(x)$の性質を確認します。

　ベルマン方程式の導出に、次の期待値の性質を利用します。

$$ \begin{align*} \mathbb{E}[a x] &= a \mathbb{E}[x] \tag{1}\\ \mathbb{E}[x + y] &= \mathbb{E}[x] + \mathbb{E}[y] \tag{2}\\ \sum_y \mathbb{E}[x | y] p(y) &= \mathbb{E}[x] \tag{3}\\ \sum_y \mathbb{E}[x | y] p(y | z) &= \mathbb{E}[x | z] \tag{4} \end{align*} $$

　それぞれ導出します。

　定数$a$は$x$と無関係なので$\sum_x$の外に出せるので

$$ \begin{align*} \mathbb{E}[a x] &= \sum_x a x p(x) \\ &= a \sum_x x p(x) \\ &= a \mathbb{E}[x] \tag{1} \end{align*} $$

となります。

　括弧を展開して$x$と$y$を整理すると、(離散型の)確率分布の定義より$\sum_x p(x) = 1$、$\sum_y p(y) = 1$なので

$$ \begin{align*} \mathbb{E}[x + y] &= \sum_x \sum_y (x + y) p(x) p(y) \\ &= \sum_x \sum_y \Bigl\{ x p(x) p(y) + y p(x) p(y) \Bigr\} \\ &= \sum_x x p(x) \sum_y p(y) + \sum_x p(x) \sum_y y p(y) \\ &= \sum_x x p(x) + \sum_y y p(y) \\ &= \mathbb{E}[x] + \mathbb{E}[y] \tag{2} \end{align*} $$

となります。

　条件付き期待値$\mathbb{E}[x | y] = \sum_{x} x p(x | y)$は、条件となる確率$p(y)$を掛けて$y$について総和をとると

$$ \begin{align*} \sum_y \mathbb{E}[x | y] p(y) &= \sum_{x} \sum_y x p(x | y) p(y) \\ &= \sum_{x} x \sum_y p(x, y) \\ &= \sum_{x} x p(x) \\ &= \mathbb{E}[x] \tag{3} \end{align*} $$

となります。乗法定理より$p(x | y) p(y) = p(x, y)$、周辺化(周辺分布)より$\sum_y p(x, y) = p(x)$です。

　条件$z$の確率が条件付き確率$p(y | z)$の場合は

$$ \begin{align*} \sum_y \mathbb{E}[x | y] p(y | z) &= \sum_{x} \sum_y x p(x | y) p(y | z) \\ &= \sum_{x} x \sum_y p(x, y | z) \\ &= \sum_{x} x p(x | z) \\ &= \mathbb{E}[x | z] \tag{4} \end{align*} $$

条件が$y$から$z$に入れ替わります。条件付き同時分布の場合も、周辺化すると$\sum_y p(x, y | z) = p(x | z)$です。

・収益の計算式

　次に、収益の計算式を扱いやすいように変形します。収益の定義については「2.3：収益と状態価値関数【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

　時刻$t$における収益$G_t$は、割引率$0 \leq \gamma < 1$を用いて、次の式でした。

$$ G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \cdots \tag{2.1} $$

　この式について、時刻$t + 1$以降に注目します。

$$ \begin{aligned} G_t &= R_t + \Bigl( \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \cdots \Bigr) \\ &= R_t + \gamma \Bigl( R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \Bigr) \end{aligned} $$

　$\gamma$を括り出した丸括弧に注目すると、時刻$t + 1$における収益$G_{t+1}$と言えます。そこで、収益の定義式(2.1)に従い

$$ G_{t+1} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots $$

で置き換えます。(分かりにくければ、$t' = t + 1$とおくと$G_{t'} = R_{t'} + \gamma R_{t'+1} + \cdots$となり、式が一致しているのが分かります。)

$$ G_t = R_t + \gamma G_{t+1} \tag{3.3} $$

　「時刻$t$の収益$G_t$」は、「時刻$t$の報酬$R_t$」と「時刻$t + 1$の収益$G_{t+1}$」で計算できるのが分かりました。

・状態価値関数の計算式

　続いて、状態価値関数の計算式を扱いやすいように変形するための準備をします。状態価値関数の定義については「2.3：収益と状態価値関数【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

　状態価値関数(状態$s$における収益の期待値)は、次の式でした。

$$ v_{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s] \tag{2.3} $$

　この式に、収益の計算式(3.3)を代入して、項を分解します。

$$ \begin{align*} v_{\pi}(s) &= \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] \tag{3.5} \end{align*} $$

　「時刻$t$の報酬$R_t$の期待値」と「時刻$t + 1$の収益$G_{t+1}$の期待値」で計算できるのが分かりました。期待値の性質(1)と(2)を使って式を変形しました。

　次からは、この2つの期待値の計算式を求めます。

・報酬の期待値の計算式

　式(3.5)の前の項「時刻$t$における報酬$R_t$の期待値」の計算式を求めます。

　状態$s$において行動$a$を行い状態$s'$になるときの報酬(報酬関数)は$r(s, a, s')$でした(2.2.2項)。また、状態$s$で行動$a$を取る確率(確率的方策)は$\pi(a | s)$で(2.2.3項)、行動$a$を行い状態が$s$から$s'$になる確率(状態遷移確率)は$p(s' | s, a)$でした(2.2.1項)。つまり、ある状態$s$において報酬$r(s, a, s')$が得られる確率は、$a, s'$の同時確率$\pi(a | s) p(s' | s, a)$です(3.1.1項)。詳しくは「2.2：環境とエージェントの定式化【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

　時刻$t$において状態$s$の場面を考えます。この場面の状態を$S_t = s$で表し、$s$は現在の状態で固定されています。
　このとき、報酬$R_t$として得られる値は、$s'$として取り得る状態の数だけあります。よって、$R_t$の期待値は、「状態が$s$から$s'$に遷移する確率$p(s' | s)$」を用いて、次の式で計算できます。

$$ \begin{aligned} \mathbb{E}_{\pi}[R_t | S_t = s] &= \sum_{s'} R_t p(S_{t+1} = s' | S_t = s) \\ &= \sum_{s'} R_t p(s' | s) \end{aligned} $$

　この式では、固定された状態$s$から各状態$s'$となる確率に応じて報酬の加重平均をとる計算をしています。

　さらに、ある状態$s$からある状態$s'$に遷移する場面を考えます。ここでの$s'$は、1つの状態のことで、$\sum_{s'}$の内の1つを指します。
　状態が$s$から$s'$に遷移するパターンは、$a$として取り得る行動の数だけあります。よって、$p(s' | s)$は、状態$s$において各行動を行い$s'$となる確率の総和と言えます(遷移しないパターンも確率0として含まれます)。つまり、$p(s' | s)$は、「$s$を条件とする$s'$と$a$の同時分布$p(s', a | s)$」を$a$について周辺化した周辺分布

$$ p(s' | s) = \sum_a p(s', a | s) $$

として置き換えます。
　また、$s'$と$a$の同時分布は、確率的方策と状態遷移確率に分解できるので

$$ p(s', a | s) = \pi(a | s) p(s' | a, s) $$

で置き換えます。

$$ \begin{aligned} \mathbb{E}_{\pi}[R_t | S_t = s] &= \sum_{s'} R_t \sum_a p(s', a | s) \\ &= \sum_{s'} R_t \sum_a \pi(a | s) p(s' | a, s) \\ &= \sum_a \pi(a | s) \sum_{s'} p(s' | a, s) R_t \end{aligned} $$

　$R_t$の期待値の計算式に、行動$a$を導入できました。

　$s', a, s$と報酬の関係が分かったので、各報酬を$R_t = r(s', a, s)$で置き換えます。

$$ \mathbb{E}_{\pi}[R_t | S_t = s] = \sum_a \pi(a | s) \sum_{s'} p(s' | s, a) r(s, a, s') \tag{a} $$

　$R_t$の期待値の具体的な計算式が得られました。状態$s$から行動$a$により状態$s'$になる確率($a, s'$の同時確率)による報酬$r(s, a, s')$の期待値(確率で重み付けした総和)の計算をしているのが分かります。

・次の時刻の収益の期待値の計算式

　続いて、式(3.5)の後の項「時刻$t + 1$の収益$G_{t+1}$の期待値」の計算式を求めます。ただし、時刻$t$の状態が$s$という条件を持ちます。

　(時刻$t$における条件を持たない)時刻$t + 1$における状態価値関数(収益の期待値)を考えます。

$$ v_{\pi}(s') = \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] $$

　ここで知りたいのは、$S_t = s$を条件とする期待値$\mathbb{E}_{\pi}[G_{t+1} | S_t = s]$です。
　$\mathbb{E}_{\pi}[G_{t+1} | S_t = s]$は、上の式の右辺について、「状態が$S_t = s$から$S_{t+1} = s'$に遷移する確率$p(s' | s)$」を掛けて$s'$について総和をとることで得られます。

$$ \begin{aligned} \mathbb{E}_{\pi}[G_{t+1} | S_t = s] &= \sum_{s'} p(S_{t+1} = s' | S_t = s) \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] \\ &= \sum_{s'} p(s' | s) \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] \end{aligned} $$

　期待値の性質(4)によって条件を入れ替えています。

　先ほどと同様に、$p(s' | s)$を確率的方策と状態遷移確率に分解します。

$$ \begin{aligned} \mathbb{E}_{\pi}[G_{t+1} | S_t = s] &= \sum_{s'} \sum_a p(s', a | s) \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] \\ &= \sum_{s'} \sum_a \pi(a | s) p(s' | a, s) \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] \\ &= \sum_a \pi(a | s) \sum_{s'} p(s' | a, s) \mathbb{E}_{\pi}[G_{t+1} | S_{t+1} = s'] \end{aligned} $$

　1つ目の式を使って、期待値の項を$v_{\pi}(s')$に置き換えます。

$$ \mathbb{E}_{\pi}[G_{t+1} | S_t = s] = \sum_a \pi(a | s) \sum_{s'} p(s' | a, s) v_{\pi}(s') \tag{b} $$

　$G_{t+1}$の期待値の具体的な計算式が得られました。式(a)と同じ構造なのが分かります。

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

　2つの期待値の計算式が得られたので、ベルマン方程式の話に戻ります。

　状態価値関数(3.5)に、式(a)と(b)を代入して式を整理します。

$$ \begin{align*} v_{\pi}(s) &= \mathbb{E}_{\pi}[G_t | S_t = s] \tag{2.3}\\ &= \mathbb{E}_{\pi}[R_t | S_t = s] + \gamma \mathbb{E}_{\pi}[G_{t+1} | S_t = s] \tag{3.5}\\ &= \sum_a \pi(a | s) \sum_{s'} p(s' | s, a) r(s, a, s') + \gamma \sum_a \pi(a | s) \sum_{s'} p(s' | s, a) v_{\pi}(s') \\ &= \sum_a \pi(a | s) \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma v_{\pi}(s') \Bigr\} \tag{3.7} \end{align*} $$

　状態価値関数のベルマン方程式が得られました。ベルマン方程式(3.7)は、「状態$s$の価値関数$v_{\pi}(s)$」と「次の状態$s'$の価値関数$v_{\pi}(s')$」の関係を表します。

　以上で、状態価値関数のベルマン方程式を導出できました。次節では、このベルマン方程式を利用してみます。

参考文献

• 斎藤康毅『ゼロから作るDeep Learning 4 ――強化学習編』オライリー・ジャパン,2022年.
• サポートページ：GitHub - oreilly-japan/deep-learning-from-scratch-4

おわりに

　キツかった……半月くらいかかったけど、何をしてるのかがやっと分かって依存関係を整理できたのでなんとか理解できました。
　確率変数$S_t, A_t$と実現値$s, a$の関係をふわっとしか捉えてなかったのがマズかったです。他にも、正確な表現は分かりませんが、$s, s', a$がある1つの値を指しているのか変数として扱っているのかもふわふわしてて、各計算が何を意味していのかさっぱりでした。あと、行動$a$と方策$\pi$の違いとかもテキトーに考えてました。
　とりあえず時刻$t$で考えるのは止めて、$S_0, A_0$で進めると考えることが1つ減っていいんじゃないでしょうか。

　ぐちぐち言いましたが、こういったあれこれを頭の中で整理できてとても気分が良いです。

　さて、投稿日前日に公開された新MVを聴きましょう。

　(もうまーちゃんがいないなんて言わないよぜったい…)

【次節の内容】

www.anarchive-beta.com