『速習強化学習』について

原著は"[Algorithms for Reinforcement Learning] (https://sites.ualberta.ca/~szepesva/RLBook.html)" (Szepesvári 2010)
勉強会コミュニティ「RL-Tokyo」で「水曜勉強会」の教科書として3周に渡って原著の輪講が行われており、そちらでの輪講資料をもとに邦訳として『速習強化学習』が2017/9/21に共立出版から刊行された
輪講資料は一部「RL-Tokyo」の活動履歴から参照することができる
また"[Algorithms for Reinforcement Learning] (https://sites.ualberta.ca/~szepesva/RLBook.html)"の公式Webサイトからは[最新のPDF版](https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf)、および本書に基づいたAAAI-2010でのチュートリアル資料（[Part 1](http://old.sztaki.hu/~szcsaba/research/AAAI10_Tutorial/tutorial01-slidesonly.pdf) 2 3 4）を参照することができる

『速習強化学習』の所感

強化学習の教科書といえばSutton & Barto : "Reinforcement learning: An introduction"（邦訳『強化学習』森北出版 2000）なのだが、邦訳本は1998年の第1版を基にしたものしかなく、その後20年間日本語で読めるめぼしい本はなかった（現在、英語の原著では第2版が準備中で、最新版ドラフト（本記事執筆時点で2018年1月版）が全文PDFで読める）
そのため、新しめの内容で新たに邦訳された本書はありがたい
内容としては原題に"[Algorithms for Reinforcement Learning] (https://sites.ualberta.ca/~szepesva/RLBook.html)"とある通り、強化学習の基本的なアルゴリズムが短くコンパクトにまとめられているアルゴリズム集といった趣である
問題を数式で定式化しながらアルゴリズムを数理的に解説する、そして擬似コードでアルゴリズムの実装を示すというスタイルで書かれている（どのような問題に適用できるかを解説するというよりは、数理的な説明に重きをおいている）
そのため、数学的な素養（機械学習や制御、その他の応用数学）がないと理解することが厳しく、またエンジニアとして実装してみることも本書だけでは厳しいと思われる
どのような研究に応用されているかを概観するには『これからの強化学習』（森北出版 2016）を読んだほうがよいと思われる
また原著では深層学習を含むアルゴリズムをカバーしていないが、訳者により、深層強化学習を含む最近の発展についても付録として記載されている

おさらい

TD学習

TD学習（時間的差分学習）もしくはTD法とは、状態遷移のモデルが分からない場合において、現在の時間ステップ $t$ から次の時間ステップ $t+1$ で観測した情報の差分（時間的差分）のみを使って価値を推定する学習方式である。

モンテカルロ法（ひたすらランダムに動いて価値を観測する手法）ではエピソードの終わり（迷路のゴールなど、最終的な報酬が得られるまで）を観測して初めて行動価値の推定を更新できるのに対し、TD法では1ステップ先までの情報を用いて価値推定を更新できるので、より手早く（環境のモデルを作らず、漸進的に）行動価値を推定することができるという利点がある。

TD(λ)法

TD学習のうちTD(0)法は、1ステップ先 $t+1$ で観測した情報をもとに現在の推定価値（方策$π$の価値関数$V^π(s_t)$）を更新するというシンプルなブートストラップ的（＝既存の推定値を一部用いて推定値を更新していく）手法であった。

一方でモンテカルロ法とはエピソード全体（ゴールで報酬を得るまで）で観測した情報をもとに推定価値を更新する手法であった。

このTD法とモンテカルロ法、両者のいいところ取りをしたのがTD(λ)法である。TD(λ)法は、1ステップ先だけではなくその先の複数ステップも（ある程度減衰させながらも）参考にする手法である。nステップ先でどれくらい減衰させるかは適格度トレースと呼ばれる（各ステップでの適格さ＝影響の度合いを調節していることに由来しているらしい）。

関数近似法

状態空間が大規模（または無限大）であるとき、各状態の価値をメモリ上にひとつひとつ保持することは大変なので、一定の次元数の特徴量からなるベクトル空間に情報を近似させて推定値を求める手法がよく採用される。これを関数近似法と呼び、状態空間からベクトル空間への写像を特徴抽出法、ベクトルの要素を定義する個々の関数を基底関数と呼ぶ。

輪読レジュメ

邦訳本p.26～38 2.2.1～2.2.3
原著PDF版p.29～40 3.2.1～3.2.3 に相当

2.2.1 関数近似を用いたTD(λ)法

線形関数近似器を用いたTD(λ)法では、状態空間の近似にパラメトリックで滑らかな関数近似 $V_θ$ を用いる。$V_θ$はパラメータに対して線形であるため、更新式2.5は前のTD(λ)法の更新式と一致する。
ただし、関数近似を用いたTD(λ)法は収束が保証されない問題がある（特に方策オフ型学習では条件に限らず発散しうる）。収束を保証するには一定の条件を満たす必要がある。
$λ→0$になるにつれて、より大きな誤差の生まれる余地が大きくなる。
$λ<1$のTD(λ)法では価値関数の近似精度としてはTD(1)法（＝モンテカルロ法）に劣ってしまうが、制御性能（詳しくは第3章）としては遜色ない。また、経験的に収束が早いことも$λ<1$のTD(λ)法がTD(1)法よりも好まれる主な理由となっている。
λが1に近づくと"いかに特徴量が価値関数の構造を捉えているか"（長期的なダイナミクスと報酬）が重要になり、λが0に近づくと"いかにうまく即時報酬と直近の特徴量の期待値の構造を捉えているか"（短期的なダイナミクスと報酬）が重要になる。

2.2.2 勾配TD学習 (gradient temporal difference learning)

線形関数近似器を用いたTD(λ)法の欠点である方策オフ型学習の状況下で発散しうるという問題を回避するために、いくつかの手法（アルゴリズム）がある。
本節で紹介する手法（GTD2およびTDC）は計算量がTD(λ)法に比べて相当大きくなる問題があるが、2.2.3節で紹介する手法はTD(λ)法とほぼ同程度の計算量で実行できる。

2.2.3 最小二乗法

2.2.2節で紹介された手法はノイズ混じりの勾配のような信号に従ってパラメータを少しずつ変化させるという点で適応フィルタにおけるLMSアルゴリズムと類似している。
そのためLMSアルゴリズムと同様にこれらの手法はステップ幅の選択などのハイパーパラメータに対して敏感であり、チューニングが大変である。
適応フィルタではLMSアルゴリズムのすべての欠点に対応するアルゴリズムとしてLS（最小二乗; least-squares）アルゴリズムが知られている。
LSアルゴリズムと機能的に類似する強化学習手法としてLSTD（最小二乗TD学習）、RLSTD（再帰的LSTD）、LSTD(λ)（TD(λ)のパラメータλを組み込んだLSTDの拡張）、RLSTD(λ)（LSTD(λ)を再帰的に行う）、λ-LSPE（λ-最小二乗方策評価）、iLSTDがある。
(R)LSTD(λ)はその解が存在すれば概収束し、TD(λ)よりも収束が早い。またステップ幅に依存せず行列$A$の固有値の構造や$θ$の初期値の選択に対して敏感でもない。
(λ)LSPEも同様に概収束し、なおかつ常にwell-definedである（＝十分なサンプルサイズ、あるいは適切な初期値のもとで、計算に必要な逆行列がすべて存在する）。LSTD(λ)は方策オフ型の設定の場合、必ずしもwell-definedとはならない。
安定性・正確性と計算量はトレードオフである。最小二乗法は多くの特徴量を扱う（例えば、囲碁の価値関数で100万以上の特徴量を扱う）規模では非現実的になるので、問題によって使い分けるか、計算量を抑えるアルゴリズム上の工夫が必要になる。（その一例がiLSTDである）

その他の参考文献

関数近似を用いたTD学習については、『これからの強化学習』（森北出版 2016）のp.73-111「2.1 統計学習の観点から見たTD学習」（前田新一）にも詳しい。
関数近似の役割として、『速習強化学習』ではメモリの節約が挙げられていたが、『これからの強化学習』では状態$s$や行動$a$に離散値ではなく連続値をもつケース（例えばボールがぶつかるときの角度など）についても挙げられている。そのような場合、状態や行動ごとの価値関数をメモリに保存することができないので、特徴を表わすパラメトリックな関数を用いて価値関数を近似的に表現することが必要になる。