#概要
強化学習理論の基礎1の続きです。
2の範囲は、Model-Free Learningについてです。
3はこちら。

1では、Model-Basedな強化学習の典型であるDPについて学習しました。
今回は、Model-Freeな強化学習のアルゴリズムについて学習します。

#Model-Free Prediction
Model-Free Predictionは、エージェントはMDPについての情報がないという前提のもと、与えられた方策($ \pi $)にとって最適な価値関数($v_ \pi $)を求めることを目的とする。
エージェントは、どの状態のどのアクションの結果どのような状態に遷移するか、どのアクションがどの程度の報酬に結びつくか、という情報は持っていない。
それらはMDPをサンプリングすることでエージェント自ら明らかにしていく。

Model-Free Predictionには、Monte-CarloとTemporal-Differenceという2つの代表的なアルゴリズムが存在する。(Controlでも使う)

##Monte-Carlo Learning
Monte-Carlo(MC)による学習は、実際にサンプリング(経験)したエピソードを元に学習する。
ある状態からサンプリングを始め、最終状態に辿り着いたサンプルから学習し、価値関数の更新を行う。(offline)
そのため、MCによる強化学習は、最終状態があるMDPにしか適用できない。

MC(Evaluation)の目的は、与えられた方策($ \pi $)にとって最適な価値関数($v_ \pi $)を求めることである。

S_1, A_1, R_1...S_k ~ \pi

最もシンプルなMCでは、各エピソードでタイムステップごとの報酬を記憶しておき、それぞれの状態での報酬を平均する。
平均を求める手法は大きく分けて2つ存在する。

1つ目が、First-Visitである。
１つのエピソードの中で、ある状態(s)に初めてたどり着いた時、エージェントは以下のことをする。

状態ごとに保持するカウンタに1を足す($N(s) \leftarrow N(s) + 1$)
状態ごとに保持する報酬の合計に、sから先で得られる報酬を足す($S(s) \leftarrow S(s) + G_t$)

G_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma ^{T-1} R_T

全てのエピソードを終えた後、状態(s)の合計報酬を状態(s)にたどり着いたエピソードの数で割り、平均を求める。($V(s) = S(s)/N(s)$)
$V(s)$は最終的に$v_ \pi (s)$に収束することが証明されている。

2つ目が、Every-Visitである。
First-Visitと実施することは同じで、カウントする条件のみが違う。
全エピソードの中で、ある状態(s)にたどり着く度に、エージェントは以下のことをする。

状態ごとに保持するカウンタに1を足す($N(s) \leftarrow N(s) + 1$)
状態ごとに保持する報酬の合計に、sから先で得られる報酬を足す($S(s) \leftarrow S(s) + G_t$)

全てのエピソードを終えた後、状態(s)の合計報酬を状態(s)にたどり着いた回数で割り、平均を求める。($V(s) = S(s)/N(s)$)

上記2つの方法では、全エピソードを回してから、合計/回数で平均をとっていた。
しかし、1エピソードごとに値を更新していく場合と最終的には同じ値になることが、以下の式でわかる。($ \mu $は平均、kはエピソード数、xは１回分の報酬)

\begin{align}
\mu _k &= \frac{1}{k} \sum ^k_{j = 1}x_j \\
&= \frac{1}{k} (x_k +  \sum ^{k - 1}_{j = 1}x_j) \\
&= \frac{1}{k} (x_k +  (k - 1) \mu _{k - 1}) \\
&= \mu _{k - 1} + \frac{1}{k} (x_k - \mu _{k - 1})
\end{align}

上記の式の最後の行は、よく機械学習で出てくる式の形になっている。($\frac{1}{k}$が学習率になっていたり。。。)
$\frac{1}{k}$より後ろの項は、よく誤差関数(Error Function)と呼ばれる。

各エピソードごとに価値関数を更新する場合以下のような方法を取る。
ある状態($S_t$)にたどり着く度に、エージェントはカウンタをインクリメントする。($N(S_t) \leftarrow N(S_t) + 1$)
エピソード終了ごとの更新は、以下の式のようになる。

V(S_t) = V(S_t) - \frac{1}{N(S_t)} (G_t - V(S_t))

以上より、MCの長所は、非定常なMDPに向いているという点と言える。
MCは、古い$V(S_t)$やエピソードごとの情報を忘れ、更新された新しい$V(S_t)$のみを保持する。
そのため、膨大な状態が想定される非定常状態において、全ての情報を記憶する必要がないことは都合が良い。

