強化学習は、意思決定主体であるエージェントと制御対象である環境の相互作用によって、最適方策を獲得するための学習手法です。強化学習にはさまざまなアルゴリズムが存在しますが、学習中における方策の更新方法によってそれらのアルゴリズムは、ValueベースとPolicyベースに大別されます。
前者のValueベースの手法は、現在の価値関数に基づいて方策を逐次更新していく強化学習手法です。一方、後者のPolicyベースの手法は、獲得報酬に基づいて方策自体を直接更新する強化学習手法です。今回は、Valueベースの手法に焦点を当てて説明します。
TD学習（Temporal Difference Learning）とは、現在の推定価値と実際の獲得報酬を比較し、それらの差分（TD誤差；Temporal Difference error）に基づいて正確な価値関数を推定する強化学習手法です。TD学習は強化学習の代表的な考え方であり、多くの強化学習手法の基礎となっています。TD学習の手法は、一度の価値更新に用いる実際の獲得報酬が\(\lambda\)ステップ先である場合、TD(\(\lambda\))法と呼ばれます。今回は、現在獲得した報酬だけを考慮するTD(0)法について説明します。
TD(0)法では、時刻\(t\)における状態\(s_t\)の価値\(V(s_t)\)を下式で更新します。
$$V(s_t){\leftarrow}V(s_t)+{\alpha}\left(r_{t+1}+{\gamma}V(s_{t+1})-V(s_t)\right)$$
ここで、\(\alpha(0<\alpha\leq1)\)は学習率（learning rate）と呼ばれる、状態価値の更新量を決定するパラメータであり、\(\gamma(0\leq\gamma\leq1)\)は割引率です。
Q学習（Q-learning）とは、状態行動対\((s,a)\)ごとのQ値をルックアップテーブル形式でそれぞれ学習することで、行動価値関数\(Q(s,a)\)を推定する強化学習手法です。具体的には、ある時刻\(t\)における状態\(s_t\)で選択した行動\(a_t\)に対して獲得する報酬\(r_t\)と、遷移先の状態\(s_{t+1}\)における最大の行動価値\(Q(s_{t+1},a_{t+1})\)を用いて、\(Q(s_t,a_t)\)を更新します。以上を踏まえ、更新式を以下に示します。
$$Q(s_t,a_t){\leftarrow}Q(s_t,a_t)+{\alpha}\left(r_{t+1}+{\gamma}\max_{a_{t+1}}Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right)$$
Q学習のアルゴリズムを以下に示します。
\(Q(s,a)\)を任意に初期化
エピソード終了まで繰り返し：
\(s\)を初期化
エピソードの各ステップまで繰り返し：
\(a{\leftarrow}s\)に対して\(\pi\)で与えられる行動
行動\(a\)を環境に与え、報酬\(r\)と次状態\(s’\)を観測
\(Q(s,a){\leftarrow}Q(s,a)+{\alpha}\left(r+{\gamma}\max_{a}Q(s,a)-Q(s,a)\right)\)
\(s{\leftarrow}s’\)
\(s\)が終端状態であれば繰り返しを終了
最終エピソードであれば繰り返しを終了
Output：\(Q(s,a)\)
SARSA（State Action Reward State Action）とは、タプル\(\left(s,a,r,s’,a’\right)\)を用いて行動価値関数を更新する強化学習手法です。SARSAによる行動価値関数の更新式は下式で表現されます。
$$Q(s_t,a_t){\leftarrow}Q(s_t,a_t)+{\alpha}\left(r_{t+1}+{\gamma}Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right)$$
ここで、状態\(s_t\)と\(s_{t+1}\)でとる行動\(a_{t}\)と\(a_{t+1}\)は、\(\epsilon\)-greedy法などの方策に基づいて決定します。
SARSAのアルゴリズムを以下に示します。
\(Q(s,a)\)を任意に初期化
各エピソードに対して繰り返し：
\(s\)を初期化
\(a{\leftarrow}s\)に対して方策\(\pi\)が与える行動
各ステップに対して繰り返し：
行動\(a\)を環境に与え、報酬\(r\)と次状態\(s’\)を観測
\(a'{\leftarrow}s’\)に対して方策\(\pi\)が与える行動
\(Q(s,a){\leftarrow}Q(s,a)+{\alpha}\left[r+{\gamma}Q(s’,a’)\right]\)
\(s,\ a{\leftarrow}s’,\ a’\)
\(s\)が終端状態であれば繰り返しを終了
最終エピソードであれば繰り返しを終了
Output：\(Q(s,a)\)
Q学習とSARSAの違いは、選択した行動と更新式の関係にあります。Q学習アルゴリズムの5行目、SARSAアルゴリズムの4・6行目の通り、状態\(s\)における行動\(a\)を方策\(\pi\)に基づいて選択する点は二つの手法で共通です。ここで、Q学習の更新式と、SARSAの更新式を示します。
- Q学習の更新式：\(Q(s_t,a_t){\leftarrow}Q(s_t,a_t)+{\alpha}\left(r_{t+1}+{\gamma}\max_{a_{t+1}}Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right)\)
- SARSAの更新式：\(Q(s_t,a_t){\leftarrow}Q(s_t,a_t)+{\alpha}\left(r_{t+1}+{\gamma}Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right)\)
上式の通り、SARSAでは更新量を決定する第2項中の行動が方策\(\pi\)に基づいて選択されたものであるのに対し、Q学習では現在の行動価値関数を最大化する行動が第2項中で用いられています。つまり、SARSAでは方策に基づいた行動を更新に用いており、Q学習では用いていないといえます。このことから、SARSAはon-policy（方策オン型）の強化学習手法、Q学習はoff-policy（方策オフ型）の強化学習手法とよばれます。
Actor-Criticは、観測した状態から行動を決定する役割をもつActor（行動器）と、状態を評価する役割をもつCritic（評価器）を独立して存在させる強化学習手法です。
Criticは、現在の状態価値関数\(V(s)\)と観測した報酬\(r_t\)に基づいてTD誤差\(\delta_t\)を計算し、観測状態\(s_t\)の価値\(V(s_t)\)を更新します。時刻\(t\)におけるTD誤差\(\delta_t\)の計算式と価値\(V(s_t)\)の更新式を以下に示します。
$$\delta_t=r_t+{\gamma}V(s_{t+1})-V(s_t)$$
$$V(s_t){\leftarrow}V(s_t)+{\alpha}\delta_t$$
Actorは、Criticが計算したTD誤差を用いて方策を更新します。具体的には、ステップサイズパラメータ\(\beta\)とTD誤差\(\delta_t\)を用いて、下式で表現する行動優先度（action preference）\(p(s_t,a_t)\)に基づいて方策\(\pi\)を更新します。
$$p(s_t,a_t){\leftarrow}p(s_t,a_t)+{\beta}\delta_t$$
例えば、Actorがsoftmax行動選択を行う場合、方策の更新式は下式で表現されます。
$$\pi_t(s,a)=P(a_t=a|s_t=s)=\frac{\exp\left(p(s,a)\right)}{\sum_{a_k}\exp\left(p(s,a_k)\right)}$$
参考文献
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An Introduction. The MIT Press, 1998.