ベルマン方程式
マルコフ決定過程(MDP) において、ベルマン方程式は期待報酬(expected reward)に関する再帰的な関係を表現する。例えば、特定の状態 s {\displaystyle s} において方策 π {\displaystyle \pi } を適用した際の期待報酬は以下のベルマン方程式を満たす:
V π ( s ) = R ( s , π ( s ) ) + γ ∑ s ′ P ( s ′ | s , π ( s ) ) V π ( s ′ ) . {\displaystyle V^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s'}P(s'|s,\pi (s))V^{\pi }(s').\ }
この方程式は、ある方策 π {\displaystyle \pi } のもとで得られる期待報酬を表している。
最適な方策を採用した場合の方程式が最適ベルマン方程式である:
V ∗ ( s ) = max a { R ( s , a ) + γ ∑ s ′ P ( s ′ | s , a ) V ∗ ( s ′ ) } . {\displaystyle V^{*}(s)=\max _{a}{\Big \{}R(s,a)+\gamma \sum _{s'}P(s'|s,a)V^{*}(s'){\Big \}}.}
この式は、最適な行動をとった場合に得られる期待報酬を表す。
}
これがベルマン方程式である。時間に関する添え字を省略し、次の状態を代入することにより、式をより単純化できる。
V ( x ) = max a ∈ Γ ( x ) { F ( x , a ) + β V ( T ( x , a ) ) } . {\displaystyle V(x)=\max _{a\in \Gamma (x)}\{F(x,a)+\beta V(T(x,a))\}.}
ベルマン方程式を解くことは、未知の関数 V ( x ) {\displaystyle V(x)} (価値関数)を見出すことである。ゆえにベルマン方程式は汎関数方程式に属している。価値関数は目的の実現可能な最良値を状態 x {\displaystyle x} の関数として表していることを思い出そう。価値関数を計算することによって、同時に我々は最適なアクションを状態の関数 a ( x ) {\displaystyle a(x)} として得ることができる。これを方策関数(policy function)と呼ぶ。