policy evaluation

ポリシー \(\pi\)が決まると価値関数\(v_{\pi}\)が決まる。 この\(v_{\pi}\)をどうやって計算するか。

定義から書き下すと

\[v_{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a) \left( r + \gamma v_{\pi}(s')\right)\]

となるが、これは、式の数と変数の数が状態数であるような連立一次方程式。真面目に解くのは大変だが、 適当な初期値から始めて収束するまで1つずつ更新するようなアルゴリズムの収束が良いことが知られている。

policy iteration

ポリシー \(\pi\)が決まると価値関数\(\v_{\pi}\)が決まる。 で、価値関数\(\v_{\pi}\)が決まると、「各状態で最善のアクションを選ぶ」という方針で新しいポリシーを作れる。 このポリシーは、元のポリシーよりも良くなっていることが示せる。 これを繰り返すと、原理的には、最良のポリシーを得ることができる。 ただし、状態x行動 → 報酬という関数がメモリに乗るくらい小さい問題に対しては。