【深層学習】強化学習　重要なネットワーク(TD法、モンテカルロ法など)とその特徴

# 1.初めに
本記事では強化学習(Reinforcement Learning)について基本事項と、自分自身が引っかかったポイントを本記事にまとめた。
# 2.手法
###2-1.全体像
まず、価値ベースと方策ベースの２種類がある。

![スクリーンショット 2021-10-20 23.48.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/5003b5e9-f853-016c-7493-9f0471da5931.png)

その上で、
Suttonの強化学習の分類に基づき、
・動的計画法
・TD法
・モンテカルロ法
の３種類に大別している。
![スクリーンショット 2021-10-20 23.47.47.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/41117d45-e5c8-1ce5-6ab7-8ebd69f9ba02.png)

体系的に学ぶ場合は、
 1.価値反復法　(＊)
 2.方策反復法(＊)
 3.TD法(＊)
 4.モンテカルロ法(＊)
 5.Q学習(＊)
 6.SARSA(＊)
 7.DQN
 8.REINFORCE(＊)
 9.Actor-Critic(＊)
10.Multi-Step Learning法
11.TD(λ)法
を覚えれば良い。特に、(＊)については数式も覚えておくべきである。

そもそもの強化学習の基礎概念（エージェント、環境、方策など）は、以下のページの解説が参考になる。
[強化学習入門 ～これから強化学習を学びたい人のための基礎知識～](https://blog.brainpad.co.jp/entry/2017/02/24/121500)

日常用語と同じ単語が多く、価値が特に覚えづらいが、
　価値：長期的な収益達成確率（将棋で勝つ確率）
と理解するとよい。

価値を算出し、Qテーブルを更新し、方策を更新する、が基本方針。

Qテーブルのわかりやすい説明は以下のリンクに記載あり。
[【深層強化学習(DQN)】Q値で分かる深層強化学習](https://dajiro.com/entry/2020/05/18/091134)

### 2-2.TD法
・価値ベースの手法。正式名称はTemporal Difference Learning。
・報酬を毎ステップでサンプリング。
・より未来の情報を重要視。結果ができるまでのパターン数が多い（＝道のりが長い、寄り道が多い）ケースに重要。
・より未来の情報を使うほど真の値に近い、という仮定。
・モンテカルロ法のブートストラップ(サンプリング報酬R、状態価値関数Vt(s))からVt+1(s)を計算。
・デメリットとして、初期の価値が学習されにくい。
・行動をとるたびに、予測した報酬と、実際の報酬の差に基づいて価値関数に対する推定を更新する方法。
![スクリーンショット 2021-10-20 23.51.34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/d7d0d12f-f905-92ee-73c5-ae0f63b4076a.png)
<img width="400" alt="スクリーンショット 2021-10-21 0.00.22.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/866376c4-9685-44a6-500c-f0eb3a3eb7be.png">
　
### 2-3.モンテカルロ法
・価値ベースの手法
・報酬を毎エピソードでサンプリング。
・一連の行動後、一連の報酬から状態価値関数V(s)、状態行動価値関数Q(s,a)を推定。
・時刻tが有限で終了する（エピソディック、episodic）の時に有効。
・囲碁のように終わりが決まっている場合は使えるが、テトリスのように負けなければ続くゲームは不適。
![スクリーンショット 2021-10-20 23.49.36.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/7f9e73ca-c15c-7876-3de5-80000695e253.png)
<img width="500" alt="スクリーンショット 2021-10-21 0.00.34.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/ea0d2415-47fd-ffe2-92f5-b6c91674151b.png">

### 2-4.Q学習
・価値ベースの手法
・Policy-Off
　・TD法の状態行動価値関数Q(s,a)バージョン。
　・Q関数の収束が早い。すなわち、学習が安定する傾向がある。
　・エピソード更新方策と価値関数更新方策は異なる。
![スクリーンショット 2021-10-20 23.51.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/18d1f0aa-1a70-a6fe-5188-05c4c1da6ede.png)
<img width="600" alt="スクリーンショット 2021-10-21 0.01.00.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/8e7332a9-d5fe-23bd-dfaa-1884c3309466.png">

### 2-5.SARSA
・価値ベースの手法
・Policy-On
・正式名称はState–action–reward–state–action
・Q学習では、max Q がある程度正確に予測できる必要がある。
・例えば、囲碁の強化学習では、初期値（どの手をさすか）が不明。
・その時点での最適な選択を探索しない代わりに、方策(Policy)に従い更新(Policy-On)
・エピソード更新方策と価値関数更新方策は同じ。価値関数の更新にランダム性を取り入れて、局所解を回避する。
・行動価値Qを更新する際、Qが小さい探索結果も反映しやすい。
・しかし、計算が不安定になりやすい。
・経験していない[状態sと行動aの組み合わせ]に対するQ(s,a)は更新されない。
![スクリーンショット 2021-10-20 23.51.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/0302c40d-1adf-213e-9c9c-49e09f3efce8.png)

### 2-6.DQN
・価値ベースの手法。
・Qテーブルが複雑になる場合、例えばロボットの腕の位置など連続値の場合は、配列で表すことが困難になる。
・Q[state(s:状態)][action(a:行動)]=Q値(状態行動価値)

このテーブルで参照できない状態・行動を参照できるように、Q値を予測する関数をDeep Learningで表現したものがDQN。
・価値関数をパラメトリックに近似する方法。特に状態や行動のとりうる場合が多い場合。
・経験再生・・・経験(s(t),a,r,s(t+1))を逐次学習すると、前後関係も意図せず学習してしまう。経験をメモリに蓄積し、後でランダムに学習させる。
・Fixed Target Q-Network
・Reward Clipping・・・点数をスケール(-1,0,1)に標準化
・Huber Loss・・・MSEだと大きすぎる。DQNではHuber関数を使う。

### 2-7.REINFORCE
・方策ベースの手法。方策勾配法の１種。
![スクリーンショット 2021-10-21 0.05.26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/b97ffa5b-dbff-558d-474b-20edc6bb1d9e.png)


# 3.重要ワード
### 3-1.Bellmann方程式
・行動する際、「価値が最大」となるものを選択することが前提。
・価値が計算済みであることが前提。
<img width="600" alt="スクリーンショット 2021-10-21 0.03.20.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/01e69b49-7a32-4771-de6b-d8bb8543c8c2.png">

### 3-2.方策勾配定理
・どの行動をどのくらいの確率で選択すべき（方策）を直接予測することを方策勾配法という。
・その方策の関数（方策関数）のパラメータの変化が、どう利得に影響するかを把握する、すなわち、パラメータを最適化するように動かし、関数Jをパラメータで微分した結果を方策勾配定理と呼ぶ。
<img width="600" alt="スクリーンショット 2021-10-21 0.01.19.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/600ab397-ba1d-b819-6cfa-13f937d1de11.png">

### 3-3.ε-greedy方策
・確率εでランダムな行動aを選ぶ(ε<<1)：探索
・確率1-εで、現状のQ関数の計算した行動aをとる。：利用
・現時点で推定される最適な方策πから外れた方策も、確率的に選ぶことで局所解に陥ることを回避する。

### 3-4.ソフトマックス方策
・ボルツマン分布、Actorの行動選択がBoltzmann分布によるSoftmax手法である場合、Q(s,a)が高いほど、行動aが選ばれる可能性が高い。
・全行動の集合Aから、行動aを選ばれる確率π(s,a)
・探索と搾取・利用のトレードオフを1/Tで決定。
・1/T:各ステップでの行動選択のランダム性を調整する。価値関数から最適な「行動」を決める際、価値関数間の差を調整する量

### 3-5.トンプソンサンプリング
・ベイズ戦略の１種。事後確率に従って、行動をランダムに選択する。
・報酬和の期待値を最大にする。

### 3-6.UCB1アルゴリズム
・最初に取りうる行動を一通り試したのちに、信頼区間の上限の値を加味して、最良のケースでの報酬期待値から最適な行動を決定し実行する。


# 4.まとめ
強化学習といっても、深層以前と以後に大別でき、深層学習以前の手法でも多数の手法があり、特徴を理解することに非常に苦労した。
まずは、Suttonの３分類と価値ベース・方策ベースで大別して理解すると、追いかけやすい。
ようやく強化学習のスタートラインに立ったような気がする。

# 5.参考リンク
[方策勾配法の仕組みと学習のワークフロー](https://dajiro.com/entry/2020/05/19/170402)
[Policy Gradient Algorithms](https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html)
[A (Long) Peek into Reinforcement Learning](https://lilianweng.github.io/lil-log/2018/02/19/a-long-peek-into-reinforcement-learning.html#evolution-strategies)
[A Map of Reinforcement Learning](http://louiskirsch.com/maps/reinforcement-learning)<-個人的に、一番網羅的に整理されており参考になるWebsite。
[A Structural Overview of Reinforcement Learning Algorithms](https://towardsdatascience.com/an-overview-of-classic-reinforcement-learning-algorithms-part-1-f79c8b87e5af)