書記が数学やるだけ#804 動的計画法（方策反復法・価値反復法）

ベルマン方程式の解法としての動的計画法について，方策反復法と価値反復法を比較して示していく。

問題

今回は，どんなマップかあらかじめ知っているものとする。

説明

方策反復法では，方策の評価と方策の改善を繰り返すことで方策を最適化する。

一方で，価値反復法では事前に価値の改善を繰り返し行い，最後に方策の抽出を行うことで最適化する。

解答

方策反復法では，行動価値関数Qを最大化する方策（今回では進行方向）を決め，そのときの状態価値関数を更新する，これを各マスごとに繰り返す。

これを数式で示してみる。まず(1,2)のマスにおいて，左に進むのが最善であり，これに応じて状態価値関数が更新される。

(2,2)に移動して同様に計算。以下同様の計算を行う。

次に価値反復法について。ここでは各マスごとに価値の改善を行い，計算が収束したところで方策の抽出がまとめて行われる。

計算は以下の通りで，途中の方策の計算が省略される。

本記事のもくじはこちら：