ポイント
・学習の過程がステップバイステップで理解できる（目で見える）サンプルを示すことで、「なぜそれでうまく学習できるのか」を理解することを目標とする。
・アルゴリズムを愚直に実装したコードを示すことで、数式ではなく、コードを通してアルゴリズムを理解する。
Tabular method
Multi-arm bandit による導入
MDPの枠組みは一旦無視して、強化学習のポイントとなる「考え方」を理解する
・Exploitation - Exploration のバランスが必要。典型的には ε - greedy を利用する。
・環境から収集したデータを元に、行動の価値を見積もる価値関数を構成する。
・データ収取と並行して、価値関数を逐次更新する。
・逐次更新の方法は、一義的に決まるものではないが、「差分を一定の重みで加えて修正する」という考え方が基本。
・価値の初期値を高めにセットして、初期の Exploration を促進する話も入れる。（後々、SARSA, Q-Learning でも必要になるテクニックなので。）
MDPとDynamic Programmingによる厳密解
環境のモデルがあれば、（計算量を無視すれば）DP で価値関数の厳密解が得られる（強化学習は完全に解ける）事を理解する。
・MDPの枠組みを説明。簡単な例で、状態遷移のツリーが展開される様子を理解する。
・ある状態から、すべてのツリーを網羅的に辿って、それぞれの「確率×総報酬」の和で価値関数が計算される。
・価値関数は、ポリシーごとに決まる点に注意。複数のポリシーは、それぞれの価値関数を比較することで、どちらがより優れたポリシーかが決定される。
・Bellman 方程式に変形して、Iterative に価値関数を計算する手法を説明
・「なぜこれでうまくいか」をどう説明するか？？？ツリーの末端から上に向かって、順次、情報が更新される様子を図解？？？
ポリシーアップデート
・あるポリシーの価値関数を用いて、Greedy policy を構成すると、元のポリシーよりも優れたものが得られる。
・価値関数の計算と、それを用いた Greedy policy の再構成を繰り返すことで、ベストなポリシーが得られる。
Policy iteration と Value iteration
・価値関数の計算、Greedy policy の再計算、それぞれの計算量を考えて、現実的には、計算量を削減する工夫が必要になる点を理解。
・Policy iteration において、コーディング上の工夫をする。
・価値関数の収束を待たずに、Policy を随時更新する手法として、Value iteration を説明。
Monte Carlo Method
・環境モデルがない場合、実環境から収集した断片的なデータから学習する必要がある。
・多数のエピソードを収集して、それぞれのエピソードで得られた総報酬の平均値として、価値関数を見積もる。（ただし、その後で Greedy policy を構成する上では、Action - Value function を見積もった方がよい。）
・ポリシーを固定すると Exploration できないので、「価値関数を計算するべきポリシー」とは、異なるポリシーで収集したデータを活用する手法が必要。
・一般論としては、Importance Sampling で対応。
・「価値関数を計算するべきポリシー＝Greedy policy」「データ収集用ポリシー＝ε - greedy」という場合、エピソードの Tail からしか学習できないので、学習の効率が悪い点を説明。
TD Method
SARSA
・価値関数の見積もりをエピソードの総報酬で見積もるのではなく、DP と同じくステップごとに評価する。TD Error による補正を加えていく。
・MC より効率的に学習できることが経験的に分かる。
・online method として ε - greedy を用いて Policy のアップデートを行う手法が SARSA。ε - greedy に伴う不確定性が課題。
Q-Learning
・SARSA を offline 化したもの。よく考えると、ステップごとの評価であれば、Importance Sampling は不要で、TD Error を Greedy Policy に対する評価に置き換えるだけでOK
・一般論としては、SARSA より効率的。ただし、Cliff walk のように作為的に Q-Learning が不利になる例も作れる。
・offline メソッドなので、experience replay （Dyna-Q）や、exploration を促進する Behavior policy の導入（Dyna-Q+）などの工夫がやりやすい。
（TD(n) はコラム程度の言及にとどめる？）
Functional approximation
・状態数が増えると、Tabular 方式が破綻するので、Functional approx を行う。最近は、NN を利用するのが流行り。
・バッチで学習するために、offline メソッドが便利。
・「TD Error の二乗平均誤差」を誤差関数として、Backpropagation でバッチ学習する方法が考えられる。
・walk game の例で説明（環境がランダムなので、環境含めてステートにしないといけない。）
github.com
・Monte Carlo tree search のもっともシンプルな例として、1step だけ先読みする手法を実装。walk game の場合、壁に自ら激突するという単純ミスを防止できる。
・Functional approximation の場合、価値関数はどうしても不正確になるので、それを compensate するために、本番時に再度、シミュレーションでエピソードを収集して補正する、という考え方。
