※大人の事情で以前削除した、個人的なメモ書きの再掲です。参考になれば……
概要
MDPのベルマン方程式
V\left ( s \right ) = \min_{a} \left \{ \ell \left ( s, a \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, a \right ) V \left ( s^{\prime} \right ) \right \}
から、線形ベルマン方程式
z(s) = \exp \Bigl( - q\left ( s \right ) \Bigr) \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) z(s^{\prime})
を導出
マルコフ決定過程(MDP)
MDPにおけるベルマン方程式
通常のMDPでは
- 状態集合$S$に属する状態$s$における状態価値関数$V(s)$
- 状態$s$で行動集合Aに属する行動$a$を実行することで得るコスト$\ell (s,a)$
- 状態$s$で行動$a$を実行して次状態$s^{\prime}$に遷移する状態遷移確率$p \left ( s^{\prime} | s, a \right ) $
を用いた、次のベルマン方程式を（価値反復法などによって）解きます。
V\left ( s \right ) = \min_{a} \left \{ \ell \left ( s, a \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, a \right ) V \left ( s^{\prime} \right ) \right \}
min邪魔問題
このベルマン方程式でV(s)を計算するためには、$\min_a$、すなわち、｛｝の中身が最小となるような行動$a$を探して計算することを繰り返し行うしかない。
普通見かけるベルマン方程式は$\max$が使われていると思いますが、今回は報酬$r$の代わりにコスト$\ell$で表現していて、$\ell$は$r$の符号を反転させたもの、すなわち$\ell(s,a) = - r(s,a)$です。コストはなるべく小さくしたいので、$\min$。
線形可解マルコフ決定過程(LMDP)
線形可解マルコフ決定過程( Linearly-solvable MDP; LMDP) とは、エマヌエル・トドロフ（アメリカ）によって提案されたマルコフ決定過程の亜種です。別名を**カルバック・ライブラー制御(KL制御)**ともいいます。以下、主にトドロフの論文(PDF)に従う形で解説します。
行動aから制御uへ
まず、行動$a$を、制御$\mathbf{u}$というベクトルで置き換えます。行動$a$が「上・下・左・右」のような抽象的な概念だったのに対し、このベクトルは、$\mathbf{u} \in \mathbb{R}^{|S|}$、状態sの数の大きさを持つ、実数値のベクトルです。状態$s$における$\mathbf{u}$である$\mathbf{u}_s$を
\mathbf{u}_s = u(s^{\prime}|s)
として定義します。$\mathbf{u}_s$は全状態$s$の数だけあるベクトルです。例えば、$3 \times 3$のグリッドワールドなら9個の要素を持ちます。
2つの仮定
LMDPでは、2つの大きな仮定を置きます。
1.状態遷移確率の定義
MDPで、
- 状態遷移確率$p \left ( s^{\prime} | s, a \right ) $
を定義しましたが、LMDPでは「行動$a$」$\rightarrow$「状態$s$についての制御$\mathbf{u}_s$」に変えた、
- 状態遷移確率$p ( s^{\prime} | s, \mathbf{u}_s ) $
を、次の式で定義します。
p\left ( s^{\prime} | s, \mathbf{u}_s \right ) = \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right )
ここで、$\bar{p}$は、「uncontrolled probability」（非制御遷移確率）とか「passive dynamics」（受動ダイナミクス）とか呼ばれる**「制御をしないときの、もともとの状態遷移確率」**です。LMDPでは、状態遷移確率を、「もともとの遷移確率が、制御を実行することで変化したもの」と捉えるのです。
もちろん、もともと遷移しない組み合わせ、すなわち$ \bar{p}\left ( s^{\prime} | s \right )=0$ならば$p\left ( s^{\prime} | s, \mathbf{u}_s \right ) =0$です。
2. コスト関数の定義
LMDPでは、コスト関数$\ell(s,\mathbf{u}_s)$を、次の式で定義します。
\ell \left ( s, \mathbf{u}_s \right ) = q\left ( s \right ) + D_{\rm{KL}} \Bigl ( p\left ( s^{\prime} | s, \mathbf{u}_s \right ) \Bigl|\Bigr| \bar{p}\left ( s^{\prime} | s \right ) \Bigr )
第一項の$q(s)$は、制御によらず、ある状態に到達した時点で受け取る状態そのもののコストで、「状態依存のコスト」といいます。
第二項は、制御の入った遷移確率$p$と、制御が入っていないときの遷移確率$\bar{p}$のカルバック・ライブラーダイバージェンスです。つまり、$p$と$\bar{p}$の確率分布の差を表しており、制御によって大きく変えられるほど、この項の数値は大きくなります。無茶な遷移をしようとするほど大きくなるので、そういう遷移を選択しないようにする効果があるようです。
カルバック・ライブラーダイバージェンスの定義
D _ { \mathrm { KL } } ( P \| Q ) = \sum _ { i } P ( i ) \log \frac { P ( i ) } { Q ( i ) }
から
\ell \left ( s, \mathbf{u}_s \right ) = q\left ( s \right ) + \sum_{s^{\prime}: \bar{p}(s^{\prime}|s) \neq 0} p \left ( s^{\prime} | s, \mathbf{u}_s \right ) \log \frac{p \left ( s^{\prime} | s, \mathbf{u}_s \right )}{\bar{p}(s^{\prime}|s)}
となります。
ここで、状態遷移確率の定義
p\left ( s^{\prime} | s, \mathbf{u}_s \right ) = \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right )
から、式変形して両辺のlogをとると
\mathbf{u}_s = \log \frac{ p\left ( s^{\prime} | s, \mathbf{u}_s \right ) }{ \bar{p}\left ( s^{\prime} | s \right ) }
となるので、これをコスト関数の定義の式に代入すると、
\ell \left ( s, \mathbf{u}_s \right ) = q\left ( s \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, \mathbf{u}_s \right ) \mathbf{u}_s
と変形できます。
打倒min ～minが邪魔なら中身を予めminしてしまえ～
さて、冒頭のベルマン方程式
V\left ( s \right ) = \min_{a} \left \{ \ell \left ( s, a \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, a \right ) V \left ( s^{\prime} \right ) \right \}
を、行動$a$を制御$\mathbf{u}_s$にした上で、先程の定義
\begin{align}
p\left ( s^{\prime} | s, \mathbf{u}_s \right ) &= \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \\
\ell \left ( s, \mathbf{u}_s \right ) &= q\left ( s \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, \mathbf{u}_s \right ) \mathbf{u}_s
\end{align}
を代入すると、
\begin{align}
V\left ( s \right ) &=& \min_{\mathbf{u}_s} \left \{ q\left ( s \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, \mathbf{u}_s \right ) \mathbf{u}_s + \sum_{s^{\prime}} p \left ( s^{\prime} | s, \mathbf{u}_s \right ) V \left ( s^{\prime} \right ) \right \} \nonumber \\
&=& \min_{\mathbf{u}_s} \left \{ q\left ( s \right ) + \sum_{s^{\prime}} p \left ( s^{\prime} | s, \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr) \right \} \nonumber \\
&=& \min_{\mathbf{u}_s} \left \{ q\left ( s \right ) + \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr) \right \}
\end{align}
のように変形できます。
ここで、例の邪魔な$\min$の中身を見てみると、$q(s)$は制御に関係ないのでスルーでき、後半の
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr)
を、$u$について最小化していることになります。これを数学的に最小化してしまえばいいじゃないか！
ラグランジュの未定乗数法による攻略
ここで、極値の候補を求めることができる「ラグランジュの未定乗数法」を用います。
まず、極値をみつけたい関数$f(x)$と制約条件$g(x)$で、ラグランジュ関数$L$をつくります。
L(x, \lambda) = f(x) - \lambda g(x)
このとき、Lのxについての偏微分と、Lのλについての偏微分がともに「0」になるような、つまり
\frac{\partial L}{\partial x} = 0 \\
\frac{\partial L}{\partial \lambda} = 0
となる$x$が極値の候補なのです。
今回、$f(x)$にあたるのが
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr)
です。
また、制約条件$g(x)$には、状態遷移確率$p$は確率なので、全部足すと1になること、つまり
\sum_{s^{\prime}} p\left ( s^{\prime} | s, \mathbf{u}_s \right ) =1
を、状態遷移確率の定義から変形して
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) = 1
として用います（式に代入するときは=0の形にします）。
こうして、次のラグランジュ関数を作り出すことができます。
\mathcal{L} \Bigl( \mathbf{u}_s, \lambda_s \Bigr)= \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr) + \lambda_s \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) - 1 \Bigr)
これを解きましょう！
ラグランジュ関数の偏微分を求めよう
uについての偏微分
\frac{\partial \mathcal{L}}{\partial \mathbf{u}_s} = \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr)
$\bar{p} (s^{\prime}|s) \neq 0$のとき，$\frac{\partial \mathcal{L}}{\partial \mathbf{u}_s}=0$を満たす唯一の解は
\mathbf{u}_s + V(s^{\prime})+\lambda_s + 1 = 0
であり，ゆえに
\mathbf{u}_s = - V(s^{\prime}) - \lambda_s - 1
です。
このときの$\mathbf{u}_s=\mathbf{u}^{*}_s$とします。
$\bar{p} (s^{\prime}|s) > 0$かつ
\exp \left ( \mathbf{u}^{*}_s \right ) > 0
なので、二階偏導関数は
\left. \frac{ {\partial}^2 \mathcal{L} } {\partial \mathbf{u}_s \partial \mathbf{u}_s} \right|_{\mathbf{u}_s = \mathbf{u}^{*}_s} = \bar{p}(s^{\prime}|s) \exp \left ( \mathbf{u}^{*}_s \right ) > 0
となります。つまり、$\mathbf{u}^{*}_s$において極小なのです！
λについての偏微分
次に、$\lambda_s$についての偏微分を求めましょう。
\frac{\partial \mathcal{L}}{\partial \lambda_s}=\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) - 1=0
なので、uについての偏微分の項目で求めた式を変形して
\begin{align}
&\mathbf{u}_s + V(s^{\prime})+\lambda_s + 1 = 0 \\
&\mathbf{u}_s = - V(s^{\prime})-\lambda_s - 1
\end{align}
として、先程のλについての式に代入してあげると、
\begin{align}
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) - \lambda_s - 1 \right \} - 1 &= 0 \nonumber \\
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \exp ( - \lambda_s - 1 ) &= 1 \nonumber \\
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} &= \exp ( \lambda_s + 1 ) \\
\log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr) &= \lambda_s + 1 \\
\lambda_s &= \log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr) - 1
\end{align}
と、$\lambda_s$が求まります。
これを、$\mathbf{u}^{*}_s$の式
\mathbf{u}^{*}_s = - V(s^{\prime})-\lambda_s - 1
に代入してあげると、
\mathbf{u}^{*}_s = - V(s^{\prime}) - \log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr)
を得ます。
線形ベルマン方程式の導出
min邪魔問題の突破
最小化したかったのは、
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) \Bigl( \mathbf{u}_s + V \left ( s^{\prime} \right ) \Bigr)
でしたね。$\mathbf{u}^{*}_s$のとき、この項は
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}^{*}_s \right ) \Bigl( \mathbf{u}^{*}_s + V \left ( s^{\prime} \right ) \Bigr) \nonumber
となります。
このとき、$\mathbf{u}^{*}_s$で極小なので、例のベルマン方程式
V\left ( s \right ) =\min_{\mathbf{u}^{*}_s} \left \{ q\left ( s \right ) + \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}^{*}_s \right ) \Bigl( \mathbf{u}^{*}_s + V \left ( s^{\prime} \right ) \Bigr) \right \}
のうち、$\min$の中身を考えると、
- 第1項はそもそも「状態依存のコスト」なので$\mathbf{u}^{*}_s$に関係ない
- 第2項はラグランジュの未定乗数法で極小値であるとわかった
ので、$\mathbf{u}^{*}_s$のとき最小になります。
つまりminを外せます！！
V(s) = q\left ( s \right ) + \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}^{*}_s \right ) \Bigl( \mathbf{u}^{*}_s + V \left ( s^{\prime} \right ) \Bigr)
min邪魔問題を突破しました。
線形ベルマン方程式への変形
さて、後少しです。ラグランジュの未定乗数法の制約条件に使った
\begin{align}
\sum_{s^{\prime}} p\left ( s^{\prime} | s, \mathbf{u}_s \right ) &=1 \\
\sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left ( \mathbf{u}_s \right ) &= 1
\end{align}
を先程の式に入れると
V(s) = q\left ( s \right ) + \Bigl( \mathbf{u}^{*}_s + V \left ( s^{\prime} \right ) \Bigr)
ラグランジュの未定乗数法で求めた
\mathbf{u}^{*}_s = - V(s^{\prime}) - \log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr)
を代入して
\begin{align}
V(s) &= q\left ( s \right ) + \Bigl( \mathbf{u}^{*}_s + V \left ( s^{\prime} \right ) \Bigr) \\
&= q\left ( s \right ) + \Bigl( - V(s^{\prime}) - \log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr) + V \left ( s^{\prime} \right ) \Bigr) \\
&= q\left ( s \right ) - \log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr)
\end{align}
最後に、両辺の指数をとって
\begin{align}
\exp \left ( - V(s) \right ) &= \exp \Bigl( - q\left ( s \right ) + \log \Bigl( \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \} \Bigr) \Bigr) \\
\exp \left ( - V(s) \right ) &= \exp \Bigl( - q\left ( s \right ) \Bigr) \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) \exp \left \{ - V(s^{\prime}) \right \}
\end{align}
ここで、$\exp \left ( - V(s) \right )$を、$z(s)$に置き換えた
z(s) = \exp \Bigl( - q\left ( s \right ) \Bigr) \sum_{s^{\prime}} \bar{p}\left ( s^{\prime} | s \right ) z(s^{\prime})
を、線形ベルマン方程式と呼びます。
$z(s)$を、desirability functionといい、日本語だと「好適度関数」などと訳されます。これは、今回$V(s)$がコスト（なるべく減らしたい）の期待値になっているので、この符号を反転させている$z(s)$は、増えれば増えるほどよい値となるためです。
さて、この線形ベルマン方程式を行列の形に書き換えてみましょう。
- $\mathbf{G}$ : 状態数$\times$状態数の対角行列、対角成分$G(i,i)=\exp ( -q(i) )$
- $\mathbf{\bar{P}}$ : 状態数$\times$状態数の行列、$\bar{P}(i,j)=\bar{p}(j|i)$
- $\mathbf{Z}$ : 状態数の大きさのベクトル、$Z(i)=z(i)$
を定義したとき、線形ベルマン方程式は
\mathbf{Z} = \mathbf{G} \mathbf{\bar{P}} \mathbf{Z}
という式になります。
つまり、状態依存のコスト$q(s)$と、もともとの遷移確率$\bar{p}(s^{\prime}|s)$が予めわかっているなら、上の式で固有値$\mathbf{Z}$を求めれば良いだけです！
ちなみに、状態価値が知りたければ、$z(s)$を求めれば、$V(s)=-\log(z(s))$で計算できます。
なお、自分がよく理解できていないだけかもしれませんが、トドロフの論文では、固有値計算にべき乗法を紹介しています。どうやら固有値zは絶対値が最も大きな固有値のようです。
べき乗法を使うやり方では、k=0,1,2,......のとき$\mathbf{Z}_0 = 1$（全要素が1）として、
\mathbf{Z}_{k+1} = \mathbf{G} \mathbf{\bar{P}} \mathbf{Z}_{k}
を、$\mathbf{Z}_k$が収束するまで計算すればよいです。
最適状態遷移確率
$z(s)$が計算できれば、最適な状態遷移確率$p^{*}$は次の式で求められます。
p^{*} \left(s^{\prime} | s \right )= \frac{ \bar{p} \left ( s^{\prime}|s \right ) z(s^{\prime}) }{ \sum_{s^{\prime}} \bar{p} \left ( s^{\prime}|s \right ) z(s^{\prime}) }
MDPでいうところの最適方策$\pi^{*}$ですね。これで状態$s$における遷移先$s^{\prime}$を（確率的に）選択してやればよいわけです。結局$\mathbf{u}_s$は式変形以外に使わなくてよいのですね。
参考文献
原論文はこちらです。
勉強する際に特に参考にしたもの。
・松原崇充(2015)「確率最適制御の最近の動向一確率推論による解法」システム／制御／情報・Vol．59 No．10 pp．369−374
・内部英治(2016)「線形可解マルコフ決定過程を用いた順・逆強化学習」日本神経回路学会誌・23巻1号
・鹿島久嗣(2007)「Linearly-solvable Markov decision problems / Emanuel Todorov (UCSD)」(ppt) 機械学習研究グループ T-PRIMAL