最後にMCの欠点として、結局エピソードが終わらなければ、どの状態も更新できないことが挙げられる。
ある状態からスタートして、最終状態にたどり着いた時点で、そのエピソードで得られた報酬が確定する。
そのため、エピソードが終わるたびに、もう一度最初の状態から$V(S_t)$の更新を最終状態に向けて(Forward)行なっていく必要がある。

##Temporal-Difference Learning
Temporal-Difference(TD)による学習は、MCと同様にサンプル(経験)から学習する。
MCとの最も大きな違いは、エピソードが完了していなくても、その状態から先の報酬を予測し、学習する点である。(bootstrapping)
これは、ある状態の価値をその先の状態の価値から予測して学習することを意味する。

TD(Evaluation)の目的は、MCと同様に与えられた方策($ \pi $)における$V_ \pi $を経験から学習することだが、上記で述べたようにエピソードが終わる前に学習を行う。(online)

最もシンプルなTD(TD(0))のある状態($S_t$)における状態価値関数($V(S_t)$)の更新は、以下のように表せる。

V(S_t) = V(S_t) + \alpha (R_{t + 1} + \gamma V(S_{t + 1}) - V(S_t))

$R_{t+1} + \gamma V(S_{t+1})$の部分をTD targetと呼び、今回のサンプリングで得られた値を表す。
また、$(R_{t + 1} + \gamma V(S_{t + 1}) - V(S_t))$の部分をTD errorと呼び、今回のサンプリングの値と前回までに得た値の差を表す。(αは学習率)

##MCとTDの違い

MCとTDの大きな違いは、以下の通り。

MCがエピソードが終わり報酬が確定してから学習を行うのに対して、TDは1ステップごとに学習を行う
MCが完全シーケンスからのみ学習が可能であるのに対して、TDは不完全なシーケンスからも学習できる
= MCは確実に終了する環境のみでしか学習できないが、TDは終端が存在しない環境でも学習できる
MCはバイアスが全くないが、バリアンスが高い
TDはバイアスが多少存在するが、バリアンスは低い
MCは初期値の影響をあまり受けないが、TDは初期値の学習への影響が大きい
TDはマルコフ性を利用するので、マルコフ性を持つ環境ではMCより効率的である(各状態遷移も学習するため)
MCはマルコフ性を利用しないので、マルコフ性を持たない環境で効果的である(エピソードごとの合計報酬で各状態の価値を学習するため)

MCは、実際にサンプリングされたデータを使って学習するため、バイアスは全くない。
一方、TDは、学習途中の$V(S_t)$と方策($ \pi $)に沿って行動した時に最適化された$V_ \pi (S_t)$に誤差があるためにバイアスが発生する。
MCはエピソードが終了してから学習を行うため、そのエピソード内の全てのランダムなアクション、状態遷移、報酬を使って学習を行うことになる($R_{t+1} + \gamma R_{t+2} ...$) = 学習結果の分散が大きくなる。
TDは、１つ先の遷移後状態より後の行動や遷移は決まっており、1つのアクション、状態遷移、報酬のみがランダムである($R_{t+1} + \gamma V(S_{t+1})$) = 学習結果の分散がそこまで大きくならない。

##TD(λ)
###Forward-view TD(λ)
TD(0)では、1つ先の状態($S_{t+1}$)の価値関数と実際に得られた即時報酬($R_{t+1}$)を使って、状態($S_t$)の価値関数($V(S_t)$)を更新した。
これは、$R_{t+1}$というたった今得られたサンプルを利用しているため、少しだけ実際のモデルに近づく方向に更新をしていると言える。
では2つ先の状態($S_{t+2}$)まで進んでから$V(S_t)$を更新すれば、より実際のモデルに近づくことになる。
3つ先、4つ先と進めていくとMCになることがわかる。

V(S_t) = V(S_t) + \alpha (R_{t + 1} + \gamma V(S_{t + 1}) - V(S_t))\\
V(S_t) = V(S_t) + \alpha (R_{t + 1} + \gamma R_{t + 2} + \gamma ^2 V(S_{t + 2}) - V(S_t))\\
V(S_t) = V(S_t) + \alpha (R_{t + 1} + \gamma R_{t + 2} + \gamma ^2 R_{t + 3} + \gamma ^3 V(S_{t + 3}) - V(S_t))\\
\vdots \\
V(S_t) = V(S_t) - \alpha (G_t - V(S_t)), \; G_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma ^{T-1} R_T

