Bellman Equationをふわっと理解する

引き続き機械学習の勉強をしており，今は強化学習と和解中である．

今回はBellman Equationについて具体的な例を考えることで和解を試みる．

報酬 $R$ が現在の状態 $s$ のみで決まる場合( $R(s)$ )のBellman Equationは以下となる．

$\begin{align} \displaystyle V(s)=R(s)+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s,a)V(s^{\prime})\tag{1} \end{align}$

以下のような例題を考える．
赤か青かを3回言うゲームを考える．
最終的に赤を2回以上言えば1点もらえる．
最終的に赤が1回以下なら-1点だ．

状態 $s$ の例
$s=(1回目の色, 2回目の色, \ldots)$
$s=({\rm red}, {\rm red})$
$s=({\rm red}, {\rm blue})$
$s=({\rm blue})$
$s=({\rm red}, {\rm red}, {\rm red})$
$s=({\rm red}, {\rm blue}, {\rm blue})$

行動 $a$
$a={\rm red}$
$a={\rm blue}$

報酬 $R(s)$ の例
$R({\rm red}, {\rm red}, {\rm red})=1$
$R({\rm red}, {\rm red}, {\rm blue})=1$
$R({\rm blue}, {\rm red}, {\rm blue})=-1$
$R({\rm blue})=0$
$R({\rm red}, {\rm red})=0$

遷移確率 $T$ は，期待した行動になる確率を $0.9$ ，それ以外を $0.1$ とする．
遷移確率 $T$ の例
$T(s^{\prime}=({\rm red}, {\rm red}) | s=({\rm red}), a={\rm red})=0.9$
$T(s^{\prime}=({\rm red}, {\rm blue}) | s=({\rm red}), a={\rm red})=0.1$
方策関数が赤を出力し，実際に状態が赤に遷移する確率が $0.9$ ということである．

それではやっていく．
(1)式で難しいのは $\max$ 以降の部分だ．ここをよく考える．

$\begin{align} \displaystyle \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s,a)V(s^{\prime})\tag{2} \end{align}$

まず $\underset{a}{\max}$ についてだが，これはある行動 $a=a_x$ を取った際に得られる報酬を比較し，より大きい報酬が得られる $a=a_X$ を採用するという話である．
今回の場合は $a={\rm red}$ と $a={\rm blue}$ でどちらが良いかを比較するということになる．

次に $\Sigma$ については，ある行動 $a=a_x$ を取った際に得られる報酬の期待値を表す．

$s=({\rm red}, {\rm blue})$ を考えよう．2回目まで色が確定した状態である．
次の状態 $s^{\prime}$ が $s^{\prime}=({\rm red}, {\rm blue},{\rm red})$ となれば勝ち， $s^{\prime}=({\rm red}, {\rm blue},{\rm blue})$ となれば負けである．

行動 $a={\rm red}$ を取れば勝ち確定かと思ってしまうが，状態遷移は遷移確率 $T(s^{\prime}|s,a)$ に従って遷移するため，実際には $0.9$ の確率で $s^{\prime}=({\rm red}, {\rm blue},{\rm red})$ に遷移し， $0.1$ の確率で $s^{\prime}=({\rm red}, {\rm blue},{\rm blue})$ に遷移する．
状態 $s=({\rm red}, {\rm blue})$ において行動 $a={\rm red}$ を取った際の遷移確率を数式で書くと以下となる．
$T(s^{\prime}=({\rm red}, {\rm blue},{\rm red})|s=({\rm red}, {\rm blue}),a={\rm red}) = 0.9$
$T(s^{\prime}=({\rm red}, {\rm blue},{\rm blue})|s=({\rm red}, {\rm blue}),a={\rm red}) = 0.1$

f:id:Yuri-Processing-Club:20220109102346p:plain

ここから報酬の期待値を計算しよう．
報酬の期待値は確率×報酬の総和で得られる．
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm b}),a={\rm r})V(s^{\prime}) \\ = T(s^{\prime}=({\rm r}, {\rm b},{\rm r})|s=({\rm r}, {\rm b}),a={\rm r})V(s^{\prime}=({\rm r}, {\rm b},{\rm r}))\\ {+} T(s^{\prime}=({\rm r}, {\rm b},{\rm b})|s=({\rm r}, {\rm b}),a={\rm r})V(s^{\prime}=({\rm r}, {\rm b},{\rm b}))\\ = 0.9V(s^{\prime}=({\rm r}, {\rm b},{\rm r})) + 0.1 V(s^{\prime}=({\rm r}, {\rm b},{\rm b}))\\ = 0.9(+1)+0.1(-1)\\ =0.8$

同様に行動 $a={\rm blue}$ を取った際も計算しよう．
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm b}),a={\rm b})V(s^{\prime}) \\ = T(s^{\prime}=({\rm r}, {\rm b},{\rm r})|s=({\rm r}, {\rm b}),a={\rm b})V(s^{\prime}=({\rm r}, {\rm b},{\rm r}))\\ {+} T(s^{\prime}=({\rm r}, {\rm b},{\rm b})|s=({\rm r}, {\rm b}),a={\rm b})V(s^{\prime}=({\rm r}, {\rm b},{\rm b}))\\ = 0.1V(s^{\prime}=({\rm r}, {\rm b},{\rm r})) + 0.9 V(s^{\prime}=({\rm r}, {\rm b},{\rm b}))\\ = 0.1(+1)+0.9(-1)\\ =-0.8$

