動的計画法をふわっと理解する

今回も数式に具体例を当てはめることで理解したつもりになっていくことにする．

報酬 $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}$

$V(s)$ を求めるには $V(s^{\prime})$ が求まっている必要があり， $V(s^{\prime})$ の計算には $V(s^{\prime \prime})$ が必要で……という感じで，全ての値が計算済である必要がある．
全ての計算を行うのは困難なことがある．動的計画法では $V(s^{\prime})$ に適当な値を入れておいて，複数回計算を繰り返すことで値の精度を上げていくものである．

動的計画法により各状態の価値を計算する方法が価値反復法（Value Iteration）である．
Bellman Equationを以下のように書き直す．

$\begin{align} \displaystyle V_{i+1}(s)= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s,a) \Bigl( R(s) + \gamma V_i(s^{\prime}) \Bigr) \biggr\} \tag{2} \end{align}$
*1

$V_{i+1}$ は前回の計算結果 $V_{i}$ を使って求められる．
これを繰り返し， $|V_{i+1}-V_{i}|< \epsilon$ となった時点で計算を終了する．
なお， $V_0 = 0$ と初期化しておく．

具体例にて計算してみよう．
例題は前回の記事と同様のものを用いる．

yuri-processing-club.hatenablog.com

遷移図は以下のような感じだ．
f:id:Yuri-Processing-Club:20220110165135p:plain

$i=0$ の時， $V_0=0$ に注意して計算すると，
$\begin{align} \displaystyle V_{1}(s=())&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=(),a) \Bigl( R(s=0) + \gamma V_0(s^{\prime}) \Bigr) \biggr\}\\ &= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=(),a) \Bigl( 0 + \gamma 0 \Bigr) \biggr\}\\ &=0 \end{align}$
同様にして， $V_1(s=({\rm r}))=V_1(s=({\rm b}))=0$ ， $V_1(s=({\rm r},{\rm r}))=V_1(s=({\rm r},{\rm b}))=V_1(s=({\rm b},{\rm r}))=V_1(s=({\rm b},{\rm b}))=0$ である．
$\begin{align} \displaystyle V_{1}(s=({\rm r},{\rm r},{\rm r}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r},{\rm r}),a) \Bigl( R(s=({\rm r},{\rm r},{\rm r})) + \gamma V_0(s^{\prime}) \Bigr) \biggr\}\\ &= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r},{\rm r}),a) \Bigl( 1 + \gamma 0 \Bigr) \biggr\}\\ &= 1 \end{align}$
$\begin{align} \displaystyle V_{1}(s=({\rm r},{\rm b},{\rm b}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm b},{\rm b}),a) \Bigl( R(s=({\rm r},{\rm b},{\rm b})) + \gamma V_0(s^{\prime}) \Bigr) \biggr\}\\ &= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm b},{\rm b}),a) \Bigl( -1 + \gamma 0 \Bigr) \biggr\}\\ &= -1 \end{align}$
全部は書かないが，こんな感じになる．

再度同じ計算をしよう．
$i=1$ の時
$\begin{align} \displaystyle V_{2}(s=())&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=(),a) \Bigl( R(s=0) + \gamma V_1(s^{\prime}) \Bigr) \biggr\}\\ &= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=(),a) \Bigl( 0 + \gamma 0 \Bigr) \biggr\}\\ &=0 \end{align}$
上記において， $s^{\prime}$ の取り得る値は ${\rm red}$ か ${\rm blue}$ であり，その状態での報酬の期待値 $V_1(s^{\prime}=({\rm r}))=V_1(s^{\prime}=({\rm b})) =0$ なので結果は相変わらず $V_{2}(s=())=0$ である．
同様に， $V_2(s=({\rm r}))=V_2(s=({\rm b}))=0$ ， $V_2(s=({\rm r},{\rm r}))=V_2(s=({\rm r},{\rm b}))=V_2(s=({\rm b},{\rm r}))=V_2(s=({\rm b},{\rm b}))=0$ である．
値は更新されるのか不安になりつつ，今度は以下を計算してみる．
$\begin{align} \displaystyle V_{2}(s=({\rm r},{\rm b}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm b}),a) \Bigl( R(s=({\rm r},{\rm b})) + \gamma V_1(s^{\prime}) \Bigr) \biggr\}\\ &=\underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm b}),a) \Bigl( 0 + \gamma V_1(s^{\prime}) \Bigr) \biggr\}\\ &=\gamma \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm b}),a) V_1(s^{\prime}) \biggr\}\\ \end{align}$
$a={\rm red}$ の時
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm b}),a={\rm r}) V_1(s^{\prime}) \\ = T(s^{\prime}=({\rm r},{\rm b},{\rm r})|s=({\rm r},{\rm b}),a={\rm r}) V_1(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_1(s^{\prime}=({\rm r},{\rm b},{\rm b}))\\ = 0.9 V_1(s^{\prime}=({\rm r},{\rm b},{\rm r})) + 0.1 V_1(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_1(s^{\prime}) \\ = 0.9 × (-1) + 0.1 × 1\\ = -0.8$
よって， $V_{2}(s=({\rm r},{\rm b})) = \gamma × 0.8 = 0.792$

次に，
$\begin{align} \displaystyle V_{2}(s=({\rm r},{\rm r}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a) \Bigl( R(s=({\rm r},{\rm r})) + \gamma V_1(s^{\prime}) \Bigr) \biggr\}\\ &=\underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a) \Bigl( 0 + \gamma V_1(s^{\prime}) \Bigr) \biggr\}\\ &=\gamma \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a) V_1(s^{\prime}) \biggr\}\\ \end{align}$
$a={\rm red}$ の時
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a={\rm r}) V_1(s^{\prime}) \\ = T(s^{\prime}=({\rm r},{\rm r},{\rm r})|s=({\rm r},{\rm r}),a={\rm r}) V_1(s^{\prime}=({\rm r},{\rm r},{\rm r}))\\ \ {+} T(s^{\prime}=({\rm r},{\rm r},{\rm b})|s=({\rm r},{\rm r}),a={\rm r}) V_1(s^{\prime}=({\rm r},{\rm r},{\rm b}))\\ = 0.9 V_1(s^{\prime}=({\rm r},{\rm r},{\rm r})) + 0.1 V_1(s^{\prime}=({\rm r},{\rm r},{\rm b}))\\ = 0.9 × 1 + 0.1 × 1\\ = 1$
$a={\rm blue}$ の時も同様に $1$ ．
よって， $V_{2}(s=({\rm r},{\rm r})) = \gamma × 1 = 0.99$

