# 專題 強化學習
1. https://www.terasoft.com.tw/support/tech_articles/reinforcement_learning_a_brief_guide.asp
2. https://medium.com/%E9%9B%9E%E9%9B%9E%E8%88%87%E5%85%94%E5%85%94%E7%9A%84%E5%B7%A5%E7%A8%8B%E4%B8%96%E7%95%8C/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-ml-note-reinforcement-learning-%E5%BC%B7%E5%8C%96%E5%AD%B8%E7%BF%92-dqn-%E5%AF%A6%E4%BD%9Catari-game-7f9185f833b0
3. https://collegeplus.itri.org.tw/2021/02/12/%E5%BC%B7%E5%8C%96%E5%AD%B8%E7%BF%92%E7%9A%84%E7%B0%A1%E4%BB%8B%E5%8F%8A%E5%85%B6%E6%87%89%E7%94%A8%E6%83%85%E5%A2%83%E8%88%87%E9%AB%98%E6%95%88%E8%A8%93%E7%B7%B4%E6%B3%95/
4. https://en.wikipedia.org/wiki/Reinforcement_learning
5. https://zh.wikipedia.org/wiki/%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0
6. https://ithelp.ithome.com.tw/articles/10234272
7. https://darren1231.pixnet.net/blog/post/350072401-actor-critic-%E5%8E%9F%E7%90%86%E8%AA%AA%E6%98%8E
8. https://zhuanlan.zhihu.com/p/73083240
9. https://www.twblogs.net/a/5b7c53e02b71770a43da75bf
10. https://towardsdatascience.com/temporal-difference-learning-47b4a7205ca8
11. http://incompleteideas.net/book/RLbook2018.pdf
12. https://docs.ray.io/en/latest/index.html
13. https://github.com/dennybritz/reinforcement-learning
14. https://gym.openai.com/
15. https://iter01.com/546104.html
16. https://zh.wikipedia.org/wiki/%E8%B2%9D%E7%88%BE%E6%9B%BC%E6%96%B9%E7%A8%8B
17. https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE

## 激活函數
1. Sigmoid-https://zh.wikipedia.org/wiki/S%E5%87%BD%E6%95%B0

## 超參數
* 參數：就是模型的輸入。 比如，深度學習的權重，偏差等
* 超參數：就是用來確定模型的一些參數。超參數不同，模型是不同的(這個模型不同的意思就是有微小的區別，比如假設都是CNN模型，如果層數不同，模型不一樣，雖然都是CNN模型哈。)，超參數一般就是 在深度學習中，超參數有：學習速率，迭代次數，層數，每層神經元的個數等等。

## 隱馬爾可夫模型HMM
> http://www.huaxiaozhuan.com/%E7%BB%9F%E8%AE%A1%E5%AD%A6%E4%B9%A0/chapters/15_HMM.html
> https://zhuanlan.zhihu.com/p/85454896

隱馬爾可夫模型是關於時序的概率模型，描述由一個 隱藏的馬爾可夫鏈 隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀察而產生觀察隨機序列的過程。
> 隱藏的馬爾可夫鏈 => 狀態隨機序列 => 觀察隨機序列 (=> 生成)
* 基本定義
* Q = {q1,q2,...} => 所有可能狀態的集合
*

## model
* Q-learning:
* https://ithelp.ithome.com.tw/articles/10234661
* https://zh.wikipedia.org/wiki/Q%E5%AD%A6%E4%B9%A0
* 記錄下學習過的策略 => 採取什麼行動會有最大的獎勵值
* 找到一個可以最大化所有步驟的獎勵期望的策略
* Q: S × A → R
* 
* 演算法初始化階段，Q初始值為零(由設計者設計)。在時間t時，環境的狀態為S~t~，智慧型代理人選擇一個行為a~t~，並且獲得獎勵r~t~，環境因為代理人的行為導致狀態改變為新的狀態S~t+1~，此時便可根據以下公式更新Q值。演算法的核心為簡單的==利用過去與最近的權重平均值==來迭代更新數值。
* 其中 r~t~ 代表從狀態 s~t~ 到狀態 s~t+1~ 所得到的獎勵值,α 為學習率(0 < α < 1)。γ為衰減系數(0 < γ < 1)，
* γ 數值越大時，智慧型代理人便更加重視未來獲得的長期獎勵
* γ 數值越小時，智慧代理人便更加短視近利，只在乎目前可獲得的獎勵。
* Q-學習最簡單的實現方式就是將獎勵值存儲在一個表格（Q-table）中，但是這種方式受限於狀態和動作空間的數目。
* 

