はじめに

前回までに、動的計画法（DP法）およびモンテカルロ法の概要を整理しました．今回は、この２つの手法を組み合わせたTD法という学習手法について整理します（Sutton本：6章）

これは私の学習ノートです．メモ、備忘録です．

今回も、以下の記事を参考にさせていただいています．ありがとうございます．
qiita.com

DP法とMC法の復習

TD法の説明に入る前に、DP法とMC法の概要をざっくりと整理します．そもそも、強化学習でやっていることは方策の元での状態・行動価値（価値関数）を推定し、方策を改善していくというものでです．

DP法では、推定したい価値関数を次の状態の価値関数を用いて計算しました．しかしその前提として、状態遷移（行動を起こしたら、次にどういう状態になるか）が把握できている必要があり、問題の全体像が分買っていない場合は、DP法を使うことはできません．

そこで、状態遷移のモデルが分からないならば、実際に行動をとって情報を集めよう。というのがMC法になります．MC法では試行に基づいてエピソードを生成し、得られた収益を平均することで価値関数の期待値を求めます．しかし、エピソードが終了するまで学習ができないという点がネックになります．

DP法：ブートストラップ（次の状態を使った価値関数の推定）が可能．でも状態遷移のモデルが分かっている必要がある．
MC法：状態遷移が分からなくても価値関数の推定が可能．でも、ブートストラップが使えない．

TD法（Temporal Difference Method）

今回紹介するTD法は、この中間、いいところをとった方法と言えます．つまり、実際にとった行動の結果から価値関数を推定するという点はMCと同じなのですが、その際、エピソード終了を待たず、DP法と同じように次の状態（またはさらにその先も）を使って価値関数の推定を行うことができる手法になります．

TD法の定式化

TD法ではMC法と同様、価値関数の推定は実際に試行を繰り返して行います．時刻 $t$ での状態 $s_t$ を起点として、エピソード終了時に得られる実際の収益を $R_t$ とした場合、MC法における価値関数更新は以下の式で表すことができます．

$$V(s_t) \leftarrow V(s_t) + \alpha [R_t - V(s_t)]$$

ここで、定数 $\alpha$ はステップサイズ・パラメータ、あるいは学習率と呼ばれます．

上記の式における $R_t$ がエピソードの終了を待たねば得られないのですが、TD法ではここを次のステップの推定値に置き換えます．ここが、動的計画法のアイデアになります．

$$V(s_t) \leftarrow V(s_t) + \alpha [r_{t+1} + \gamma V(s_{t+1}) - V(s_t)]$$

結果として、MC法では収益 $R_t$ を目標として更新するのに対し、TD法では $r_{t+1} + \gamma V(s_{t+1})$ を目標にして価値関数の更新を行うことになります．

繰り返しになりますが、TD法は以下のメリットを持つ学習方法だと言えます．

終端状態になるまで学習を行うのを待つ必要がない（DP法のメリット）
他の行動の価値を使って学習を行うことが出来る（DP法のメリット）
状態遷移のモデルを把握してなくてもよい（MC法のメリット）

以下に、DP法、MC法、TD法（後述のTD(0)）のバックアップ線図を示します．

f:id:shirakonotempura:20190202090949p:plain — DP(動的計画）法

f:id:shirakonotempura:20190202091012p:plain — MC（モンテカルロ）法

f:id:shirakonotempura:20190202091023p:plain — TD（Temporal-Difference）法

TD法のアルゴリズム

TD法は別に次のステップの状態しか使えないわけではなく、2ステップ先、3ステップ先と少し先の状態価値を使って推定を行うことができます．それはn-step TD学習（Sutton本：7.1章あたり～）と呼ばれます．

以下に示すアルゴリズムは直近（次のステップ）の価値関数の推定値を用いる方法でTD(0)とか1step-TD法と呼ばれるものになります．なお、MC法は終着状態（Terminal）のステップまで推定に利用するn-step TD学習となります．

Tabular TD(0) for estimating $v_\pi$
Input: the policy $\pi$ to be evaluated
Initialize $V(s)$ arbitrary (e.g., $V(s) = 0, \forall _s \in S^+$
Repeat (for each episode):
$\qquad$ Initialize $S$
$\qquad$ Repeat (for each step of episode):
$\qquad\qquad A \leftarrow$ action given by $\pi$ for $s$
$\qquad\qquad$ Take action $A$ , observe $R, s'$
$\qquad\qquad V(s) \leftarrow V(s) + \alpha [R + \gamma V(s') -V(s)$ ]
$\qquad$ unitil $S$ is terminal

Grid World での実装

例によって、コードを拝借しGrid WorldでTD法の実装を行いました．
得られた状態価値の推定値を以下に示します．精度よく推定できていますね．

f:id:shirakonotempura:20190202092151p:plain

行動価値関数の定式化

ここまで、状態価値関数 $V(s_t)$ を使ってTD法の説明をしてきましたが、行動価値関数 $Q(s_t, a_t)$ にも当然使えます．むしろ、こっちがよく使う式だと思うのですがSutton本の6.1章の導出のところでは出てきません．次回以降に説明する予定のSARSAなどのアルゴリズムの説明ではこちらの式がベースになります．