ベルマン方程式は、動的計画法（動的な最適化問題）の最適性の必要条件を表す方程式らしい。必要条件は、再帰を使って部分を解くことで全体が解ける状態にあることと、メモ化を使うことです。最適化問題とは、集合内のすべての数値を、ある関数にいれたときに最小あるいは最大となる集合内の元を探すことを目的とする問題のことです。
動的計画法において、問題の目的を数式で表したものを目的関数といいます。
xは状態です。aは行動です。tは時間です。βは割引率です。F(x, a)は、状態xのときに行動aをとることで得られる報酬が出力される関数です。この式は、報酬を最大化させることが目的になっています。割引率は0 < β < 1で、0であればどの時間tに得られた報酬も同じ重さで扱います。1に近ければ未来のtで得られた報酬程重要視します。t100のときの報酬は、βの100乗が掛けられるからです。
この式は再帰可能な形態に変形できます。まず下記のようにします。
最初のx0のときの報酬だけ左に出しました。βも一つ左に出すことで、右の式はt0がt1になっただけで、あとは上記の式とまったく同じです。よって下記のように書けます。
これを下記のように簡単に書いたのが、ベルマン方程式だそうです。
なぜ、上の式のx1が、下ではT(x, a)に変わっているかというと、T(x, a)は、状態xのときに、行動aをとった場合に次に遷移する状態を返す関数として定義しているからです。変数の添え字を消したかったのでこれを使っています。