以上の結果により，行動 $a={\rm red}$ を取った際の報酬の期待値は $0.8$ ， $a={\rm blue}$ を取った際の報酬の期待値は $-0.8$ となり， $s=({\rm r}, {\rm b})$ における最適な行動は $a={\rm red}$ であることが分かった．

$\begin{align} \displaystyle \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm b}),a)V(s^{\prime})=0.8 \end{align}$

また，これを(1)式に代入してみる．なお， $\gamma=0.99$ とする．
$\begin{align} \displaystyle V(s=({\rm r}, {\rm b}))&=R(s=({\rm r}, {\rm b}))+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm b}),a)V(s^{\prime})\\ &=0+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm b}),a)V(s^{\prime})\\ &=0+0.99 × 0.8 \\ &= 0.792 \end{align}$

同様にして， $V(s=({\rm b}, {\rm r}))=0.792$ であることも明らかである．

次に， $V(s=({\rm r}, {\rm r}))$ を考える．これも(1)式に代入して，
$\begin{align} \displaystyle V(s=({\rm r}, {\rm r}))&=R(s=({\rm r}, {\rm r}))+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm r}),a)V(s^{\prime})\\ &=0+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}, {\rm r}),a)V(s^{\prime})\\ &=0+0.99 × 1 \\ &= 0.99 \end{align}$
行動 $a$ がどんな値であっても勝ち確定なので上記のような結果となる．
同様にして $V(s=({\rm b}, {\rm b}))=-0.99$ となる．

次に考えるのは $V(s=({\rm r}))$ の場合だ．
(1)式に代入して，
$\begin{align} \displaystyle V(s=({\rm r}))&=R(s=({\rm r}))+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a)V(s^{\prime})\\ &=\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a)V(s^{\prime})\tag{3} \end{align}$
$a={\rm red}$ の場合
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a={\rm r})V(s^{\prime})\\ =T(s^{\prime}=({\rm r}, {\rm r})|s=({\rm r}),a={\rm r})V(s^{\prime}=({\rm r}, {\rm r})) + T(s^{\prime}=({\rm r}, {\rm b})|s=({\rm r}),a={\rm r})V(s^{\prime}=({\rm r}, {\rm b}))\\ =0.9 × 0.99 + 0.1 × 0.792\\ =0.9702$
$a={\rm blue}$ の場合
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a={\rm b})V(s^{\prime})\\ =T(s^{\prime}=({\rm r}, {\rm r})|s=({\rm r}),a={\rm b})V(s^{\prime}=({\rm r}, {\rm r})) + T(s^{\prime}=({\rm r}, {\rm b})|s=({\rm r}),a={\rm b})V(s^{\prime}=({\rm r}, {\rm b}))\\ =0.1 × 0.99 + 0.9 × 0.792\\ =0.0706$
よって(3)式に代入して

$\begin{align} \displaystyle V(s=({\rm r}))&=\gamma × 0.9702 = 0.96 \end{align}$

$V(s=({\rm b}))$ も同様に考えよう．
(1)式に代入して，
$\begin{align} \displaystyle V(s=({\rm b}))&=R(s=({\rm b}))+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm b}),a)V(s^{\prime})\\ &=\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=({\rm b}),a)V(s^{\prime})\tag{4} \end{align}$
$a={\rm red}$ の場合
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm b}),a={\rm r})V(s^{\prime})\\ =T(s^{\prime}=({\rm b}, {\rm r})|s=({\rm b}),a={\rm r})V(s^{\prime}=({\rm b}, {\rm r})) + T(s^{\prime}=({\rm b}, {\rm b})|s=({\rm r}),a={\rm r})V(s^{\prime}=({\rm b}, {\rm b}))\\ =0.9 × 0.792 + 0.1 × (-0.99)\\ =0.6138$
$a={\rm blue}$ の場合
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a={\rm b})V(s^{\prime})\\ =T(s^{\prime}=({\rm b}, {\rm r})|s=({\rm b}),a={\rm b})V(s^{\prime}=({\rm b}, {\rm r})) + T(s^{\prime}=({\rm b}, {\rm b})|s=({\rm b}),a={\rm b})V(s^{\prime}=({\rm b}, {\rm b}))\\ =0.1 × 0.792 + 0.9 × (-0.99)\\ =-0.8118$
よって(4)式に代入して

$\begin{align} \displaystyle V(s=({\rm b}))&=\gamma × 0.6138 = 0.677 \end{align}$

最後に初期状態 $s=()$ から開始しよう．
(1)式に代入して，
$\begin{align} \displaystyle V(s=())&=R(s=())+\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=(),a)V(s^{\prime})\\ &=\gamma \underset{a}{\max} \sum_{s^{\prime}} T(s^{\prime}|s=(),a)V(s^{\prime})\tag{5} \end{align}$

$a={\rm red}$ の場合
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=(),a={\rm r})V(s^{\prime})\\ =T(s^{\prime}=({\rm r})|s=(),a={\rm r})V(s^{\prime}=({\rm r})) + T(s^{\prime}=({\rm b})|s=(),a={\rm r})V(s^{\prime}=({\rm b}))\\ =0.9 × 0.96 + 0.1 × 0.677\\ =0.9317$
$a={\rm blue}$ の場合
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=(),a={\rm b})V(s^{\prime})\\ =T(s^{\prime}=({\rm r})|s=(),a={\rm b})V(s^{\prime}=({\rm r})) + T(s^{\prime}=({\rm b})|s=(),a={\rm b})V(s^{\prime}=({\rm b}))\\ =0.1 × 0.96 + 0.9 × 0.677\\ =0.7053$
よって(5)式に代入して