強化学習をざっと勉強した際のまとめです。
入門者の参考となれば幸いです。
強化学習とは
強化学習の位置付けはこのようになります。
【用語】
- 教師あり学習
- 教師データとして入力とその出力がある
- 回帰や分類問題
- 教師なし学習
- 教師データがない
- データの特徴を抽出したり、表現変換
強化学習では何をしていくかというと、
「将来の価値を最大化するような行動を学習」 していきます。
強化学習のモデル
強化学習の基本的な仕組みは次のようになっています。
以下の$t$は任意のステップを示します
- エージェント（意思決定者）: 意思決定と学習を行う主体
- 環境: エージェントが相互作用を行う対象
- 状態: 環境がエージェントの行動を反映した上で、エージェントに与える状況, $s_t$
- 行動: $a_t$
- 報酬: $r_t$
- 方策: $π_t(s, a)$:確率分布で表される行動戦略。任意の状態において、ある行動をとる確率を示す
まず環境からある「状態」$s_t$が与えられ
→ 「エージェント」が「方策」 $\pi_t(s,a)$ に従い「行動」$a_t$を選択し
→ 次のステップに「環境」から「報酬」$r_{t+1}$と「状態」$s_{t+1}$をフィードバックとしてもらう
という流れです。
マルコフ決定過程（MDP）
このように強化学習では
次状態$ s_{t+1}$(の確率)が 現在の状態$s_{t}$と選択した行動$a_{t}$によってのみ決定されること
報酬$r_{t+1}$(の確率)が 次状態$s_{t+1}$と現在の状態$s_{t}$と選択した行動$a_{t}$によってのみ決定されること
引用: ゼロから始める深層強化学習（NLP2018講演資料）/ Introduction of Deep Reinforcement Learning
を前提として話が進められます。
この前提を「マルコフ決定過程（MDP）」と呼びます
強化学習の解法
強化学習は上で示した図のようにモデル化されているわけですが、ではここで興味の対象はどこにあるでしょうか。
強化学習は「将来の価値を最大化するような行動を学習していくこと」であったわけなので、エージェントは将来得られる報酬が最も大きくなるような方策を知りたい訳です。
また、将来得られる報酬は現在価値で表すために $γ(0 \leqq γ \leqq 1)$ の割引率を掛けるのが自然です。以上より一連の報酬の和（累積報酬）は次のように表されます。
$$ R = \sum_{t=0}^{∞}γ^tr_{t+1} $$
強化学習においてはこの期待値を最大化するような方策が知りたいというモチベーションがあります。
そしてそのような方策を求めていくにあたって大きく2つの手法が存在します。
価値関数ベース
価値関数を推定し、間接的に最適な方策を求める方法のことです。
ある状態の価値（実際には行動しないとわからない価値）がどれほど良いかを表す関数を用い、価値の高い状態に移る行動をするような方策を求めていきます。
では「価値関数」とはどのようなものになるでしょうか？
最終的には、ある方策をとっているときに、ある状態においてある行動 を取った場合の価値、がわかればその価値が最大となる行動を選択すればよくなるはずです。
→ 従って「ある方策をとっているときに、ある状態においてある行動を取った場合の価値」を表す関数を求めたい
→ それは「ある方策をとっているときに、ある状態における価値」を表す関数において、特定の「行動」についてのところだけに注目すればよさそう
→ では「状態」をあらわす価値関数はどのようになるか。それは上にあるようにある状態で得られる累積報酬の期待値で表されそう
→ 従って、「ある方策をとっているときに、ある状態における価値」を表す関数は次のような式であらわされます（状態価値関数）。
$$ V^{\pi}(s) = \mathbb{E}\bigl[ \sum_{i=1}{\gamma^{i-1}r_{t+i}} \bigr| s\bigr] $$
→ よって、ある方策をとっているときに、ある状態においてある行動を取った場合の価値」を表す関数は次のような式であらわされます（行動価値関数）。
$$ Q^{\pi}(s,a) = \mathbb{E}\bigl[ \sum_{i=1}{\gamma^{i-1}r_{t+i}} \bigr| s, a\bigr] $$
ここまでの話は、「ある状態においてある行動を取った場合の価値、がわかればその価値が最大となる行動を選択すればよくなる」というところからスタートしているので、この行動価値関数の最適なもの（最も高い価値を得る行動をとることのできる関数）を実現する方策を最適な方策とすれば、学習の目的を果たせそうです。
また、最適な状態価値関数は次のような「最適ベルマン方程式」で示すことができます。
（ここでは最適ベルマン方程式とは何か、なぜそのような式変形となるかの説明はしません。）
$$ V^\ast(s) = \underset{a}{\max}\bigr[R_{(s,a)}{+}\gamma{\sum{p(s'|s, a)}{V^\ast(s')}} \bigr] $$
- $ s' $ : 次のステップでの「状態」
- $ p $ : 状態遷移確率、ある「状態」に遷移する確率
環境のパラメータが既知の場合
上のような最適ベルマン方程式を考えるにあたって、$R$ や $p$ がわかっている場合は次のようなステップにて $V$ の値を更新していくことができます。
1.すべての状態 s について V(s) を適当な値(ゼロなど)に初期化
2.すべての V(s) について以下の式を計算して値を更新
3.ステップ2を値が収束するまで繰り返す
環境のパラメータがわからない場合
この場合は実際に「行動」を実施し情報をサンプリングしていく必要があります。
価値関数ベースにおいては、最適な状態価値関数（ひいては最適行動価値関数）を導出することが目的であり、環境の情報が十分である場合はこれを価値反復法で求めることができます。不十分な場合はそれらの情報まず集めることから必要になるのでモンテカルロ法等の手法を用いて $p$ の情報を得て $V$ を更新していく必要があります。
（モンテカルロ法等を使用した場合でも、得られるのは情報は近似でしかないことに注意。完全なｐが得られた場合はその時点で価値反復法が使えます。）
以下に価値関数ベースの手法をいくつか紹介します。
モンテカルロ法
エピソード（オセロや将棋などでいう勝ち負けが決まるまでのこと）を繰り返しサンプリングし、それを利用して価値関数を推定していきます。
即ち価値関数は以下のようにして更新されていきます。
$$ V(s_t) \leftarrow V(s_t)+\alpha[R_t-V(s_t)] $$
- $R_t$ : tにおける報酬
- $\alpha$ : 学習率
TD法
モンテカルロ法がエピソードが完了してから価値関数を推定していたのに対し、TD法では各ステップ毎で価値関数を更新していきます。
また、モンテカルロ法では（上述の式が示すように）$R_T$ と $V(S_t)$ との差が小さくなるように価値関数を更新していきますが、ではTD法では次のようになります。
$$ V(s_t) \leftarrow V(s_t)+\alpha[r_{t+1}+\gamma V(s_{t+1}) -V(s_t)] $$
- $\gamma$ : 割引率
つまり「次のステップでの報酬と価値関数の和」をサンプルから得た価値関数の値として表現しそれと「現在の価値関数」との差によって更新していきます。
❇︎ モンテカルロ法やTD法を用いる場合に偏ったサンプリングをする可能性があるために局所解を取るリスクがあります、その回避方法として以下のような手法が用いられます。
- ε-greedy方策
- 行動価値関数Qに基づいて行動を行うのではなく一定の確率 ε ( < 1 ) の時にランダムな行動をとる手法
- ソフトマックス方策
- 行動価値関数Qが推定する価値が高い行動を選ばれやすくする。そうでないもの関しては選ばれにくくなるが全く選ばれないわけではない。
Q学習
TD法を行動価値関数の推定に適用したもので、ε-greedy方策を利用します。
更新式は次のようになります。
$$ Q(s_t,a_t) \leftarrow Q(s,a)+\alpha[r_{t+1}+\gamma maxQ(s_{t+1},a_{t+1}) - Q(s_t, a_t)] $$
上記式を見てみると、価値関数の値が最大となるような価値関数によって更新を行なっています。
これは実際にエピソードを進める際にとる行動方策（ε-greedy方策による行動方策）を更新時に用いるのではなく、あくまで最大なものを利用して推定値を更新することを示しています。このような手法を方策オフ型と呼びます。
【用語】
方策オン、方策オフ
- 価値関数の更新の際に仕様する方策が、評価対象の方策（実際に使用した方策）である場合に方策オン型といい、そうではない場合（例えば、価値関数が最大となるような行動方策を使うような場合）を方策オフ型といいます。
SARSA
以下のようにQ学習と同じような特徴を持ちます。
- TD法を行動価値関数に応用したもの
- ε-greedy方策を利用する
ただ、方策オン型の手法であるという点が異なっています。
更新式をみてみましょう。
$$ Q(s_t,a_t) \leftarrow Q(s,a)+\alpha[r_{t+1}+\gamma Q(s_{t+1},a_{t+1}) - Q(s_t, a_t)] $$
この式から分かるように、エピソードを進める際にとる行動方策（ε-greedy方策による行動方策）を更新時に用いており、このような手法を方策オン型と呼びます。
DQN
DQNでは、行動価値関数をニューラルネットワークを用いて近似し、また学習を安定化させるためにExperience replay（経験再生）や Double network などといった手法を用いるものです。
Experience replay（経験再生）
サンプルした情報をその時系列のまま利用すると、それぞれの情報が時系列として強い相関を持ったままとなり学習が上手くいかなくなります。それを防ぐため、サンプルを貯めておきそこからいくつか取り出してバッチ学習を行う。
Double network
Q学習では価値関数の更新時にmaxの値を用いて更新を行なっていましたが、これにより特定の行動価値が過大評価される可能性があります（極端に価値の高い行動がある場合特に）。これを防ぐために、メインとは別の価値評価を行う用のネットワークを作成し学習していく手法です。
| 関数の更新タイミング | 方策オン/オフ | 特徴 | |
|---|---|---|---|
| モンテカルロ法 | 試行が終了したとき | オン/オフ型それぞれあり | 局所解を取る可能性あり。 エピソードの開始から終端までで繰り返しサンプリングを行うため、エピソードの完了までに待たなくては計算可能とならない。 |
| TD法 | 各ステップごと | - | 局所解を取る可能性あり。 各ステップ毎の更新なので（＝エピソードの完了を待たないので）、エピソード全体に渡っての推定を行うモンテカルロ法と比べて、初期段階においては精度は欠ける。 |
| Q学習 | 各ステップごと | 方策オフ | TD法を行動価値関数に応用したもの ε-greedy方策を利用する 方策オフ |
| SARSA | 各ステップごと | 方策オン | TD法を行動価値関数に応用したもの ε-greedy方策を利用する 方策オン |
| DQN | 各ステップごと | 方策オフ | 最適な行動価値関数をニューラルネットワークを用いて近似関数を求めます。 |
方策関数ベース
（価値関数を経由せず）直接的に最適な方策を求める、現在の方策を改善していく手法です。
価値関数ベースでは「価値関数」を更新していったのに対し方策関数ベースでは、方策のパラメータを勾配ベースの手法により更新し方策そのものを改善していきます。
方策勾配法
方策関数ベースにて考える目的関数を $J(\theta)$ とします。
これは累積報酬やQ関数、状態価値関数を用いて表現され、これを最大化するのが目的です。
方策勾配法ではパラメータ $\theta$ の変化が目的関数にどう影響するか、というのを知りたいモチベーションがあり、その結果を任意の学習率を用いて$\theta$ を更新していきます。
ここで、方策モデルを $\pi_\theta(s,a)$ とすると、そのパラメータ $\theta$ の学習は次のように表すことができます。（$\delta$ は学習率）
$$ \theta \leftarrow \theta + \delta\nabla_\theta J(\theta) $$
また、「パラメータ $\theta$ の変化が目的関数にどう影響するか」というのは微分で表せますが、これは方策勾配定理によって以下のように表されます。
（ここでは方策勾配定理についての説明はしません。）
$$ \begin{eqnarray}
\nabla_{\theta}J(\theta) &=& E_s\Bigl[ \sum_{a}Q^\pi(s,a)~\nabla_\theta(a|s;\theta) \Bigr]\
&=& E_{(s,a)}\Bigl[ Q^{\pi_{\theta}}(s,a)~\nabla_{\theta}\log{\pi_{\theta}}(a|s) \Bigr] \end{eqnarray}$$
よって方策勾配のアルゴリズムは次のようなステップにまとめることができます。
この方策勾配による強化学習アルゴリズムは、大きく分けて以下のような３つの手順にまとめられる。
① 行動方策 $\pi_{\theta(s,a)}$ による行動
② 行動方策 $\pi_{\theta(s,a)}$ の評価
③ 行動方策 $\pi_{\theta(s,a)}$ の更新
この手順を繰り返すことで最適な方策を獲得していきます。
方策勾配定理によって表された式に $Q$ が出てきました。この $Q$ 関数の分散が大きいと学習が進みにくくなるため、同じような分布を持つ関数との差を取ることで分散を抑える、ということを行うことがありこの手法をベースラインを呼びます。
また、とりわけベースラインにおいて設定するバイアス項を $V$ とした関すをアドバンテージ関数と呼びます。
主なアルゴリズム
REINFORCE
方策勾配定理にて得られた式を見ると $Q$ が出てきています。
従ってそれを求める（近似すする）必要性があるのですが、このアルゴリズムではサンプリングを行い、その「報酬の平均値」で $Q$ を近似します。
Actor-Critic（アクター・クリティック）
REINFORCEが $Q$ を報酬の平均で近似していたのに対し、Actor-Criticではその $Q$ についても学習を行い更新していきます。