#はじめに
JDLA E資格試験で出題される、強化学習の価値ベースのアルゴリズム、特にQ学習とSarsaについて解説した記事です。
E資格試験の機械学習パートでは、Q学習とSarsaの更新則や特徴について出題されます。

なお、他パートの具体的な解説については、下記をご覧ください。
[E資格試験に関する私の投稿記事リスト][link-1]
[link-1]:https://qiita.com/fridericusgauss/items/5a97f2645cdcefe15ce0

###目次

強化学習アルゴリズム
TD学習
Q学習
Sarsa
おわりに

###数式表記
$\mathbb{R}$は実数集合、$\mathrm{U}(X)$は集合$X$の実数値一様分布、$\mathrm{U}_{\mathbb{R}}(a,b)$は閉区間$[a,b]$の実数値一様分布です。
また、$\theta \sim \mathrm{P}$は確率分布$\mathrm{P}$に従う乱数であることを表します。

#強化学習アルゴリズム
E資格試験の機械学習パートで出題される、強化学習アルゴリズムを大まかに分類すると下記表になります。

モデル	学習方式	価値推定方式	方策オン/オフ	アルゴリズム
モデルベース	価値/方策ベース	―	―	動的計画法
モデルフリー	価値ベース	実績ベース	方策オン/オフ	MC法
モデルフリー	価値ベース	TD学習	方策オフ	Q学習
モデルフリー	価値ベース	TD学習	方策オン	Sarsa
モデルフリー	方策ベース	―	―	REINFORCE
モデルフリー	Actor-Critic	TD学習	―	A3C

#TD学習
###位置づけ
Q学習とSarsaは、価値ベースでTemporal-Difference学習（TD学習）に分類されます。

価値ベース：明示的な方策はなく、サンプルから学習し、最適な価値関数の値を逐次推定するアルゴリズム。「価値」を求めたうえでその「価値」を高めるような「方策」を選択する。（厳密には方策自身はあるが、価値関数が最大の方策を常に選択する）
Temporal-Difference学習（TD学習）：サンプルが予測ベースなので、エピソード途中で、目標の価値と現在の価値のズレ（Temporal-Difference誤差：TD誤差）を修正していくことで、価値関数を推定する。

また、Q学習は方策オフ型、__Sarsaは方策オン型__です。

方策オン型：ターゲット方策$＝$行動方策$\pi(a|s)$
方策オフ型：ターゲット方策$\neq$行動方策$\pi(a|s)$

方策の違いは下記の通りです。

行動方策$\pi$：行動を決定する方策
ターゲット方策：行動価値関数の更新に用いる方策

価値関数の種類やベルマン方程式については、下記記事をご覧ください。
[強化学習の価値関数とベルマン方程式][link-2]
[link-2]:https://qiita.com/fridericusgauss/items/a2b868490eb809b19872

###ベルマン方程式との違い
ベルマン方程式は、各状態・行動の報酬に状態遷移確率をかけて総和をとることで価値関数を表しています。
このため、状態遷移確率が既知であれば解けますが、実際には未知であることが多いです。
そこで、TD学習は、試行錯誤で得たサンプルから、状態遷移確率を推測します。
つまり、__状態遷移確率は未知だが、実際の観測を集めながら価値関数を逐次更新していけば、ベルマン方程式が指す式に収束していくだろう__という発想です。

###方策決定
行動方策$\pi$は、ある状態$s$が与えられたとき、行動$a$を返す関数です。
確率的方策$\pi(a|s)$の場合、条件付き確率で与えられます。
この具体的な方策関数を$a=K(s)$と表すことにします。

####【greedy法】
貪欲法（greedy法）とは、$Q(s,a)$を$a$について最大化するものとして選ぶ方法で、次に得る利得が高くなることが経験的に期待できます。
greedy法の方策関数を$K(s)$は式(1)で表されます。

\begin{align}
K(s)= \mathrm{arg}\max_{a\in A}Q(s,a)
\end{align}
\tag{1}

####【ε-greedy法】
$\varepsilon$-greedy法は、閾値$\varepsilon\in[0,1]$を設定しておき、基本的にはgreedy法に従って選択するが、閾値を満たした場合だけ完全にランダムに行動を選ぶ方法です。
greedy法に比べて、局所的最適解に収束しにくくなることが期待できます。
$\varepsilon$-greedy法の方策関数を$K(s)$は式(2)で表されます。

