強化学習について学んでみた。（その11）

昨日は方策評価について説明した。

今日は、評価された状態価値を使って、方策を改善していくことを考えていく。

方策改善

さて、方策評価が出来たのなら、今度はその方策を変えることで、状態価値（や行動価値）を改善していきたいとなる。
これを、方策改善と呼ぶ。

なお、方策や状態価値を改善するためには、そもそも方策や状態価値の大小関係を定義しておかないといけない。

まず、状態価値はベクトルなので、その大小関係を次のように定義する。

そして、これを使って、方策の大小関係を次のように定義する。

特に、この大小関係で最大となる、最適方策 $\pi^{\ast}$ 、最適状態価値ベクトル $\boldsymbol{V}^{\ast}$ を、次のように定義する。

なお、こうして定めた大小関係は全順序ではなく半順序なので、実際のところ、（有界であれば）極大元の存在は言えるけれど、最大元が存在するということまでは言えない。
本ではこの辺りの議論が全然されてなくてかなり怪しいのだけれど、おそらく大丈夫なんだと思う・・・
（Bellman方程式は、 $\pi$ を固定すれば $\boldsymbol{V}^{\pi}$ に関する連立一次方程式だけど、 $\pi$ も変数と考えれば、（目的関数の定式化がちょっとよく分からないけど）2次計画問題になるはずなので、最適解が存在するのだと思う・・・）

さて、こうして方策の大小関係を定義した上で、どうやって方策を改善させるのかを考えてみる。

まず、状態価値と行動価値の間には、定義から次のような関係がある。

この式をみたとき、方針 $\pi$ が確率であったことを考えると、

であるから、 $Q^{\pi}_{s, a}$ を最大にするような行動 $a$ を行う確率を1にした方が、状態価値をより大きくなると考えられることが分かる。

そこで、新たな方策 $\pi'$ として、次のような方策を考えてみる。

このような方策を、グリーディ方策と呼ぶ。

このとき、証明は省略するが、方策改善定理というものが証明されていて、それにより $\pi' \ge \pi$ が成り立つことが言えるらしい。
（というか、本の説明は証明になっていない。本の説明だと $V^{\pi}_{s} \le \sum_a \pi'(s, a) Q^{\pi}_{s, a}$ までは言えるけれど、 $V^{\pi}_{s} \le \sum_a \pi'(s, a) Q^{\pi'}_{s, a} (= V^{\pi'}_{s})$ というところまでは、論理の飛躍があって言えない）

このことを使って、次のように方策を改善することが出来る。

$updated \leftarrow \mbox{false}$
各について：
1. $old \leftarrow \pi(s)$
2. $\pi(s) \leftarrow \mathop{\mbox{arg max}}_{a \in \mathcal{A}(s)} \sum_{s' \in \mathcal{S}} \mathcal{P}^{a}_{ss'} \left( \mathcal{R}^{a}_{ss'} + \gamma V_{s'} \right)$
3. $old \neq \pi(s)$ なら、 $updated \leftarrow \mbox{true}$
$updated$ を戻り値として返す。
（これがtrueなら方策が改善されたことを意味し、そうでなければ方策が改善されなかった（＝方策は最適方策）ことを意味する）

なお、 $\pi(s)$ は、 $\pi(s, a) = 1$ となるような行動 $a$ を返す関数とする。
また、上のアルゴリズムでは、行動価値と状態価値の間に $Q^{\pi}_{s, a} = \sum_{s' \in \mathcal{S}} \mathcal{P}^{a}_{ss'} \left( \mathcal{R}^{a}_{ss'} + \gamma V^{\pi}_{s'} \right)$ という関係があることを利用している。
（この関係は、定義から出てくる）