MDPによる強化学習：ベルマン方程式

価値関数を再帰的に扱い、ベルマン方程式を導出する。
ベルマン方程式を導出するにあたっては、時刻$${t}$$での状態と行動を条件とした$${t+1}$$での報酬の期待値である
$${E_{\pi}[G_{t+1}|S_t=s, A_t=a]}$$
の計算が出てくる。
本来、時刻$${t+1}$$での報酬の期待値は、
$${E_{\pi}[G_{t+1}|S_{t+1}=s', A_{t+1}=a']}$$
で与えられる。ここで、時刻$${t}$$での状態と行動と区別するために、それぞれに$${'}$$をつけている。
時刻$${t}$$での状態と行動からの$${t+1}$$での報酬の期待値とは、言い換えれば、$${S_t=s,A_t=a}$$を条件とする$${G_{t+1}}$$の期待値と言えることから、$${S_t=s,A_t=a}$$なる条件付きの$${S_{t+1}=s',A_{t+1}=a'}$$の同時確率$${Pr(s',a'|s,a)}$$をかけ、$${s',a'}$$で足し上げれば良い。また、$${Pr(s',a'|s,a)}$$を確立的ポリシーと環境の状態遷移確率で表せば、$${\pi(a'|s')Pr(s',r|s,a)}$$である。
よって、
$${E_{\pi}[G_{t+1}|S_t=s, A_t=a]}$$
$${=\sum_{s'\in S,a\in A'}Pr(s',a'|s,a)E_{\pi}[G_{t+1}|S_{t+1}=s', A_{t+1}=a']}$$
$${=\sum_{s'\in S,a\in A',r \in R}\pi(a'|s')Pr(s',r|s,a)E_{\pi}[G_{t+1}|S_{t+1}=s', A_{t+1}=a']}$$
となる。
$${E_{\pi}[G_{t+1}|S_{t+1}=s', A_{t+1}=a']=q_{\pi}(s',a')}$$であり、$${\sum_{a' \in A}\pi(a'|s')q_{\pi}(s',a')=\nu_{\pi}(s')}$$であるから、
$${E_{\pi}[G_{t+1}|S_t=s, A_t=a]=\sum_{s'\in S,r \in R}Pr(s',r|s,a)\nu_{\pi}(s')}$$で与えられる。

また、即時報酬の期待値$${E_{\pi}[r]}$$は、環境の状態が$${s_{t}}$$から$${s_{t+1}}$$になりエージェントに報酬$${r}$$を渡す定義から、$${r}$$は${s_{t+1}}$$のとりえる状態の数だけ存在することになる。
よって、
$${E_{\pi}[r]=\sum_{s'\in S}rPr(s',r|s,a)}$$
で与えられる。

利息の再帰的式と状態価値関数と行動価値関数の関係から、
$${\nu_{\pi}(s)=\sum_{a\in A} \pi(a|s)q_{\pi}(s,a)=\sum_{a\in A}\pi(a|s)E_{\pi}[r+\gamma G_{t+1}|S_t=s,A_t=a]}$$
　上記の２式を用いて、
$${\sum_{a\in A}\pi(a|s)E_{\pi}[r+\gamma G_{t+1}|S_t=s,A_t=a]=\sum_{a\in A}\pi(a|s)\sum_{s' \in S, r \in R}Pr(s',r|s,a)(r+\gamma \nu_{\pi}(s'))}$$
よって、状態価値関数のベルマン方程式は、
$${\nu_{\pi}(s)=\sum_{a\in A}\pi(a|s)\sum_{s' \in S, r \in R}Pr(s',r|s,a)[r+\gamma\nu_{\pi}(s')]}$$
と与えられる。

　同様に行動価値関数においても、利得の再帰表記から
$${q_{\pi}(s,a)=E_{\pi}[r+\gamma G_{t+1}|S_t=s,A_t=a]=\sum_{s' \in S, r\in R}r Pr(s',r|s,a)+ \gamma E_{\pi}[G_{t+1}|S_t=s, A_t=a]}$$
$${=\sum_{s' \in S, r\in R}r Pr(s',r|s,a)+\gamma \sum_{s'\in S}Pr(s',r|s,a)\nu_{\pi}(s')=\sum_{s' \in S, r\in R}Pr(s',r|s,a)(r+\gamma\nu_{\pi}(s'))}$$
となる。
　この標識を行動価値関数のベルマン方程式と呼ぶ。