K(s)=  \left\{
\begin{array}{ll}
\mathrm{arg}\max_{a\in A}Q(s,a), \theta>\varepsilon\\
a_{\mathrm{rand}}, \mathrm{otherwise}
\end{array}
\right.
\tag{2}

$\theta \sim \mathrm{U}_{\mathbb{R}}(0,1)$は$[0,1]$から一様に選ばれた乱数、$a_{\mathrm{rand}} \sim \mathrm{U}(A)$は行動集合$A$から一様に選ばれた行動です。

方策オン型のアルゴリズムで使用される場合、序盤のエピソードでは、$\varepsilon$を大きくしておくことで、方策の依存性を低くし、エピソードが進むごとに$\varepsilon$をスケジューリング的に減少させ、方策の依存性を高めていくことが一般的です。
これは、__多様化と集中化__といい、探索アルゴリズムでは経験的に上手くいく探索戦略です。
なお、方策オフ型のアルゴリズムでは、方策に依存しないため、$\varepsilon$をエピソード毎に調整する必要がありません。

#Q学習
###更新則
以降では、ステップ$t$における状態$s(t)=s\in S$、行動$a(t)=a\in A$、ステップ$t+1$における即時報酬$r(t+1)=r\in \mathbb{R}$、状態$s(t+1)=s^{\prime}\in S$、状態$a(t+1)=a^{\prime}\in A$とします。
Q学習における行動価値関数$Q$の更新則は式(3)で表されます。

\begin{align}
Q(s,a):
&=Q(s,a)+\alpha\left(r+\gamma Q_{\mathrm{max}}-Q(s,a)\right)\\
Q_{\mathrm{max}} &= \max_{a^{\prime}\in A}Q(s^{\prime},a^{\prime})
\end{align}
\tag{3}

ただし、$\alpha \in [0,1]$はステップサイズです。
右辺の$Q_{\mathrm{max}}$は、状態$s(t+1)=s^{\prime}$において、_方策に従わず、次の行動$a(t+1)=a^{\prime}\in A$の可能な範囲を調べた上で、最大となる行動価値__です。
TD誤差は$r+\gamma Q{\mathrm{max}}-Q(s,a)$の箇所で、これを0にするように学習します。

###特徴

方策オフ型なので、行動方策$\pi$とは別の方策（ターゲット方策）で$a^{\prime}$を選ぶ
行動価値関数$Q$の更新が行動方策に依存しない
行動価値関数$Q$の収束が早い。ただし、保証はされていない
行動価値関数$Q$を更新する際、行動価値の小さい探索結果は反映されにくい

###アルゴリズム
$\varepsilon$-greedy法を用いた、Q学習のアルゴリズムを示します。なお、これはE資格試験で出題されません。

パラメータ$\alpha,\varepsilon$を設定する。
各$s\in S,a\in A$について$Q(s,a)$を初期化する。ただし、エピソード終了時点は$Q(s,a)=0$とする。
Loop for each episode $T$
$\qquad$状態$s(1)$を初期化する。$t=1$とする。
$\qquad$Loop for each step $t$ in episode $T$
$\qquad\qquad$方策$\pi$に従い、行動$a(t)$を選択する。
$\qquad\qquad$行動$a(t)$を行い、即時報酬$r(t+1)$、状態$s^{\prime}$を得る。
$\qquad\qquad$式(3)に従い、$Q(s(t),a(t))$を更新する。
$\qquad\qquad$$s(t+1)=s^{\prime}$とする。
$\qquad\qquad$エピソードが終了したらループを抜ける。そうでなければ、$t:=t+1$とする。
$\qquad$Loop End
$\qquad$全てのエピソードが終了したらループを抜ける。そうでなければ、次のエピソードに移る。
Loop End

#Sarsa
###更新則
Sarsaにおける行動価値関数$Q$の更新則は式(4)で表されます。

Q(s,a):=Q(s,a)+\alpha\left(r+\gamma Q(s^{\prime},a^{\prime})-Q(s,a)\right)
\tag{4}

ただし、$\alpha \in [0,1]$はステップサイズです。
右辺の$Q(s^{\prime},a^{\prime})$は、状態$s(t+1)=s^{\prime}$において、__方策に従って実際に選ばれた次の行動$a(t+1)=a^{\prime}\in A$の行動価値__です。
TD誤差は$r+\gamma Q(s^{\prime},a^{\prime})-Q(s,a)$の箇所で、これを0にするように学習します。

###特徴

方策オン型なので、行動方策$\pi$と同じ方策（ターゲット方策）で$a^{\prime}$を選ぶ
行動価値関数$Q$の更新が行動方策に依存する
未経験の「状態と行動の組合せ」に対する行動価値関数$Q$は更新されない
行動価値関数$Q$の計算が不安定になりやすい
行動価値関数$Q$を更新する際、行動価値の小さい探索結果も反映されやすい

###アルゴリズム
$\varepsilon$-greedy法を用いた、Sarsaのアルゴリズムを示します。なお、これはE資格試験で出題されません。

パラメータ$\alpha,\varepsilon$を設定する。
各$s\in S,a\in A$について$Q(s,a)$を初期化する。ただし、エピソード終了時点は$Q(s,a)=0$とする。
Loop for each episode $T$
$\qquad$状態$s(1)$を初期化する。$t=1$とする。
$\qquad$$Q(s(t),a(t))$の方策$\pi$に従い、行動$a(t)$を選択する。
$\qquad$Loop for each step $t$ in episode $T$
$\qquad\qquad$行動$a(t)$を行い、即時報酬$r(t+1)$、状態$s^{\prime}$を得る。
$\qquad\qquad$方策$\pi$に従い、行動$a^{\prime}$を選択する。
$\qquad\qquad$式(4)に従い、$Q(s(t),a(t))$を更新する。
$\qquad\qquad$$s(t+1)=s^{\prime},a(t+1)=a^{\prime}$とする。
$\qquad\qquad$エピソードが終了したらループを抜ける。そうでなければ、$t:=t+1$とする。
$\qquad$Loop End
$\qquad$全てのエピソードが終了したらループを抜ける。そうでなければ、次のエピソードに移る。
Loop End

本記事は、E資格試験に出題される範囲に主に限定して解説しましたが、実装したほうが二つの方法の違いを数値的に確認することができます。

Q学習とSarsaの実装については、下記記事が参考になります。
[Q学習とSarsaの実装][link-3]
[link-3]:https://qiita.com/God_KonaBanana/items/dc5090899321bd0d6709

Q学習とSarsaの違いのイメージについては、下記記事が参考になります。
[Q学習とSarsaの違いのイメージ][link-4]
[link-4]:https://qiita.com/triwave33/items/cae48e492769852aa9f1

#おわりに
E資格向けの強化学習の価値ベースのアルゴリズムについて解説しました。
なお、上記は、2021年2月時点における内容であることにご注意ください。

[E資格試験に関する私の投稿記事リスト][link-1]