* SARSA: https://en.wikipedia.org/wiki/State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action
* 
* 基於策略的學習算法
* Q-learning 更新了對最佳狀態-動作值函數的估計Q^*^基於可用操作的最大獎勵。
* 學習率 (alpha) :
* 決定了在何種程度上學習的資訊覆蓋舊的資訊。因子為 0 將使代理不學習任何東西，而因子為 1 將使代理僅考慮最近的訊息。
* 折扣因子 (gamma) :
* 折扣因子決定了未來獎勵的重要性。折扣因子因子為 0 會使代理“投機取巧”或“短視”，例如[4]，僅考慮當前的獎勵，而接近 1 的因子將使其爭取長期的高獎勵。如果折扣係數達到或超過 1，則{\displaystyle Q}問 值可能會有所不同。
* 初始條件 ( Q ( s~0~ , a~0~ ) )
* 低初始值，也稱為“樂觀初始條件”，可以鼓勵探索：無論發生什麼動作，更新規則都會使其具有比其他替代方案更高的值，從而增加他們的選擇概率

* 蒙特卡羅學習(MonteCarlo)
* 所求解的問題本身具有內在的隨機性，藉助電腦的運算能力可以直接類比這種隨機的過程。
* 所求解問題可以轉化為某種隨機分布的特徵數，
* 比如隨機事件出現的機率，
* 或者隨機變數的期望值。
* 通過隨機抽樣的方法，以隨機事件出現的頻率估計其機率，或者以抽樣的數字特徵估算隨機變數的數字特徵，並將其作為問題的解。
* 執行
* 用蒙地卡羅方法類比某一過程時，需要產生各種機率分布的隨機變數。
* 用統計方法把模型的數字特徵估計出來，從而得到實際問題的數值解。

* 時間差異學習(Temporal difference learning)
* https://zhuanlan.zhihu.com/p/75246419
* https://zhuanlan.zhihu.com/p/73083240
* https://blog.csdn.net/coffee_cream/article/details/70194456
* https://www.twblogs.net/a/5b7c53e02b71770a43da75bf
* https://www.g8787856.me/
* https://www.g8787856.me/post/6
* https://zhuanlan.zhihu.com/p/73083240

import numpy as np
import pandas as pd
#------------------------------------------------------
class QLearningTable:
     def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9):
        self.actions = actions    # a list动作集
        self.lr = learning_rate   #学习率
        self.gamma = reward_decay #回报的衰减系数
        self.epsilon = e_greedy   #贪婪系数
        self.q_table = pd.DataFrame(columns=self.actions, dtype=np.float64) #定义q表
#------------------------------------------------------
     def choose_action(self, observation):
        self.check_state_exist(observation)
        # action selection
        if np.random.uniform() < self.epsilon:
            # choose best action
            state_action = self.q_table.loc[observation, :]
            # some actions may have the same value, randomly choose on in these actions
            action = np.random.choice(state_action[state_action == np.max(state_action)].index)
        else:
            # choose random action
            action = np.random.choice(self.actions)
        return action
#------------------------------------------------------
     def learn(self, s, a, r, s_):
        self.check_state_exist(s_)
        q_predict = self.q_table.loc[s, a]
        if s_ != 'terminal':
            q_target = r + self.gamma * self.q_table.loc[s_, :].max()  # next state is not terminal
        else:
            q_target = r  # next state is terminal
        self.q_table.loc[s, a] += self.lr * (q_target - q_predict)  # update
#------------------------------------------------------  
    def check_state_exist(self, state):
        if state not in self.q_table.index:
            # append new state to q table
            self.q_table = self.q_table.append(
                pd.Series(
                    [0]*len(self.actions),
                    index=self.q_table.columns,
                    name=state,
                )
            )

## 貝爾曼方程式

## 馬可夫決策過程
* 馬可夫決策過程是一個4元組{S , A , P~a~ , R~a~ }

