大学数学

HOME
大学数学
ベルマン方程式をわかりやすく解説|強化学習や動的計画法

05/11/2022 / 最終更新日時 : 09/16/2024 bluest 大学数学

ベルマン方程式をわかりやすく解説|強化学習や動的計画法

こんにちは、青の統計学です。

今回は、ベルマン方程式についてわかりやすく解説します。

管理人は経済学部出身だったので動的計画法の文脈で学びました。

情報数理であれば、強化学習のアルゴリズムで学びますね。

こちらでも簡単にまとめていますが、より深く学びたい方は本コンテンツをご覧いただければと思います。

ベルマン方程式|Bellman function

Bellman方程式とは，価値関数を状態$S$と次の状態$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(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) }$$

$γ$は割引率と呼びます。

これは第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)$になったときに得る即時報酬です。

なぜ、第1項と残りを分けたかというと、即時価値と将来価値を分けるためです。

もっとわかりやすく言えば、エージェントは目先の利益を最大化するだけではなく、将来にわたって利得の合計を最大化するのです。

ただ時刻$t$において$t+1$期の報酬などわかるわけないので、割引率$γ$をかけて報酬を割り引く必要があるというわけです。

さて、ここまで話した即時価値の期待値をとってみましょう。

$$R(s,a,s’)=E_P [r(t+1)|s’,s,a]=\sum_{rr}P(r|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^\pi(s)=E_{P, \pi}[R(t)|s]$$

ここでの添字$P$と$π$の意味は，さきほど出て来た即時報酬の期待値と同様に，遷移確率$P$と方策$π$で期待値を取っているという意味です。

さて、この状態価値関数とは別に「今の状態で行動$a$をとった時の累積報酬の期待値」も考えねばなりません。

これを行動価値関数と呼びます。

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

$$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)$$

ベルマン方程式とマルコフ性

ここまでで、状態価値関数と行動価値関数の関係は分かりましたが、実はまだベルマン方程式ではないです。

大雑把にやることとしては、次の状態$s’$で条件づけることです。

なぜでしょうか？

ベルマン方程式の導出において、状態 $s$から次の状態$s’$ を条件付けする理由は、マルコフ決定過程の性質から来ています。

マルコフ決定過程では、現在の状態と行動が与えられた時、次の状態と報酬はそれらにのみ依存し、過去の履歴には依存しない（マルコフ性）という前提があります。

$$Pr(X_{n+1}=j|X_{n},X_{n-1},…,X_0)=Pr(X_{n+1},X_n=i)$$

この性質により、次の状態 $s$ とその時の報酬を考慮することで、現在の状態$s’$の価値を計算することが可能になります。

マルコフ性については、以下のコンテンツでまとめています。

【完全ガイド】MCMC法についてわかりやすく解説|ベイズ推定

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

さて、状態価値関数(以下V)のベルマン方程式から導出していきます。

Vについてのベルマン方程式とQについてのベルマン方程式が両方導出できる理由は、これらが異なる視点（状態の価値 vs. 特定の行動を取った時の価値）から同じマルコフ決定過程をモデル化しているためです。

Vは状態の価値のみを考慮し、Qは特定の行動を取った場合の価値を考慮しますが、どちらも同じプロセス（MDP）に基づいております。

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

もともと上の式でした。

さて、では条件づけてみましょう。

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

$$\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)=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} }$$

右の方の$E_P[\gamma R(t+1)|s’,s,a]$は、即時報酬の期待値ですね。

こちらも先程は、$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} }$$

もう一息です！

式の一部を、$\sum_{a,s’}\pi(a|s)P(s’|s,a)R(s,a,s’)=R^{\pi} (s)$のように、$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項目には遷移確率が含まれているから，方策$a$で条件づけているところは消せます。

加えて、期待値に関係のない$γ$は外に出しちゃいましょう。

$$\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] }$$

さて、$E_P[R(t+1)|s’,s,a] $は、方策と状態2つで条件づけていますが、$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’)$という、次の状態の状態価値観数になりました。感動。

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

つまり、これが状態価値関数におけるベルマン方程式です。

応用の話で言うと、価値反復アルゴリズムでは、価値関数 $V(s)$が収束するまで繰り返し更新されます。

各繰り返しで、ベルマン方程式を使って、各状態における価値の推定値を更新します。

これを、価値反復アルゴリズム（Value Iteration)と呼びます。

行動価値関数のベルマン方程式の導出

こちらの導出もやることは同じで、$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’)$なので、

$$\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} }$$

これが行動価値関数のベルマン方程式になります。