はじめに
参考書籍
- メイン
- サブ
計算ルール（確率，期待値の基本）
本題
- 登場人物（強化学習に出てくる基本概念）
- ようやくBellman方程式へ
  - 状態価値関数についてのBellman方程式
  - 行動価値関数についてのBellman方程式
Sutton本との比較

はじめに

Qrunchに投稿した記事に少し追記したものです．というのも，現状Qrunchだと外部からの検索で上手く引っかからないよう（つまりGoogle検索で出てこない）．QrunchはQrunchコミュニティ内での気軽な技術系情報共有を目的にしているところがコンセプトっぽいので，あえて閉鎖的なコンテンツにしているということなのかもしれません．個人の勉強メモとして引き続きQrunchも活用していきたいと思っていますが，多少なりとも誰かの役に立ちそうな内容のものは積極的に外部に公開しても良いのかなと考えて，はてなも活用していこうと思っています．（Qrunchには「クロス投稿」機能があるので，それを使うのが良さそう）

モチベーション

強化学習のお勉強のため，Pythonで実装しようぜ系の本をしばらく読んでいたのですが，肝心のBellman方程式はわりとサラッと導出されていて，自分で手を動かして式を追ってみないとなんだかよくわからない．そうするにあたって瀧先生の深層学習本の強化学習の章における説明が個人的に分かりやすかったので，これを参考にBellman方程式導出の過程をまとめておく．この記事の目的はあくまでもBellman方程式を導出するまでのひとつひとつの式変形のステップを省略せずにまとめておくことなので，強化学習そのものについては次節で挙げている書籍を参考にされてください．

Bellman方程式ってなに

Bellman方程式とは，価値関数を状態 $s$ と次の状態 $s'$ についての漸化式として表したものである．再帰的に価値関数を表すことの必要性は書籍「Pythonで学ぶ強化学習」に易しい解説があり，分かりやすいと思う．

Bellman方程式の導出の流れ

量の書き換えがいくつか出て来て最初は混乱したのですが，やっていることは単純で，以下の二点にまとめられる．

報酬の再帰性を使って，価値関数を漸化式の形に書く．
マルコフ性によって依存関係を整える．

参考書籍

メイン

瀧雅人，「機械学習スタートアップシリーズ　これならわかる深層学習入門 (KS情報科学専門書) 」，講談社，2018.

サブ

計算ルール（確率，期待値の基本）

Bellman方程式の導出で必要になる計算ルールを予備知識としてまとめておく．これらに加えて，強化学習の問題設定がマルコフ決定過程であることを利用して話が進んでいきます．確率の基礎にまつわる話は個人的に「プログラミングのための確率統計」が直感的で分かりやすいので，脳が混乱したときには読み返している．

周辺化

基本

$\displaystyle{ P(A)=\sum_{B}P(A,B) }$

ですよね．同時分布をある確率変数について和を取れば，括弧からそいつが消えます．得られた $P(A)$ を周辺分布という．

例

Bellman方程式の導出では，たとえば遷移確率を周辺化によって次のように式変形する．強化学習では基本的に条件付き分布ばかりを扱いますが，上で見た基本式のおしりに条件がくっついてるだけ．

$\displaystyle{ P^{\pi}(s'|s)=\sum_{a}P(s',a|s) }$

同時確率と条件付き確率の関係（乗法定理）

基本

$P(A,B)=P(A|B)P(B)$

例