次にnステップのTDを定義する。

G^{(n)}_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma ^{n-1} R_{t+n} + \gamma ^n V({S_{t+n}}) \\
V(S_t) = V(S_t) + \alpha (G^{(n)}_t - V(S_t))

するとTDターゲット($G_t$)は以下のように変化する。

\begin{align}
n &= 1 \; \; G^{(1)}_t = R_{t+1} + \gamma  V({S_{t+1}}) \\
n &= 2 \; \; G^{(2)}_t = R_{t+1} + \gamma R_{t+2} + \gamma ^2 V({S_{t+2}}) \\
\vdots \\
n &= \infty \; \; G^{( \infty )}_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma ^{T-1} R_T
\end{align}

nが1の時はTD、nが∞の時はMCになる。
nが大きくなるほど、今回のエピソードの影響が大きくなる。

では、どのnが最適なのか。
その答えとして、ここではTD(λ)という考えを使って、異なる全てのnからその平均をとる方法を考える。
TD(λ)では、各$G_t$に$(1- \lambda ) \lambda ^{n-1}$をかけ、それを合計する。($1- \lambda $は合計を1にするための正規化)
これを「λ return」と呼ぶ。

\begin{align}
G^ \lambda _t &= (1- \lambda ) \; G^{(1)}_t + (1- \lambda )\lambda  \; G^{(2)}_t + ... \\
&= (1- \lambda ) \sum^ \infty _{n = 1} \lambda ^{n - 1} G^{(n)}_t
\end{align}

λが0の時をTD(0)、λが1の時をTD(1)のように表す。
λの値が小さければ小さいほど、現在の状態($S_t$)に近い状態の価値関数の値(予測)を信頼することになり、大きければ大きいほど今回のエピソードの報酬データを信頼することになる。
TD(1)を各状態の価値関数をエピソード終了後に更新するようにすると、MCと全く同じアルゴリズムとなる。

このように後のタイムステップの報酬を利用するTD(λ)をForward-view TD(λ)と呼び、以下のような式で$V(S_t)$が更新される。

V(S_t) = V(S_t) + \alpha (G^ \lambda _t - V(S_t))

λ returnからもわかるように、Forward-view TD(λ)はMCと同様に、エピソードが完了しなければ学習することはできない。

###Backward-view TD(λ)
では、各ステップごとに学習し、さらに完了しないエピソードからも学習できるようにするにはどうすればよいか。
そこで登場するのが、Backward-view TD(λ)である。
Backward-view TD(λ)では、Eligibility tracesという考えを使う。
Eligibility tracesは、何か現象が発生した時、その責任がどの状態にあるかを考えるかという考えが根底にある。
最もメジャーな考え方に、現象が発生する前に最もよく訪れた状態に責任があるという考え(Frequency Heuristic)、現象が発生する直前の状態に責任があるという考え(Recency Heuristic)の2つがある。
例えば、3日連続で雨が降った後に1日晴れたとする。すると、夜空がとても綺麗だった。
夜空が綺麗だった責任の所在は、Frequency Heuristicの考えでは雨の状態にあり、Recency Heuristicの考えでは晴れの状態にある。
この2つを組み合わせた考えがEligibility tracesである。

以下はEligibility traces(accumulating Eligibility traces)と$V(s)$の更新を式で表したものである。

E_0(s) = 0 \\
E_t(s) \leftarrow \gamma \lambda E_{t-1}(s) + 1(S_t = s) \\
\delta _t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \\
V(s) \leftarrow V(s) + \alpha \delta _t E_t(s)

まず前提として、$E_t$(Eligibility traces)は全ての状態に対して保持し、また各ステップごとに全状態の$E_t$を更新し、更新した$E_t$を使って全状態の$V(s)$を更新する。

次に$E_t$の中身を解説する。
γは割引率であり、Recency Heuristicの考えを表している。例えば、エピソードの最初の方に訪れたがその後ずっと訪れなかった状態のEtは、ステップごとに1にλとγが掛けられて減少していく。
+1の部分は、もし現在の状態の$E_t$であれば1を足すということなので、Frequency Heuristicの考えを表している。
さらにλが入っているため、TD(λ)の考えも導入している。
λが0の場合、現在の状態以外の$E_t$は0になり、現在の状態のみ更新され、TD(0)の更新と同様となる。

