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

昨日の続き。

今日はどうやってBellman方程式を解いていくのかを考えていく。

方策評価

昨日言及した通り、ある方策 $\pi$ の元でBellman方程式を解くと、その方策での状態価値（あるいは行動価値）が計算できる。
なので、Bellman方程式を解くことを方策評価と呼んだりする。

Bellman方程式は連立一次方程式なので、解き方はいろいろあるのだけれど、本では反復解法が用いられている。
これは、後々で方策改善と組み合わせるときに、都合がよかったりするから。

なお、反復解法を用いる場合、問題によっては答えが収束せずに発散してしまうこともあるので、本当は収束条件を満たしているかをチェックしないといけないんだけれど、本では「収束することが一般的に示されている」の一言のみ・・・
まぁ、ここは本を信じるということで。
詳細をちゃんと確認したい場合、「ヤコビ法収束条件」などでググると、情報が出てくる。
（ググってみると、収束の十分条件として「係数行列が対角優位であること」が挙げられている。Bellman方程式の場合、右辺の変数の係数はどれも確率や割引率を掛けたものなので、この十分条件を満たすことが分かる）

反復解法で解く場合、各反復で得られる解を $\boldsymbol{V}^{(0)}, \boldsymbol{V}^{(1)}, \cdots$ で表すことにして、 $\boldsymbol{V}^{(k+1)}$ を $\boldsymbol{V}^{(k)}$ で次のように更新する。

なお、この更新式だと、 $\boldsymbol{V}^{(k+1)}$ を得るために $\boldsymbol{V}^{(k)}$ の値を丸々取っておく必要があるけれど、すでに更新された $V^{(k+1)}_{s'}$ の値を使ってもいいことが知られている。（ガウス＝ザイデル法）
この場合、解を取っておくための配列は1つで済むので、メモリ的にもお得だし、普通は配列を2つ使うよりも速く収束する。

$k \rightarrow \infty$ とすることで $\boldsymbol{V}^{(k)} \rightarrow \boldsymbol{V}^{\pi}$ に収束するけど、無限に繰り返すのは無理なので、更新の幅が十分に小さくなったら終了するといい。

疑似コードで書くと、以下の通り。

すべての $s \in \mathcal{S}$ に対して、 $V_s \leftarrow 0$ とする。
以下を繰り返す：
1. $\Delta \leftarrow 0$
2. 各について：
  1. $v \leftarrow V_s$
  2. $V_s \leftarrow \sum_{a \in \mathcal{A}(s)} \pi(s, a) \left( \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \left( \mathcal{R}^a_{ss'} + \gamma V_{s'} \right) \right)$
  3. $\Delta \leftarrow \mbox{max} \left\{ \Delta, \left| V_s - v \right| \right\}$
3. $\Delta \lt \varepsilon$ （ $\varepsilon$ は十分小さい正の定数）なら、繰り返しを終了。