## 馬可夫鍊(Markov Chains)
初始定義
* 狀態集 S: 包含所有狀態s,記做 S = {s0,s1,s2,...}
* 初始狀態 s0: 一開始的狀態
* 轉移矩陣 : 描述上一狀態如何轉至下一個狀態，記做 T(s,s')

### 馬可夫性質(Markov Property)
狀態的轉移只和現在的狀態有關，與過去無關。

> 有n個事件，以機率的方式描述
> => Pr(Sn|Sn-1,Sn-2,...) = Pr(Sn|Sn-1)

so 馬可夫鍊指在符合馬可夫性質的事件，可以使用Sn = S ‧ T^n^計算第n次的狀態。

import numpy as np
#兩種狀態 s0 s1
Matrix_trans = np.array([[0.9,0.1],[0.5,0.5]])

def Matrix_trans_step_n(n):
  return np.linalg.matrix_power(Matrix_trans,n)
for i in [1,5,10,100]:
  print(Matrix_trans_step_n(i))

轉移矩陣收斂 => 再加上其他狀態照樣收斂
But 除了要遵守馬可夫性質，還有
* a. 任意狀態皆能轉移至任意其他狀態(直接或間接)
* b. 狀態轉移不是固定周期
=>
* 只滿足 a => 最終不收斂，卡在重複循環中
* 只滿足 b => 只會在連通的部分收斂
* 都不滿足 => 在連通的狀態出現重複週期

## 馬可夫決策過程
初始定義
* 狀態集 S : 所有可能的狀態, 記做 S = {s0,s1,s2,...}
* 初始狀態 : s0
* 動作集 A: 所有可能動作, 記做 A = {a0,a1,a2,...}
* 轉移模型 T : 轉移至下個狀態之模型 T(s,a,s')
* 獎勵函數 R: 憑藉決策的結果, 記做 r(s,a,s')

### 獎勵函數
名詞定義
* 行動step: 表示完成「獲得狀態、決定動作、移動到新狀態」整個流程。
* 策略 (π)：將狀態與動作對應到機率的函數。表示某狀態下，採取某動作的機率，記做π (a|s)
* 回饋 (Gt):
* T 不趨近於無限:
* 
* T 趨近無限
* 
* so γ -> 0 or T -> ∞ 只有一個成立(存在)
* 
* 只在乎這次行動，可以獲得多少回饋。
* 
* 在乎多次行動後，可以獲得的回饋總量。
* 價值函數定義
在某個策略 π 之下，處於這個狀態 s 有多少價值，而價值是由未來可能獲得的回饋總和決定。
=> 透過狀態價值函數，得知一個狀態的價值。相同的，亦可評估一個狀態下，採取某動作的價值。
* 動作價值函數 (action-value function)
評估在某狀態下的某個動作的價值。

## 求價值函數
* 動態規劃 (Dynamic programming)
* 蒙地卡羅方法 (Monte Carlo method)
* Temporal-Difference learning

狀態價值函數：
動作價值函數：
## 動態規劃 DP
推導公式
我們將 G~t~ 代入狀態價值函數，得到
取出第一個回饋R~t+1~，得到
> 離散情況下，期望值的定義。
> 

將定義帶入
式子的組成，就是 「機率 x 該機率下的數值」
and
是狀態價值函數的定義
so
=> 貝爾曼方程
> 個人想法
> π(a|s): 表示s狀態下，採取動作a的機率
> p(s'|s,a): 從s經動作a到s'的機率
### 策略迭代
迭代的目標是狀態價值，而狀態價值受策略 (π) 影響。
=>
實現「根據現在的價值函數，估計新的價值函數。藉由重複獲得新的價值函數，逼近真實的狀態價值。」
* 以策略為單位進行更新，也就是說經過一次迭代，所有的狀態價值都會更新，因此稱為策略迭代。
* 所有新的價值函數，都是由舊的價值函數計算的，沒有先計算先更新的問題。
> eg 現在有狀態 A, B, C。更新 A 的價值後，若計算 B 時需要 A 的價值，仍使用舊的價值進行計算。

#### 策略增進 (Policy Improvement)
計算完狀態價值後，我們可以使用「狀態價值」與「動作價值函數」，計算在每個狀態下，每個動作的動作價值。
###### 貪婪法 (greedy method)
最好的動作，產生其他動作機率為 0
為了方便，將使用貪婪法的這個策略記作π'，並將透過貪婪法決定的動作記為π'(s)
現在有更好的動作，可以再回去更新狀態價值，如此一來，我們對狀態價值的判斷，就會比原本隨機動作的情況更準確。

so 回到策略迭代，透過找到每個狀態下最好的動作，我們可以找出最接近真實情況的狀態價值函數
重複這個過程的話，最終我們可以逼近各狀態的價值、各狀態下最適合的動作
=> 重複進行「策略評估」與「策略增進」這兩個步驟
> code: https://github.com/ChampDBG/LearnRL/blob/master/Policy_Iteration.py

### 價值迭代 (Value Iteration)
在策略迭代的方法中，使用「策略增進」來決定最佳的動作，並送到「策略評估」中。
價值迭代的方法中，我們在評估狀態價值時，不像「策略評估」只執行最好的動作，而是計算所有動作，並選擇價值最高者，做為新的狀態價值
初始狀態下(所有狀態價值皆為0)

while Δ > θ:
    for s in S:
        v_now = v
        v = T * (reward + v_now*γ)
        best_action = T*reward
        Δ = max(Δ,|v-v_now|)

> code: https://github.com/ChampDBG/LearnRL/blob/master/Value_Iteration.py

注意這邊不需考慮動作機率，因為我們只做最佳動作

### DP 優缺點
* 優點
* 更新所有狀態價值，是由價值函數的定義，衍伸出來的解決方案。
* 因此滿足這個條件(更新所有狀態價值)時，我們可以確保得到的狀態估計值，可以代表狀態價值，
* 缺點
* 更新所有狀態價值，計算量會隨著狀態數量而改變。
* 面對大數量，執行時間久
更新所有狀態價值，確保我們得到數值的意義，但也限制我們問題的大小。過於複雜的問題，可能不適合使用這個方法。
事實上，這個限制來自於動態規劃本身
> https://en.wikipedia.org/wiki/Curse_of_dimensionality

if 我們不更新狀態價值
= > 從數學上來說，不更新所有狀態價值時，將不滿足價值函數定義。所以計算出來的出來的數值不一定代表真實的狀態價值，造成動作決策錯誤。
### 迭代輪流更新狀態價值與策略
* 優點
* 我們可以確保評估價值與策略，是往同一個方向、有相同目標。
* 缺點
* 透過迭代更新，代表我們必須不斷與環境互動，以更新價值狀態與策略。想像以下情境

## 蒙地卡羅
使用大量模擬測試，逼近數值的方法。
估計價值函數時，需要找與價值函數有關，且可以使用大量試驗獲得數值
=> 例如: 回饋(Gt)

獎勵函數定義:
Gt 指的是從現在這個狀態，到整個過程結束時，我們可以獲得的回饋

回到價值函數定義 => 

透過重複試驗，取得多次的Gt => 再取平均 => 狀態價值函數
> eg.GridWorld (γ = 0.9):
> 1 -> 0
> 1 -> 5 -> 4 -> 0
> =>
> Gt = -1×1 + 0 = -1
> Gt = (-1×1)+(-1×0.9)+(-1×0.81) = -2.71
> V(s) = (-1 + -2.75)/2

狀態價值意義:
在DP中，動作價值定義
=> 變成遞迴形式
因為計算動作價值需要狀態價值，所以計算狀態價值有意義
But 蒙特卡羅並非用遞迴形式求解，而大量模擬求平均
* 逼近狀態價值，使用
* 起始狀態
* 動作
* 回饋
* 轉移矩陣
* 逼近動作價值
* 起始狀態
* 起始動作
* 回饋
* 轉移矩陣
* 決定初始動作 => 避免因為第一動導致結果難易度
### 蒙地卡羅控制
決策方式
1. 初始化動作價值函數、策略、以及回饋
2. 以 episode 為單位，開始收集各狀態下的狀態、動作 => 回饋，進行動作價值估算。
3. 再透過估算出的動作價值，決定「下次遇到相同的狀態時，執行具有最佳動作價值的動作」。
But 上述的策略，是建立在我們模擬準確的情況下
> eg.
> q(1, 左)、q(4, 上)、q(11, 下)、q(14, 右)，以上四個動作價值，不需要經過模擬，就已經知道是零。
> 選到這幾個狀態與動作時，我們之後就可以找到最好的策略。
> however
> 假設起始於狀態 2 、動作往左，並走以下路線
> 2 > 1 > 5 > 4 > 0
> 我們不會評價 q(1, 左)，而且 q(1, 下) 表現得也不錯，最終可能會收斂在 q(1, 下) 是最佳策略。
錯誤收斂
* Q(s,a) 的初始化
* 如果初始化是給予隨機範圍的負值，現在 q(1, 下) 大約為 -3 ，只要給予的隨機值小於 -3 ，未來就不可能選到 q(1, 左) 這個情況。
* 獎勵函數的給予機制

=> 在蒙地卡羅方法中使用貪婪法，可能不會收斂於最佳動作的情況。

### ε-greedy
貪婪法可能會不收斂於最佳動作 <= 讓最佳動作沒有被選到的機會
(不會被選擇到，所以不會被更新)
so ， 增加其他動作被選擇的機會 => 更新該動作價值
=> 間接讓最佳動作有機會被選到
=> 不採取貪婪法的選擇
=> 有機會採取其他選擇
主要差異在(c) 選擇a^ * ^的方法
* 1-ε+(ε/|A(s)|) 的機率採取貪婪決定的動作
* ε-(ε/|A(s)|) 的機率採取其他動作，各動作機率為(ε/|A(s)|)