\left\{
\begin{array}{ll}
E_t(s) = \gamma \times 0 \times E_{t-1}(s) = 0 & (S_t \neq s) \\
E_t(s) = \gamma \times 0 \times E_{t-1}(s) + 1 = 1 & (S_t = s)
\end{array}
\right.

λが1の場合、$E_t$は割引率によってのみ減退され、TD(1)の更新と同様となる。(Offlineの学習時のみ)
詳しい計算は講義資料を参照すること。

\left\{
\begin{array}{ll}
E_t(s) = \gamma \times 1 \times E_{t-1}(s) = \gamma E_{t-1}(s) & (S_t \neq s) \\
E_t(s) = \gamma \times 1 \times E_{t-1}(s) + 1 = \gamma E_{t-1}(s) + 1 & (S_t = s)
\end{array}
\right.

このように、価値関数の更新を後ろ向きに行うので、Backward-view TD(λ)と呼ばれる。
Backward-view TD(λ)は、ステップごとのV(s)の更新が可能であり、完了しないエピソードにおける学習も可能とである。

#Model-Free Control
Model-Free Predictionでは、未知のMDPにおける価値関数を推測した。
Model-Free Controlでは、未知のMDPにおける価値関数の最適化を行う。

Model-Free Controlの手法には、On-Policy LearningとOff-Policy Learningという2つがある。
On-Policyは、ある方策(π)によって得たサンプルを利用して、方策(π)自身を評価する。
人間で言えば、自分自身の経験から学習するということになる。
Off-Policyは、ある方策(μ)によって得たサンプルを利用して、方策(π)を評価する。
これは、ロボットが人間の経験を利用して学習するようなものになる。学習の結果、よりよい方策を見つけることもできる。
DPを知っていれば、On-PolicyはPolicy IterationのModel-Free版、Off-PolicyはValue IterationのModel-Free版とした方がわかりやすいかもしれない。

##On-Policy learning
###On-Policy Monte-Carlo Learning
まず、Policy IterationをMCに取り入れる。
Policy Iterationでは、ある方策($ \pi $)における最適な価値関数($V_ \pi $)を学習してから(ステップ1)、方策の最適化($ \pi '$)を行なった(ステップ2)。それを繰り返すことで最適な方策($ \pi _*$)を見つけた。

最もシンプルな手法では以下のようになる。
ステップ1の部分には、MCを適用する。
ステップ2に関しては、現状の$V_ \pi $において最大報酬が得られる行動をとるように方策を改善する。(Greedy Policy Improvement)

しかし、これには2つの問題点がある。
1つ目は、MCはModelが未知のため、状態価値関数を利用して方策を最適化できないことである。
状態価値関数($V(s')$)を利用した、greedy Policy Improvementを確認する。

\pi '(s) = argmax_{a \in A} \: R^a_s + P^a_{ss'} V(s')

ここでPが入っていることが確認できるが、Pはモデルを知っていなければわからない。
On-Policy MCはModel-Freeのため、Pを利用して方策の最適化を行うことはできない。

ここで状態価値関数ではなく、行動価値関数を利用すれば、この問題は解決する。
行動価値関数(Q)を利用した方策の更新は以下のようになる。

\pi '(s) = argmax_{a \in A} \: Q(s, a)

この式では、Pは登場しないため、モデルが未知の場合でもgreedyな方策の更新が可能になる。
以上より、On-Policy MCでは、Qが$q_ \pi $になるまで学習してから、方策の更新を行うことになる。

2つ目は、搾取と探索の問題(exploration-exploitation trade-off)である。
常に最大報酬が予測されている状態や行動を選択した場合、実は今わかっている最適なパスよりも多くの報酬を最終的に取得できるパスがあるかもしれないにも関わらず、そのパスが学習されることはなくなってしまう。
DPでは、モデルが全てわかっており、さらに全てのパスを更新していくため、この問題は生じなかった。

この問題を解決するために、ε-Greedy explorationを導入する。
これはとてもシンプルな考えであり、$ \epsilon $に指定した割合だけランダムなアクションを選択し、$1 - \epsilon $の割合だけgreedyにアクションを選択する。以下の式はその確率を表す。

\pi (a|s) = \left\{
\begin{array}{ll}
\epsilon / m + 1 - \epsilon & if \: argmax_{a \in A} \: Q(s, a) \\
\epsilon / m & otherwise
\end{array}
\right.

$ \epsilon /m$は、全てのアクションmにおけるεの割合である。
greedyの場合にも$ \epsilon /m$を足しているのは、ランダムにアクションを選択した場合でも、それがgreedyに選択したアクションと同じになる可能性が存在するためである。
では、ε-Greedyを採用したとしても、古い方策($ \pi $)よりも更新後の方策($ \pi '$)の方が優れた方策であると言えるのであろうか。

\begin{align}
q_ \pi (s, \pi '(s)) &= \sum _{a \in A} \pi '(a|s) q_ \pi (s,a) \\
&= \epsilon / m \sum _{a \in A} q_ \pi (s,a) + (1 - \epsilon ) \: max_{a \in A} \: q_ \pi (s,a) \\
&\geq \epsilon / m \sum _{a \in A} q_ \pi (s,a) + (1 - \epsilon ) \: \sum _{a \in A} \frac{\pi (a|s) - \epsilon / m}{1 - \epsilon} \: q_ \pi (s,a) \\
&= \sum _{a \in A} \pi (a|s) q_ \pi (s,a) = v_ \pi (s)
\end{align}

最も価値の高いアクションは、全ての他のアクションの価値の合計よりも、高い価値がある。
そのため、$ \pi '$は必ず$ \pi $よりも優れた方策となる。

また、DPと同様に、$v_ \pi $を求めてから方策を更新するのではなく、vの更新を行なったらすぐに方策の更新を行うようにする。(Policy Iteration → Value Iteration)
ここでは、1エピソードごとに$q_ \pi$を更新し、また方策($ \pi $)も更新するようにし、効率的に$\pi * $と$q* $を求めるようにする。

搾取と探索への対策の最後として、GLIE(Greedy in the Limit with Infinite Exploration)を採用する。
シンプルなε-Greedy explorationについて、本当に全ての価値関数を網羅できるのか、効率的に最適化できるのかという疑問がある。
GLIEでは全ての状態とアクションのペアを無限に探索し、全てのペアを探し出す。
また、最終的に完全にgreedyな方策に収束する。
これをMCに適用したアルゴリズムをGLIE Monte-Carloと呼ぶ。

具体的には以下の処理を行う。
方策$ \pi : {S_1, A_1, R_2, ..., S_T} ~ \pi $を利用したk回目のエピソードを考える。
エピソード内である状態($S_t$)とアクション($A_t$)を訪れるたびに、カウンタを更新($N_t (S_t, A_t) \leftarrow N_t (S_t, A_t) + 1 $)する。
エピソード終了後には、価値関数を$G_t$の平均によって更新する($ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N_t (S_t, A_t)}(G_t - Q(S_t, A_t))) $)。
そして問題の$ \pi $と$ \epsilon $は、以下のようになる。

\epsilon = 1 / k
\pi = \epsilon -greedy(Q)

エピソードが進めば進むほど、$ \epsilon $の値は減少し、より完全なgreedyな方策に近づいていくことになる。
そしてエピソードが完了するたびに$ pi $が更新されることもわかる。

おまけだが、Qの初期値がいかなる値であっても、学習に影響がない。(最初の更新では$N_t (S_t, A_t)$が1になるため)

###On-Policy Temporal-Difference Learning(Sarsa)
On-Policy TDは、TDに前述のQによる方策更新、ε-Greedyを適用する。(+ TDのためステップごとに価値関数を更新)

On-Policy TDによる価値関数の更新はSarsaと呼ばれる。
理由は、下記のように$[S, A, R, S', A']$を使って、Qの更新を行うためである。

Q(S,A) = Q(S,A) + \alpha (R + \gamma Q(S',A') - Q(S,A))

この時、次のアクション(A')は、遷移先状態(S')と方策($ \pi $)によって決定される。
On-Policy TDでは、価値関数の更新だけでなく、方策($ \pi $)の更新もステップごとに行う。
まとめると、エピソードが終了するまで全てのステップにおいて、以下を繰り返す。

状態Sにいるとき、方策$ \pi $に従ってアクションAを実行する
アクションAによって得られた即時報酬Rと遷移先状態S'を得る
遷移先状態S'と方策$ \pi $によって次のアクションA'を選択する
Q(S,A)をSarsaによって更新する
状態SにS'、アクションAにA'を代入する

Sarsaは、Robbins-Monroシーケンスを満たさなければうまく動かないという理論があるらしいが、経験的には気にしなくて良いらしい。。。

ここで、TDの時と同様にnステップについて考えてみる。(n-Step Sarsa)

q^{(n)}_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma ^{n-1} R_{t+n} + \gamma ^n Q({S_{t+n}}) \\
Q(S_t, A_t) = Q(S_t, A_t) + \alpha (q^{(n)}_t - Q(S_t, A_t))

上記の1つ目の式をn-step Q-Returnと呼ぶ。
2つ目の式は、n-step Q-Returnを使った、n-Step SarsaによるQの更新である。

ここで、TD(λ)と同様にSarsa(λ)を定義するが、Forward-view TD(λ)の$G_t$が$q_t$に変わっただけである。

q^ \lambda _t = (1- \lambda ) \sum^ \infty _{n = 1} \lambda ^{n - 1} q^{(n)}_t

これを利用したQの更新は以下のようになり、Forward-view Sarsa(λ)と呼ぶ。

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (q^{( \lambda )}_t - Q(S_t, A_t))

Forward-view Sarsa(λ)は、Forward-view TD(λ)と同様にOnlineでのQの更新ができない。
そのため、Sarsa(λ)にもEligibility Tracesを導入し、Backward-view Sarsa(λ)を定義する。

E_0(s,a) = 0 \\
E_t(s,a) \leftarrow \gamma \lambda E_{t-1}(s,a) + 1(S_t = s, A_t = a) \\
\delta _t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \\
Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \delta _t E_t(s,a)

これも、状態のみから状態とアクションのセットになった以外は、Backward-view TD(λ)と変わらない。
$E_t$は全ての状態とアクションのペアに対して保持し、また各ステップごとに全てのペアの$E_t$を更新し、更新した$E_t$を使って全ペアの$Q(s,a)$を更新する。

##Off-Policy Learning
Off-Policy Learningは、ある方策$ \mu (a|s)$(Behaviour Policy)に従って得たサンプルを利用して、別の方策$ \pi (a|s)$(Target Policy)を評価/更新する。
$ \pi $は完全greedyであり、$ \mu $は$ \pi $よりも探索を行うような方策であることが多い(ε-Greedyなど)。
Off-Policy Learningの利点は、以下の通り。

人間や他のエージェントの振る舞いから学習できる
古い方策の経験を再利用することができる($ \pi _1, \pi _2, ...\pi _{t-1} $)
ランダムに行動する方策(Exploratory Policy)で状態/アクションを探索しつつ、最適な方策について学習することができる
1つの方策に従いつつ、複数の方策について学習することができる(1つの経験から多くの方策について学習できる)

###重点サンプリング
Off-Policy Learningで重要な考えにImportance Sampling(重点サンプリング)がある。
これは簡単に言うと、異なる分布の期待値の推定において、より重要と考えられる確率領域を重点的にサンプリングすることである。
ある確率分布$P(X)$が存在する時、期待値を$f(X)$とすると、予測値は以下のようになる。

E_{X \sim P}[f(X)] = \sum P(X) f(X)

$P(X)$を別の確率分布$Q(X)$で割り、さらに$Q(X)$をかける。
そうすると、$P(X) f(X)/Q(X)$についての$Q(X)$の分布の時の期待値を得ることができる。
ちなみに、$P(X)/Q(X)$をImportance Sampling Rationと呼ぶ。

\begin{align}
E_{X \sim P}[f(X)] &= \sum P(X) f(X) \\
&= \sum Q(X) \frac{P(X)}{Q(X)} f(X) \\
&= E_{X \sim Q} \Bigl[ \frac{P(X)}{Q(X)} f(X) \Bigr]
\end{align}

###Off-Policy Monte-Carlo with Importance Sampling

まずは、この考えをMCに適用する。
方策$ \mu $によって得た報酬$G_t$を使って、方策$ \pi $を評価する。
ステップtから先の報酬の最大合計$G_t$に、方策$ \mu $と方策$ \pi $の各ステップにおける類似割合を全て掛ける。

G^{ \pi / \mu } _t = \frac{ \pi (A_t \, | \, S_t)}{ \mu (A_t \, | \, S_t)} \frac{ \pi (A_{t+1} \, | \, S_{t+1})}{ \mu (A_{t+1} \, | \, S_{t+1})} \cdots \frac{ \pi (A_T \, | \, S_T)}{ \mu (A_T \, | \, S_T)} G_t

この計算によって$ \pi $によって選択される可能性が$ \mu $によって選択される可能性よりもかなり低いサンプルの重要度は0に限りなく近くなり、$ \pi $によって選択される可能性が$ \mu $によって選択される可能性よりもかなり高い場合は大きくなる。これは、$ \mu $によって選択される可能性が少ない = サンプルが少ないため、より重要度(Importance)が増すためである。

価値関数の更新はこの$G^{ \pi / \mu } _t$によって行う。

V(S_t) \leftarrow V(S_t) + \alpha (G^{ \pi / \mu } _t - V(S_t))

重点サンプリングはとても重要だが、MCに適用した場合、分散が大きくなり過ぎてしまい、実用的ではない。

###Off-Policy Temporal-Difference with Importance Sampling
次にTDについて見てみる。
TDはbootstrapするため、重点サンプリングを使っても分散を抑えることができる。(MCよりも大分抑えられる)

まず、MC同じように、方策$ \mu $によって得たTDターゲット$R + \gamma V(S')$を使って、方策$ \pi $を評価する。
MCとの大きな違いは、Importance Sampling Ratioを1ステップ分だけTDターゲットに掛けるというところである。

V(S_t) \leftarrow V(S_t) + \alpha ( \frac{ \pi (A_t \, | \, S_t)}{ \mu (A_t \, | \, S_t)} (R_{t+1} + \gamma V(S_{t+1})) - V(S_t))

###Q-Learning
最後に、Q-Learning(Q学習)と呼ばれる、行動価値関数を利用したOff-Policy Learning(TD(0)の)を確認する。
Q学習には、重点サンプリングは必要ない。
その理由は以下の通りである。
まず、次のステップのアクション$A_{t+1}$をBehaviour Policy$ \mu $によって選択する。
それと同時に、Target Policy$ \pi $によってもう１つのアクション$A'$を考慮する。
実際に行うアクションは$A_{t+1}$であり、$A'$はこのアクションをとったらどれくらいの報酬が得られるかということを計算するために使う。
行動価値関数の更新は以下のようになる。

Q(S_t, A_t) = Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A') - Q(S_t, A_t))

Q(S_t, A_t)を、Target Policyに従って選択したアクションを実行した場合の報酬を使って更新している。
何をしているかというと、Behaviour Policyに従ってサンプリングを進めながら、価値関数の更新はTarget Policyによって行なっている。
これによって、Behaviour Policyで得たサンプルを利用して、Target Policyを評価するということを、重点サンプリングなしに行なっているのである。

###Off-Policy Control with Q-Learning
ここで、Q学習によるOff-Policy Controlについて考える。
この場合、Behaviour PolicyとTarget Policyを両方最適化していく。
Target Policy($ \pi $)はgreedy、Behaviour Policy($ \mu $)はε-Greedyとする。
そのため、$ \pi $は常にQ(S, A)において、最大報酬が得られる行動をとる。

\pi (S_{t+1}) = argmax_{a'} Q(S_{t+1}, a')

Q学習で確認したTDターゲットは以下のように簡潔になる。

R_{t+1} + \gamma \, Q(S_{t+1}, A') \\
= R_{t+1} + \gamma \: Q(S_{t+1}, argmax_{a'} \, Q(S_{t+1}, a')) \\
= R_{t+1} + max_{a'} \: \gamma \, Q(S_{t+1}, a')

行動価値関数の更新は、次のように行う。

Q(S, A) \leftarrow Q(S, A) + \alpha (R + max_{a'} \: \gamma \, Q(S', a')) - Q(S, A))

これによって、ε-Greedy Policyで探索を行いながら、Greedy Policyで価値関数の更新を行なっている。
Silver教授は、このQ-LearningアルゴリズムをSARSAMAXと呼んでいた。(S,A,R,S',A'によって価値関数の最適化を行うため)

#最後に
社会人になって再学習したとはいえ、数学を高校2年でやめた、強化学習独学の文系人が書いているので、間違っているところも多いと思います。
間違いを見つけた際には、私自身の学びのためにも、ご指摘いただけると大変ありがたいです。

#参考資料
An Introduction to Reinforcement Learning(訳本は出版されてますが、有料です)
http://incompleteideas.net/book/bookdraft2017nov5.pdf

Algorithms for Reinforcement Learning
https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf