Ch_8 Planning and Learning with Tabular Methods③｜『Reinforcement Learning(by Sutton)』を読み解く #5
強化学習に関しては概要の確認やDeep Q Network関連を中心とした論文の解説や実装の確認などをこれまで行ってきましたが、ベースの知識の再整理ということで『Reinforcement Learning(by Sutton)』をまとめていきます。
https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf
こちらのpdfは英語で書かれているものの、情報が豊富かつ非常にわかりやすく記述されているので、概要をつかんだ後に確認するにはちょうど良いです。
#4では第8章のPlanning and Learning with Tabular Methodsの第二回としてSection8.2〜Section8.3について取り扱いました。
#5では第8章のPlanning and Learning with Tabular Methodsの第三回としてSection8.4〜Section8.5について取り扱います。
以下目次になります。
1. Prioritized Sweeping(Section8.4)
2. Expected vs. Sample Updates(Section8.5)
3. まとめ
1. Prioritized Sweeping(Section8.4)
Section8.4では学習に使用する経験の優先度付けをするにあたって、Prioritized Sweepingについて紹介されています。
第一パラグラフの冒頭では、Dyna agentにおけるsimulated transitionsは過去の経験状態と行動のペア(state-action pairs)からランダムに開始されるとありますが、これは大抵の場合において最善ではないとされています。もしsimulated transitionsやupdateが特定のstate-action pairsに集中していたらプランニングはより効率的になるとされています。
第二パラグラフでは、計算リソースをより効率的に利用するにあたって、迷路(maze)のゴール(goal states)から逆算する(backword)のが良さそうだとされています。さらにこの時にゴールだけに着目するのではなく、ゴールはあくまでも一つの例と捉え、より一般的には価値を変える任意の状態に着目するのが良いとされています。
上記はPrioritized sweepingの擬似コードですが、ステップ(e)においてTD誤差と同様の計算を行い、その値に基づいて一連のプロセスが実施されていることが確認できます。
また、Example8.4では迷路(Maze)の問題におけるPrioritized sweepingの導入にあたって、通常のDyna-Qよりも最適解にたどり着くのが早くなっているということが確認できます。ざっくり把握するなら同じ問題の複雑さにおいて(grid sizeは迷路においては問題の複雑さと読み替えて良さそうです)縦軸は指数関数のため、目盛が1単位分差があると10倍、2単位差があると100倍の計算コストの削減になると意識して右の図表を確認すると良いと思います。
Prioritized sweepingについては概ねつかめたので1節はここまでとします。
2. Expected vs. Sample Updates(Section8.5)
Section8.5ではExpected UpdatesとSample Updatesの対比について取り扱われています。
第一パラグラフでは、これまでのSectionではlearningとplanningの組み合わせの可能性についてのアイデアについて述べられてきたことを受けて、Chapter8の残りのSectionでは関連するアイデアを分析するとされています。Section8.5ではそのスタートとしてexpected updateとsample updatesの比較について確認していくとなっています。
第二パラグラフでは、one-stepのupdateに着目した際に三つの二値の次元(dimension)があり、それらが8つの状況(eight cases)を生み出しているとされています。最初の二つの次元はFigure8.6の一番左の列の4つの項目を生じさせています。価値関数として状態価値のvを用いるか状態行動価値のqを用いるかの違いと、で表された将来ステップの近似に方策を用いるか*で表された将来ステップの近似に予測値を使用するかかの違いが二つの軸とされています。三つ目の軸としてはDPのようなExpected updateを用いるかone-step TDのようにSample updateを用いるかであるとされています。
大体のイメージはつかめたので2節はここまでとします。
3. まとめ
#5ではChapter8のPlanning and Learning with Tabular Methodsの第三回として、Section8.4のPrioritized Sweepingから、Section8.5のExpected vs. Sample Updatesまでを取り扱いました。
Section8の内容は概ね確認ができたので、#6ではSection3について取り扱っていきます。
