Ch_6 Temporal-Difference Learning｜『Reinforcement Learning(by Sutton)』を読み解く #1

f:id:lib-arts:20191102182327p:plain

強化学習に関しては概要の確認やDeep Q Network関連を中心とした論文の解説や実装の確認などをこれまで行ってきましたが、ベースの知識の再整理ということで『Reinforcement Learning(by Sutton)』をまとめていければと思います。

https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf

こちらのpdfは英語で書かれているものの、情報が豊富かつ非常にわかりやすく記述されているので、概要をつかんだ後に確認するにはちょうど良いと思われます。
#1ではDeep Q-NetworkのLossのベースにもなっている、第6章のTemporal-Difference Learningについて取り扱います。（概要を掴むのが目的のため、全てのSectionは取り扱いません。あくまで読解メモとして参考にしていただき、詳細はpdfファイルをご確認いただけたらと思います。）

1. Temporal-Difference Learning(Chapter6)
1-1. TD Prediction(Section6.1)
1-2. Advantages of TD Prediction Methods(Section6.2)
1-3. Sarsa: On-policy TD Control(Section6.4)
1-4. Q-learning: Offpolicy TD Control(Section6.5)
2. まとめ

1. Temporal-Difference Learning(Chapter6)
Chapter6の冒頭で"temporal-difference (TD) learning"の概要について触れられています。

f:id:lib-arts:20191102183040p:plain

上記で色をつけた部分では、強化学習における中心的(central)かつ新規的(novel)なアイデアとしてTD Learningが紹介されています。TD learningは"Monte Carlo ideas"と動的計画法(DP; Dynamic Programming)の組み合わせであるとされています。ここで注意なのが、Section6.1で出てくるMonte Carlo methodとここでのMonte Carlo ideaは区別して考えるべきであるということです。それぞれの違いとしては、Monte Carlo ideaが環境のモデルなしで経験から直接的に学習する(learn directly from raw experience without a model of the environment's dynamics)ことを表しているのに対し、Monte Carlo methodではこの考え方をベースに、数式(6.1)のようにEpisodeが終わってから学習するというニュアンスも足されているということです。
解釈としては、Monte Carloというのは元々乱数生成に関する話で用いられており(Monte Carlo Sampling)、環境のモデルを元に解くのではなく、経験のサンプルを通して近似的に解くというニュアンスで用いられると考えるのが良いのではと思われます。従ってMonte Carlo methodは狭義、Monte Carlo ideaは広義の意味で用いられていると考えておくのが良さそうです。
また、DPは1ステップずつ帰納的に解いていくというイメージのため、Monte Carlo methodは違い、経験から学習はするものの、episodeではなく、step単位で学習していると整理しておくと良いと思います。詳細についてはこの後の1-1節で取り扱います。

1-1. TD Prediction(Section6.1)
1-1節ではSection6.1のTD Predictionについてまとめます。

f:id:lib-arts:20191102184508p:plain

f:id:lib-arts:20191102184523p:plain

違いとしては基本的には上記の(6.1)式と(6.2)式を考えていくと良いです。それぞれ、(6.1)式がMonte Carlo Method、(6.2)式がTemporal-Difference Learningを表しています。それぞれの解釈としては、(6.1)式が $G_{t}$ を将来の報酬和と考えているのに対して、(6.2)式では $R_{t+1}+\gamma V(S_{t+1})$ を将来の報酬和と考えています。

f:id:lib-arts:20191102185142p:plain

(6.2)式のTemporal-Difference Learningについて考えていくと、上記のようにTD errorが導出されます。(6.5)式のTD errorをベースにDeep Q Network系(Rainbowなども含む)の学習が行われています。学習にあたっては単純に2乗誤差として用いることもできますが、外れ値(outlier)の影響を受けにくくするためにHuber Lossなどを用いることの方が多いのではという印象です。

f:id:lib-arts:20191102191339p:plain

また、上記で書かれているように、Monte Carlo errorがTD errorsの和で表現されるのも抑えておくと良いです。将来の報酬和を用いてVを考える以上、この辺に関連が出てくるのは納得の内容ではと思います。

1-2. Advantages of TD Prediction Methods(Section6.2)
Section6-2ではTD Prediction Methodsの利点についてまとめられています。

f:id:lib-arts:20191102192246p:plain

上記のようにTD methodsは環境モデルをベースにDPで解くのに比べて、環境のモデルを必要としない利点があるとされています。また、Monte Carlo Methodsと比べた際の利点としては、学習を行うにあたってepisodeの終わりまで待たなくて良いとされています。収束性についても議論されていますが、問題ないとされています。

1-3. Sarsa: On-policy TD Control(Section6.4)
Section6.4ではOn-policyの例としてSarsaについてまとめられています。

f:id:lib-arts:20191102193105p:plain

まずは大枠から見ていきますが、Sarsaは上記のようにaction-value functionとしてQを導入しています。action-value functionは引数として状態の $S_{t}$ のみを扱うstate-value functionとは異なり、状態の $S_{t}$ と行動の $A_{t}$ の二つを引数として取り扱います。(6.7)をstate-value functionと同様に考えていくと、TD errorとして下記が導出できます。
$\delta_{t}=R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_{t},A_{t})$
1-1節ではVを用いましたがQに変わっており、Deep Q NetworkのLossの数式にだんだん近づいてきたことがわかります。が、ここで $Q(S_{t+1},A_{t+1})$ の取り扱いが方策(policy)に従うとされているために、若干わかりづらくなっています。この点を変更したのが、1-4で取り扱うOff-PolicyのアルゴリズムであるQ-learningです(SarsaのようなアルゴリズムをOn-Policy、Q-learningのようなアルゴリズムをOff-Policyと呼んでおり、この二つの用語はよく出てくるので抑えておくと良いです)。

1-4. Q-learning: Offpolicy TD Control(Section6.5)
1-4節ではSection6.5のQ-learningについて見ていきます。

f:id:lib-arts:20191102194227p:plain
Q-learningは上記のように処理が記述されています。1ステップ先のQ関数をmaxを用いて表現することで、処理の簡略化を行なっています。Deep Q NetworkではこのQ-learningがベースとして用いられているので、抑えておきたいところです。