$i=2$ の時
ここで，すでに求まっている $V(s=({\rm r},{\rm r},{\rm r}))$ はどういう値になるだろう．
$\begin{align} \displaystyle V_{3}(s=({\rm r},{\rm r},{\rm r}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r},{\rm r}),a) \Bigl( R(s=({\rm r},{\rm r},{\rm r})) + \gamma V_2(s^{\prime}) \Bigr) \biggr\}\\ &= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r},{\rm r}),a) \Bigl( 1 + \gamma 0 \Bigr) \biggr\}\\ &= 1 \end{align}$
$s=({\rm r},{\rm r},{\rm r})$ の次の状態は存在しないので， $V(s^{\prime})=0$ である．
よって何度計算をしても $V(s=({\rm r},{\rm r},{\rm r}))=1$ である．

同様に，
$\begin{align} \displaystyle V_{3}(s=({\rm r},{\rm r}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a) \Bigl( R(s=({\rm r},{\rm r})) + \gamma V_2(s^{\prime}) \Bigr) \biggr\}\\ &= \gamma \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a) V_2(s^{\prime}) \biggr\}\\ \end{align}$
$a={\rm red}$ の時
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r},{\rm r}),a={\rm r}) V_2(s^{\prime}) \\ = T(s^{\prime}=({\rm r},{\rm r},{\rm r})|s=({\rm r},{\rm r}),a={\rm r}) V_2(s^{\prime}=({\rm r},{\rm r},{\rm r}))\\ \ {+} T(s^{\prime}=({\rm r},{\rm r},{\rm b})|s=({\rm r},{\rm r}),a={\rm r}) V_2(s^{\prime}=({\rm r},{\rm r},{\rm b}))\\ = 0.9 V_2(s^{\prime}=({\rm r},{\rm r},{\rm r})) + 0.1 V_2(s^{\prime}=({\rm r},{\rm r},{\rm b}))\\ = 0.9 × 1 + 0.1 × 1\\ = 1$
$a={\rm blue}$ の時も同様．
よって， $V_{3}(s=({\rm r},{\rm r}))=\gamma × 1 = 0.99$ ．

さて，
$\begin{align} \displaystyle V_{3}(s=({\rm r}))&= \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a) \Bigl( R(s=({\rm r})) + \gamma V_2(s^{\prime}) \Bigr) \biggr\}\\ &= \gamma \underset{a}{\max} \biggl\{ \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a) V_2(s^{\prime}) \biggr\}\\ \end{align}$
$a={\rm red}$ の時
$\displaystyle \sum_{s^{\prime}} T(s^{\prime}|s=({\rm r}),a={\rm r}) V_2(s^{\prime}) \\ = T(s^{\prime}=({\rm r},{\rm r})|s=({\rm r}),a={\rm r}) V_2(s^{\prime}=({\rm r},{\rm r}))\\ \ {+} T(s^{\prime}=({\rm r},{\rm b})|s=({\rm r}),a={\rm r}) V_2(s^{\prime}=({\rm r},{\rm b}))\\ = 0.9 V_2(s^{\prime}=({\rm r},{\rm r})) + 0.1V_2(s^{\prime}=({\rm r},{\rm b}))\\ = 0.9 × 0.99 + 0.1 × 0.792\\ = 0.9702$
$a={\rm blue}$ の時は省略．
$V_{3}(s=({\rm r}))=\gamma × 0.9702 = 0.9605$ ．
こんな感じで，報酬がもらえる状態に近いところから順番に求まっていっている．