はじめに

• 強化学習を学んだ際のメモとして，いろいろな手法を分類して紹介します。各手法の実装や詳細は，他の方の記事を参照してください。本記事は，[1]森村哲郎『強化学習』講談社 を中心として記載しています。
• 末尾の参考文献をもとに，できるだけ簡素に記載するように心がけたので，厳密性に欠ける可能性があります。あくまで手法全体を俯瞰するフローチャート的な立ち位置としてご参考ください。
• 明らかな誤りがあった際にはご連絡ください。
• 記事の基本的な流れは文献[1]をかなり参考にしています。著作権等の問題が発覚した場合には記事を取り下げますので，ご了承ください。文献[1]は数理的に非常に厳密に記載されており，難しいですが一読どころか百読くらいの価値がありますので，ぜひご購入の検討を (ステマ)。

実装や簡単な説明は，「Pythonで学ぶ強化学習」のgithubがとてもわかりやすいです。
https://github.com/icoxfog417/baby-steps-of-rl-ja

章立ては以下の通り。
1. 環境が既知の場合
2. 環境が未知の場合1 - バッチ学習編
3. 環境が未知の場合1 - オンライン学習編
4. 環境が未知の場合2 - モデルベース戦略
5. 関数近似手法
6. 部分観測マルコフ決定過程の場合

事前準備

次のように文字を定めます。

次に，章立ての詳しい内容を説明します。

環境モデルが既知：
以下の変数のすべてがわかっている場合を指します。
$(s,a,g(もしくはr),p)$
すなわち，「ある状態 $s_t$ で行動 $a_t$ をとると，確率 $p$ で状態 $s_{t+1}$ に遷移し，(報酬関数 $g$ に基づき) 報酬 $r_t$ を得る」ことがかわっている場合。

環境モデルが未知の場合1：
以下の変数の関係が分かっている場合を指します。
$(s,a,r)$
すなわち，「ある状態 $s_t$ で行動 $a_t$ をとると，状態 $s_{t+1}$ に遷移し，報酬 $r_t$ を得る場合がある」ことがかわっている場合 (S×A->S×R)。遷移確率は分かりません。

環境モデルが未知の場合2：
$(s,a,r)$ の他に，状態遷移確率や報酬関数があれば，環境モデルが既知と言えるので，これを推定しよう，という手法になります。また，更に難しいタスクとして，$(s,a)$ しかわからない場合も考えます。

部分観測マルコフ決定過程
通常の強化学習は，マルコフ決定過程 (Markov Decision Process; MDP) に該当し，すべての状態が観測可能であり，報酬や行動の入力が存在することが前提です。MDPとは異なり，すべての状態が観測できるわけではない場合を部分観測マルコフ決定過程 (Partially Obserbable MDP; POMDP) と呼びます。

1.環境モデルが既知の場合

この場合，プランニングと呼ぶことが多いようです。
強化学習の根本には，マルコフ決定過程とベルマン方程式の考え方が存在します。
本記事では詳説しませんので，こちらを参照してください。
https://qiita.com/triwave33/items/5e13e03d4d76b71bc802

価値反復法

価値反復法では，以下のことを行います。実装や定式は，参考文献[3]が分かりやすいです。

(1)価値関数 $V(s)$ を最大化ような最適価値関数 $V^{\prime}(s)$ を求める
(1-a) 価値関数を更新する