これを使って先ほどの周辺化の例を， $\displaystyle{ P^{\pi}(s'|s)=\sum _ aP(s',a|s)=\sum _ aP(s'|a,s)P(a|s) }$

というように変形していったりする．

条件付き期待値

基本1

条件付き期待値の定義はこう．

$\displaystyle{ E[Y|a]= \sum _ {b} bP(Y=b|a) }$

基本2

$\displaystyle{ \sum_aE[Y|a] P(a)=E[Y] }$

こうなることを一応確認しておく．

\begin{align} \sum_aE[Y|a]P(a) &= \sum_a\sum_bbP(b|a)P(a) \\ &= \sum_a\sum_bbP(a,b) \\ &= \sum_bb\left(\sum_aP(a,b)\right) \\ &= \sum_bbP(b) \\ &= E[Y=b] \end{align}

例

$\displaystyle{ V ^ \pi (s)=E _ {p,\pi}[R(t)|s=s(t)]=\sum _ a E[R(t)|s,a]P(a|s) }$

本題

登場人物（強化学習に出てくる基本概念）

遷移確率

状態 $s$ で行動 $a$ を取ったときに状態 $s'$ に遷移する確率． $P(s'|s,a)=P(s'=s(t+1)|s=s(t),a=a(t))$

取り得る全ての行動について足し合わせると（計算ルールのところで確認した周辺化），状態 $s$ から $s'$ への遷移確率になる．

$P^{\pi}(s'|s)=\sum_{a}P(s'|s,a) P(a|s)=\sum_a\pi(a|s)P(s'|s,a)$

ここで，状態 $s$ において行動 $a$ を選択する確率は方策と呼ばれ，特別に $\pi$ と書く．

$\pi(a|s)=P(a|s)$

利得（累積報酬）

$\displaystyle{ R(t)=r(t+1)+\gamma r(t+2)+\gamma^2 r(t+3)+\cdots=\sum_{k=0}^\infty \gamma^k r(t+k+1) }$

$\gamma$ は割引率．累積報酬とか割引報酬和，割引累積報酬なんて呼ぶのが意味が分かりやすくて好きだが，単に報酬や利得と呼ばれることも多いっぽい．これは第1項と残りを分けることで再帰的に書くことができる．

$\displaystyle{ \begin{align} R(t)&=r(t+1)+\gamma \left(r(t+2)+\gamma r(t+3)+\cdots\right)\\ &=r(t+1)+\sum_{k=0}^\infty \gamma^k r(t+k+2) \\ &=r(t+1)+\gamma R(t+1) \end{align} }$

ちなみに $r=r(t+1)$ は，行動 $a$ によって，状態 $s=s(t)$ から状態 $s'=s(t+1)$ になったときに得る即時報酬．貰うタイミングは時刻 $t+1$ ．

即時報酬の期待値

大文字の $R$ で書いているが，上の累積報酬ではなく時刻 $t+1$ の即時報酬についての話である．

$R(s,a,s')=E_P [r(t+1)|s',s,a]=\sum_{rr}P(r|s',s,a)$

上で書いているように $r=r(t+1)$ なので，右辺の意味は以下のとおり． $\sum_{r(t+1)}r(t+1)P(r(t+1)|s',s,a)$

状態 $s$ での報酬の期待値は，上記の量を行動 $a$ と次の状態 $s'$ について期待値を取る．要するに，行動や次の状態にかかわらず，「ただ状態 $s$ にいるだけで」これくらいの報酬が得られるだろうと期待できるということ．ここで重みとして用いる確率は， $a$ を取る確率と， $s'$ となる確率なのだから，すなわち方策と遷移確率ですね． $R^\pi (s)=\sum_{a,s'}\pi(a|s)P(s'|s,a)R(s,a,s')$

価値関数

状態価値関数 $V$

ある状態 $s$ であったとき，得られるであろう累積報酬 $R(t)$ の期待値を状態価値関数と呼ぶ．これによって各状態の良し悪し（価値）が評価できる． $V^\pi(s)=E_{P, \pi}[R(t)|s$ ] ここでの添字 $P$ と $\pi$ の意味は，さきほど出て来た即時報酬の期待値と同様に，遷移確率 $P$ と方策 $\pi$ で期待値を取っているよということ．

行動価値関数 $Q$

状態 $s$ において行動 $a$ を取ったときの累積報酬 $R(t)$ の期待値． $Q^\pi(s,a)=E_P[R(t)|s,a]$

$V$ と $Q$ の関係

計算ルールの条件付き期待値のところで見たように， $V^\pi(s)=E_{P, \pi}[R(t)|s]=\sum_aE_P[R(t)|s,a]P(a|s)=\sum_a\pi(a|s)E_P[R(t)|s,a]$

と書き換えられる．最右辺の条件付き期待値はまさに $Q$ だから， $V^\pi(s)=\sum_a\pi(a|s)Q^\pi(s,a)$

ようやくBellman方程式へ

状態価値関数 $V$ についてのBellman方程式

さきほどの「 $V$ と $Q$ の関係」で出て来たように，

$V^\pi(s)=E_{P, \pi}[R(t)|s] =\sum_a\pi(a|s)E_P[R(t)|s,a]$

予備知識の計算ルールである条件付き期待値の性質を使って，条件に $s'$ を追加する．

$E_P[R(t)|s,a]=\sum_{s'} E_P[R(t)|s',s,a]P(s'|s,a)$

するとVは

$\displaystyle{ \begin{align} V^\pi(s) &=E_{P, \pi} [R(t)|s] \\ &=\sum_a\pi(a|s)E_P[R(t)|s,a] \\ &=\sum_{a,s'}\pi(a|s)P(s'|s,a)E_P[R(t)|s',s,a] \end{align} }$

となりますね．

累積報酬を再帰的に書くと $R(t)=r(t+1)+\gamma R(t+1)$

だったから，これを上の式に入れてやる．そうすると，

$\displaystyle{ \begin{align} V^\pi(s)&=\sum_{a,s'}\pi(a|s)P(s'|s,a)E_P[R(t)|s',s,a] \\ &=\sum_{a,s'}\pi(a|s)P(s'|s,a)E_P[r(t+1)+\gamma R(t+1)|s',s,a] \\ &=\sum_{a,s'}\pi(a|s)P(s'|s,a)\left(E_P[r(t+1)|s',s,a]+E_P[\gamma R(t+1)|s',s,a]\right) \end{align} }$

となって，即時報酬 $r(t+1)$ の期待値が出て来た．これは上で見たように

$R(s,a,s')=E_P [r(t+1)|s',s,a$ ]

と表していたので，これを使ってさらに書き換えると

$\displaystyle{ \begin{align} V^\pi(s)&=\sum_{a,s'}\pi(a|s)P(s'|s,a)\left(E_P[r(t+1)|s',s,a]+E_P[\gamma R(t+1)|s',s,a]\right) \\ &=\sum_{a,s'}\pi(a|s)P(s'|s,a)\left(R(s,a,s')+E_P[\gamma R(t+1)|s',s,a]\right) \end{align} }$

ここで出て来た $R^\pi (s)$ は

$R^\pi (s)=\sum_{a,s'}\pi(a|s)P(s'|s,a)R(s,a,s')$

なのでした．したがって

$\displaystyle{ V^\pi(s)=R^\pi (s)+\sum_{a,s'}\pi(a|s)P(s'|s,a)E_P[\gamma R(t+1)|s',s,a] }$

この第2項目には遷移確率が含まれているから，

$\displaystyle{ \sum_{s'}\left(\sum_{a}\pi(a|s)P(s'|s,a)\right)E_P[\gamma R(t+1)|s',s,a]=\gamma \sum_{s'}P^\pi(s'|s)E_P[R(t+1)|s',s,a] }$

さてここで， $R(t+1)$ は状態 $s'=s(t+1)$ から $s''=s(t+2)$ となった時点以降の累積報酬である．これは状態 $s$ と行動 $a$ には依存しない（マルコフ性）．そういうわけで上の式の中の条件付き期待値は，

$E_P[R(t+1)|s',s,a]=E_P[R(t+1)|s']=V^\pi (s')$

となり，これは結局，次の状態 $s'$ での状態価値関数 $V(s')$ であった．したがって最終的に，

$V^\pi(s)=R^\pi (s)+\gamma \sum_{s'}P^\pi(s'|s)V^\pi (s')$

となって，これが状態価値関数についてのBellman方程式です．

行動価値関数 $Q$ についてのBellman方程式

行動価値関数は

$Q^\pi(s,a)=E_P[R(t)|s,a$ ]

なのでした．これを $V$ に対してやったのと同様に，計算ルールである条件付き期待値の性質を使って $s'$ について和を取ります．それから $R(t)=r(t+1)+\gamma R(t+1)$ を代入して二つの項に分けます．そうすると第1項には $R(s,a,s')$ が現れます．第2項はマルコフ性によって条件付き期待値から $s$ と $a$ が除かれて，その結果 $V^\pi(s')$ が出て来る．

$\displaystyle{ \begin{align} Q^\pi(s,a)&=E_P[R(t)|s,a] \\ &=\sum_{s'}P(s'|s,a)E_P[R(t)|s,a,s'] \\ &=\sum_{s'}P(s'|s,a)E_P[r(t+1)+\gamma R(t+1)|s,a,s'] \\ &=\sum_{s'}P(s'|s,a)E_P[r(t+1)|s,a,s']+\sum_{s'}P(s'|s,a)E_P[\gamma R(t+1)|s,a,s'] \\ &=\sum_{s'}P(s'|s,a)R(s,a,s')+\gamma \sum_{s'}P(s'|s,a)E_P[R(t+1)|s,a,s'] \\ &=\sum_{s'}P(s'|s,a)R(s,a,s')+\gamma \sum_{s'}P(s'|s,a)E_P[R(t+1)|s'] \\ &=\sum_{s'}P(s'|s,a)R(s,a,s')+\gamma \sum_{s'}P(s'|s,a)V^\pi(s') \end{align} }$

「 $V$ と $Q$ の関係」で見たように

$V^\pi(s)=\sum_a\pi(a|s)Q^\pi(s,a)$

だったから，

$V^\pi(s')=\sum_{a'}\pi(a'|s')Q^\pi(s',a')$

である．これを使って書き換えれば，

$\displaystyle{ \begin{align} Q^\pi(s,a)&=\sum_{s'}P(s'|s,a)R(s,a,s')+\gamma \sum_{s'}P(s'|s,a)\sum_{a'}\pi(a'|s')Q^\pi(s',a') \\ &=\sum_{s'}P(s'|s,a)R(s,a,s')+\gamma \sum_{s'}\sum_{a'}\pi(a'|s')P(s'|s,a)Q^\pi(s',a') \end{align} }$

となる．これが行動価値関数 $Q$ についてのBellman方程式．

Sutton本との比較

Sutton本と瀧深層学習本はそれぞれ量の表記が異なるので，同じ方程式であるのか一目見るだけでは私は脳のメモリが足りずよく分からない．というわけで互いに同一の結果を得ていることを確認しておく．Sutton本だとp.76の式(3.10)で $V$ についてのBellman方程式が示されている．

$\displaystyle{ V^\pi(s)=\sum_{a}\pi(s,a)\sum_{s'}P_{ss'}^{a}\left[R_{ss'}^{a}+\gamma V^\pi (s')\right] }$

まず $\pi(s,a)$ であるが，p.56にて説明がなされており，これはこれまで見てきた $\pi(a|s)$ と同じものである．Sutton本では， $\pi$ が $s$ と $a$ の関数であることを明示した表記を取っていると私は解釈した．次に $P_{ss'}^{a}$ と $R_{ss'}^{a}$ はp.72の式(3.6)と(3.7)で説明がされているように，

$P_{ss'}^{a}=P(s'|s,a)$

$\displaystyle{ R_{ss'}^{a}=E[r_{t+1}|s,a,s'] }$

である．ここで $r_{t+1}$ と書かれているのは， $r_{t+1}=r(t+1)$ ということである．以上を踏まえて，瀧深層学習本での表記に合わせるようにSutton本のBellman方程式を書き換えてみる．

$\displaystyle{ \begin{align} V^\pi(s)&=\sum_{a}\pi(s,a)\sum_{s'}P_{ss'}^{a}\left[R_{ss'}^{a}+\gamma V^\pi (s')\right] \\ &=\sum_{a}\pi(a|s)\sum_{s'}P(s'|s,a)\left(E_P[r(t+1)|s,a,s']+\gamma V^\pi (s')\right) \end{align} }$

この時点で，あぁ，同じやんけ，と安心するのだが，折角なので最後まで書き換える．ここで以下の3つを思い出す．

$E_P [r(t+1)|s',s,a]=R(s,a,s')$

$R^\pi (s)=\sum_{a,s'}\pi(a|s)P(s'|s,a)R(s,a,s')$

$P^{\pi}(s'|s)=\sum_a\pi(a|s)P(s'|s,a)$

これらを使って書き換えると，

$\displaystyle{ \begin{align} V^\pi(s)=R^\pi (s)+\gamma \sum_{s'}P^\pi(s'|s)V^\pi (s') \end{align} }$

となって，瀧深層学習本のBellman方程式に一致した．安心した．

ギャラクシースーパーはてなブログ

ギャラクシースーパーノヴァ子の日記だお

【強化学習】Bellman方程式の導出