適格度トレース

迷路問題で普通のSarsaアルゴリズムと適格度トレースという技法を使った Sarsa(λ) アルゴリズムで学習収束速度を比較した。数値をぱっと見たところ後者の方が桁違いに速いことが確認できた。ちょっと改良するだけでこんなに違いが出るなんてすごいと思った。

と思っていたけど、やっぱりすごくないかも。確かに学習収束までの「学習回数」は劇的に短くなるが、１回の学習に要する「計算量」が劇的に多くなるので、結果的に適格度トレースを使うと計算時間がより多くかかるという結果になった。全然改良になってない。プログラムが下手だからか。何か勘違いしているのか。

追記

よく読んだら書いてあった。

適格度トレースを用いた手法は１ステップ手法に比べると計算量が多くなるが、その代わり、学習速度はかなり速くなる。（中略）したがって、オンラインのアプリケーションの場合のように、データ量が少なくて処理を繰り返すことが出来ない場合に適格度トレースを使うことは意味がある。他方、オフラインアプリケーションのように、（高価ではない）シミュレーション等によってデータを容易に生成できる場合には、適格度トレースを使っても見合わない。
強化学習（p.206）

上の学習速度っていうのは、学習収束「時間」じゃなくて、学習収束までの「回数」のことらしい。そう捉えれば、全ての意味が通る。得られるデータが少なければ、少しの学習回数で収束させなければいけないので、計算量が多いが適格度トレースを使ったほうがよい。データが山ほど生成できれば、学習回数は多くてもよいので、計算量が少ない方を取ったほうがいい。

本を読んでるだけじゃ、あまり注目していなかったところだけど、実際にやってみると、すごく納得できる。

また、結果をグラフで表示したかったが書き方がよくわからない。たしか、gnuplotっていうのが使えると思ったが、Cプログラムとどう連結すればよいのだろう。調べてみる。