V^{\prime}(s_t) = \max_a(r(s_t,a_t) + \gamma \sum_{s_{t+1}} p(s_{t+1}|s_t,a_t)V(s_{t+1})

(1-b) 更新前後の差が一定値を下回れば，次の(2)へ進む
(2)その際の方策 (最適方策 $\hat{\pi}$) を求める。具体的には，ある状態 $s_t$ では， $V^{\prime}(s)$ が最大になるような$a_t$を選べばよい

方策反復法

価値反復法では，価値関数を最大化した後に最適方策を求めました。こちらの方法では，方策に関するベルマン方程式と，方策に関する価値関数 $V_{\pi}$ を利用します。具体的には以下の通りです。
(1)(方策評価) ベルマン方程式から，価値関数 $V_{\pi}$ を求める
(2)(方策改善) 計算した価値関数をもとに方策 $\pi$ を改善する
(3) 更新前後の差が一定値を下回るまで，(1)と(2)を繰り返す。

2. 環境が未知の場合1 - バッチ学習編

バッチ学習をするために，$(s_t,a_t,s_{t+1},r_t)$ から成る履歴データが大量に存在することを前提とします。

ベルマン方程式からのアプローチ

上記の大量の履歴データをもとに，価値反復法を方策反復法と同様のプロセスを行います。

探索によるアプローチ

履歴データをもとにすれば，どのような状態に遷移するかを表現する木を描くことができます(深さ方向が時間に該当しますね)。これらを探索することで，最適方策を見つけることができます。
- 幅優先探索
- 深さ優先探索
- スパースサンプリング法 (確率的な幅優先探索)
- UCT法
- モンテカルロ木探索
などがあります。

3. 環境が未知の場合1 - オンライン学習編

逐次手に入る，$(s_t,a_t,s_{t+1},r_t)$ の情報をもとにして強化学習を行います。

TD(temporal difference)法

本手法では，以下のような値，TD誤差 $\delta$ を利用します．

\delta_t = r_t +\gamma \hat{V}(s_{t+1})-\hat{V}(s_t)

TD誤差は，あるステップとその次のステップにおける推定価値関数の差と報酬の和として定義されます (注：環境が既知の場合の価値関数と区別して，推定価値関数と表現しています)。これを利用して，推定価値関数を適当な初期値からスタートして以下のように逐次更新します．
まず，方策 $\pi(a|s)$ に従って，行動 $a_t$ をとり，その結果として，報酬 $r_t$ と次の状態 $s_{t+1}$ を観測します．
そして次の式で推定価値関数を更新します．

\hat{V}(s_t)　= \hat{V}(s_t) + \alpha _t \delta_t

$\alpha _t$ は学習率です．$t=t+1$ としながら，何らかの終了条件(最大ステップ数など)まで繰り返します．

Q学習　　

$Q(s,a)$ を使うという点を除けばTD法とほぼ式は同一です。TD法の場合と同様に，推定行動価値関数 $\hat{Q}(s,a)$ として表記します。
一般には，方策は$\hat{Q_t}$に依存したものを設定します。すなわち，$\hat{Q_t}$ が高くなるような行動をする，ということです。方策 $\pi(a|s;\hat{Q_t})$ に従って，行動 $a_t$ をとり，その結果として，報酬 $r_t$ と次の状態 $s_{t+1}$ を観測します．そして以下のようにして，推定行動価値関数を更新していきます．

\delta_t = r_t +\gamma \max_{a^{\prime}\in A}\hat{Q}(s_{t+1},a^{\prime})-\hat{Q}(s_t,a_t)\\
\hat{Q}(s_t,a_t)　= \hat{Q}(s_t,a_t) + \alpha _t \delta_t

SARSA法

ほとんどQ学習と同じです．学習の式を見てみましょう．

\delta_t = r_t +\gamma \hat{Q}(s_{t+1},a_{t+1})-\hat{Q}(s_t,a_t)\\

\hat{Q}(s_t,a_t)= \hat{Q}(s_t,a_t) + \alpha _t \delta_t

どこが違うのかというと，1つ目の式の右辺2項目です．Q学習では，とりうる行動から最も $Q$ の高くなる行動を選ぶということになっています．しかし，SARSA法では，$a_{t+1}$ となっています．すなわち，Q学習だと「とりあえずQが大きくなる行動を選択」しますが，SARSA法だと「方策に基づいて生成した次の行動を利用」しています。
方策には，収集したデータを用いて次の行動も利用する「行動方策」と，Qから求められる「目的方策」が存在します。Q学習ではこれらが不一致の可能性がありますが，SARSAでは一致します。前者のような場合を前者のような手法を方策オフ型，後者のような手法を方策オン型と呼びます．

アクター・クリティック法

アクター・クリティック法は，SARSA法と似ており，方策オン型の手法です．SARSA法では，$Q$ という単一の指標を用いて方策評価と方策改善を行いました．これを分離させたものが本手法であると直感的には捉えられます．
アクター(方策)とクリティック(方策評価)という2つのモジュールを用意し，クリティックが方策改善信号をアクターに送り，アクターはそれによって方策を更新する，というプロセスです．こういった方針のアルゴリズムによって成り立つ手法を総称してアクター・クリティック法と呼んでいます．

アクター・クリティック法の1つとして，TD誤差を利用するものが存在します．クリティックは以下のようにしてTD誤差を計算し，$V$ を更新します．

\delta_t = r_t +\gamma \hat{V}(s_{t+1})-\hat{V}(s_t)\\

\hat{V}(s_t)　= \hat{V}(s_t) + \alpha_t^{critic} \delta_t\\

このTD誤差をアクターに送信して，$q$ を次のように更新します．

q(s_t,a_t)= q(s_t,a_t) + \alpha_t^{actor} \delta_t

4. 環境が未知の場合2 - モデルベース戦略

「モデルベース」とは，不明なパラメタ，すなわち状態遷移確率などを陽に求めようというアプローチを指します。(これまでのアプローチでは，わからないものは求めずに取り組んできましたね。)

ここでは，
(a) バッチ型
(b) オンライン型
(c) 逆強化学習
に分けて紹介します。

バッチ型

やることはシンプルで，大量の履歴データからモデルを推定し，価値反復法などを用いてプランニングします。
状態遷移確率の求め方を考えましょう。最も簡単にするとしたら，ある $[s_t,a_t,a_{t+1}]$ の組み合わせが全体に占める割合を求めればよさそうです (データが存在しない部分については，恣意的に決める必要があります)。
他にも，最大事後確率の最大化を利用したり，ベイジアン強化学習を行ったり…とあります。

オンライン型

1回1回の動きをもとに，推定したいパラメータを更新していきます。
代表例としてR-max法があります。こちらの論文を参照してください。
https://jmlr.csail.mit.edu/papers/volume3/brafman02a/brafman02a.pdf

逆強化学習

環境が未知の場合1との違いは，「ある状態$s_t$で行動$a_t$をとると，状態$s_{t+1}$に遷移することはわかるが，報酬まではわからない」ということです。
逆強化学習では，「熟達者の動きをもとにパラメータを推定し，もとまったパラメータから強化学習する」ということを行います。こちらの記事がすごくわかりやすいです。
https://qiita.com/shiro-kuma/items/aaab6184aea7d285b103

5. 関数近似手法

　例えばQ学習の場合，$Q(s,a)$ を実装する上では，$Q[s][a]$ というような配列 (テーブル) が利用できます。しかし，状態の数や行動の数が膨大になったら，大量のメモリを消費しますし，$s$ が連続値の場合に適用できません(実際には，離散化してQテーブルを使うこともあります)。
　ところがなんと，このQを何らかの関数で表現することで，メモリを節約できます。関数の数式さえ覚えておけば，あとはsやaの値を入力するだけでQが求まるからです。こういった手法を，関数近似と呼びます。
基本的な場合，価値関数 $V(s)$，重みベクトル $w$，予め定めておく基底関数のベクトルを $\phi(s)$ として，$V_w(s) = w^T\phi(s)$ という線形変換を想定します。基底関数は定まったものなので，$w$ を学習していく必要があります。

ここでは，更に次の3つに分けて紹介します。
(a) 価値関数の近似(1) テーブル法の拡張
(b) 価値関数の近似(2) 損失関数の利用
(c) 方策の近似

深層強化学習もこの分野ですが，ここでは省略します。
概略は　https://book.mynavi.jp/manatee/detail/id=89691
サンプル実装として，https://github.com/YutaroOgawa/Deep-Reinforcement-Learning-Book
を参考にしてください。
本節以降では，$\hat{Q}$ や $\hat{V}$ も簡単のため $Q, V$ として表記します。

(a)と(b)の違いをざっくりいうと，これまでの数式をちょっと弄ればたどり着ける方法が(a)，新たな概念の導入が必要なものが(b)という認識です。
数式は持ち出さないので，詳細は別途検索するか[1]を参照してください。

価値関数の近似(1) テーブル法の拡張

簡単のため，価値関数 $V_w(s)$ に関するベルマン方程式を $BV_w(s)$ と表記します。

(i) バッチ型

価値反復法からわかるように，$V_w^{\prime}(s) = BV_w(s)$ の更新をできるだけ小さくしたいので，$\min_w \sum_s (BV_w(s) - V_w(s))^2$ (ベルマン残差) を解こう，というのが自然な発想です。
(ベルマン残差を用いた学習は，テーブル法からは少し離れるので，「損失関数の利用」に記載します。)
「状態数が多い場合に関数近似を行う」ので，状態数に依存する形は望ましくないこともあります。そこで，かわりにデータセットの数に着目した学習を紹介します。
適合価値反復法(fitted value iteration)では，n個目のデータセット $[s_{n},r_{n},s_n^{\prime}]$ に注目して
(1) $V_n^{\prime} = r_n + \gamma V_w(s_n^{\prime})$ を計算
(2) $w = arg \min_w \frac{1}{N} \sum_{n=1}^N (V_n^{\prime} - V_w(s_n))^2$として更新
を繰り返します。
価値関数$V$の替わりに行動価値関数$Q$を用いる適合Q反復法(fitted Q iteration)も存在します。

(ii) オンライン型

$V_w$ の変化量をもとに，$w$ をオンライン学習させます。すなわち，

w = w + \alpha \delta_t \nabla_w V_w(s_t)\\
\delta_t = r_t +\gamma \hat{V_w}(s_{t+1})-\hat{V_w}(s_t)

これを，近似TD法と呼びます。TD法の式と見比べると，非常に類似しています。
同様にして，Q学習やSARSA法の式のような形として，近似Q学習や近似SARSA法が存在します。

w = w + \alpha \delta_t \nabla_w Q_w(s_t,a_t)\\
\delta_t^Q = r_t +\gamma \max_{a^{\prime}} Q_w(s_{t+1},a^{\prime})-Q_w(s_t,a_t)\\
\delta_t^{SARSA} = r_t +\gamma Q_w(s_{t+1},a_{t+1})-Q_w(s_t,a_t)

実装の流れについては，日本語記事では以下が参考になります。
実装の正確性については，(私はプロでないので) 担保はできません。
https://shirakonotempura.hatenablog.com/entry/2019/03/16/040026

価値関数の近似(2) 損失関数の利用

損失関数として，ベルマン残差 (Bellman Residue) や射影ベルマン残差 (Projected Bellman Residue) が利用されます。

L_{br} = \sum_s \mu (s)(BV_w(s)-V_w(s))^2\\
L_{pbr} = \sum_s \mu (s)(\Gamma (BV_w(s))-V_w(s))^2\\
\Gamma(v) = arg\min_{V_w} \sum_s \mu (s)(v-V_w(s))^2\\

最小2乗誤差や勾配降下法を利用して，$w$を学習します。
・残差勾配法 (residual gradient algorithm)
・最小二乗TD法 (least square temporal-difference)
・LSTDQ法
・GDT法,GDT2法 (gradient temporal-difference)
などが存在します。

方策の近似

アクター・クリティック法では，Q関数を用いて方策を更新しましたが，パラメタ$\theta$を導入し，これを勾配降下で学習する，方策勾配法 (policy gradient learning)が存在します。
方策勾配法として，モンテカルロ方策勾配法，アクター・クリティック方策勾配法などが存在します。
こちらのスライドがわかりやすいので，参照ください。
https://www.slideshare.net/RyoIwaki/ss-87924430

6. 部分観測マルコフ決定モデルの場合

後日更新したい…

参考文献

(全体) 森村哲郎『強化学習』講談社
(実装例) https://github.com/icoxfog417/baby-steps-of-rl-ja
(MDPとベルマン方程式) https://qiita.com/triwave33/items/5e13e03d4d76b71bc802
(価値反復法と逆強化学習) https://qiita.com/shiro-kuma/items/aaab6184aea7d285b103
(深層強化学習の概要) https://book.mynavi.jp/manatee/detail/id=89691
(深層強化学習の実装例) https://github.com/YutaroOgawa/Deep-Reinforcement-Learning-Book
(深層強化学習の発展) https://www.slideshare.net/juneokumura/dqnrainbow
(近似Q学習) https://shirakonotempura.hatenablog.com/entry/2019/03/16/040026
(方策勾配法) https://www.slideshare.net/RyoIwaki/ss-87924430
(すごいサイト) http://yagami12.hatenablog.com/entry/2019/02/22/210608