# [DL] Q-Learning 簡介
###### tags: `Deep Learning`

## 四元素：Agent、環境狀態、Action、Reward

**強化學習的目的：找到一個最好的Action，可讓Reward最大。**


1. Agent大腦：(接收State&Reward)
* 接收State(狀態)：
* 將Environment(環境)每一個時間點的Observation(觀察)的集合當作環境的狀態(State)
* 因為Agent不一定能得到Environment的所有資訊，比如機械臂上的攝像頭只能得到某特定角度的畫面。因此，只能用Observation來表示Agent獲取的感知資訊。
* Policy(策略)：
* 從State(環境的狀態)跟Reward(獎勵)再去選擇一個最好的Action(動作)
* 做出Action去改變Enviroment時，會得到Reward來學習那次的Action是不是好的。
2. State：[0, 0, -10, 10]
* 觀察 Observation 的集合
* Agent的所處的狀態 State = Agent可到達的位置，有4個。
4. Environment(環境)：
* 一個環境在不同的狀態下會有不同的情況，並將這些情況告訴大腦，讓大腦可以去學習。
* 會接收Agent執行的Action(動作)，並吐出Reward跟Observation給Agent。
5. Reward
* Agent執行了Action，Environment進行互動後，Environment會發生變化
* 變化的好與壞就用Reward來表示。

---

## MDP (Markov Decision Process) 馬可夫決策過程
> 只看現在State

(一) $St = (a1,o1,r1, ....at-1, ot, rt)$
現在的狀態 = 現在+以前的action，observation，reward

(二) 

* **重要觀念：未來只取決於當前**
1. 估計下一個狀態(St+1)，要把過去所有狀態(S1~St)考慮進去
2. (State,Action)=Value、 (s1,a1)=-2
每組(狀態-動作)，都有一個值表示，(s1,a1)=-2
需要建立一個超大的Q表儲存(State,Action)=Reward(Value)
但這樣模型便會非常的大，訓練會很困難
3. 假設下一個狀態只跟**現在狀態**有關，則可縮小模型

把強化學習想像成是MDP的一種模型：
從現在的狀態來知道未來的狀態，要找到未來最好的動作也變得有可能了

## 公式推倒
### (一)Value function 價值函數
> 看整個State，等所有未來的時間都結束

==$G_t = R_{t+1} + \lambda R_{t+2} + … = \sum_{k=0}^\infty\lambda^kR_{t+k+1}$==
Future Reward: 當前狀態對未來reward的期望

有了以上Reward(Value)值，我們可以判斷什麼是好的State以選擇最優策略
* 問題：只看**現在**狀態的Reward，並不能判定哪種策略更優
* 解法：去看**整個**狀態序列(過去~現在)的 $λReward$ 最大

$R$：未來每一個時間點的Reward相加
$λ$：discount factor，當下的reward最有價值，越未來所給的reward影響是越小，

### (二) State-Value function 狀態價值函數
> 看整個State，不用等未來的時間都結束

* 問題：要等整個過程結束，才能計算出Gt
Gt：獲取所有的reward來計算出每個狀態的Return
* 解法：用value function 來表示一個狀態未來的潛在價值v ( s )

Bellman方程：期望的Reward越高，Value也就越大
\begin{align} v(s) & = \mathbb E[G_t|S_t = s] \\ & = \mathbb E[R_{t+1}+\lambda R_{t+2} + \lambda ^2R_{t+3} + …|S_t = s] \\ & = \mathbb E[R_{t+1}+\lambda (R_{t+2} + \lambda R_{t+3} + …)|S_t = s] \\ & = \mathbb E[R_{t+1} + \lambda G_{t+1}|S_t = s] \\ & = \mathbb E[R_{t+1} + \lambda v(S_{t+1})|S_t = s] \end{align}

$v(s)$：當前value function(狀態的價值)和
$v(S_{t+1})$：下一步狀態的Value function + $R_{t+1}$：下一步的Reward有關。

### (三)　Action-Value function 動作價值函數
> 看整個State，不用等未來的時間都結束
> 關心某個State下的不同Action(動作)的價值，就可選擇Value最大的一個Action執行。

在Policy(策略)下的Action-Value(動作價值)：
\begin{align} Q^\pi(s,a) & = \mathbb E[r_{t+1} + \lambda r_{t+2} + \lambda^2r_{t+3} + … |s,a] \\ & = \mathbb E_{s^\prime}[r+\lambda Q^\pi(s^\prime,a^\prime)|s,a] \end{align}

公式上 **π = Policy(策略)**
前面有提到，Policy是根據當前的State跟Reward中找到一個最好的Action
Policy的決定就會跟Action-Value function有關
而前面的State-Value function則不一定依賴於Policy。

### (四) Optimal value function 優化價值函數
==$Q^*(s,a) = \mathbb E_{s^\prime}[r+\lambda \max _{a^\prime}Q^*(s^\prime,a^\prime)|s,a]$==
最好的Action-Value functioNn = 所有Policy下的Action-Value function的**最大值**

---

## Q-Learning決策
1. 狀態s1
在我的記憶Q表格，Q(s1, a1)=-2 < Q(s1, a2)=1，選擇a2作為下一個行為
2. 狀態更新成s2
在我的記憶Q表格，Q(s2, a1)=-4 < Q(s2, a2)=2，選擇a2作為下一個行為
3. 狀態更新成s3
.... 重複上面的決策過程....

## Q-Learning更新


## 如何選擇動作

### epsilon-first：平衡探索與開發

#### (一) 定義
**Policy(State+Reward)** →Action
我們需要使用某一個Policy來生成Action(動作)，有以下兩種方法

#### (二) 探索(Exploration) vs. 利用(Exploitation)
先試玩一段時間，累積足夠次數的探索(Exploration)
累積足夠經驗後，就可進行利用(Exploitation)
* 法一：**探索(Exploration)**：通過多次觀測推斷出一道菜做的好吃的概率
* **隨機探索**：生成一個Action(動作)
* 優點：有利於更新Q值，獲得更好的policy。
* 缺點：若＂探索太多＂，真正得到的報酬無法極大化
* 法二：**利用(Exploitation)**：已知所有的菜做的好吃的概率，該如何推薦
* 利用**選擇最優策略**：greedy policy貪婪策略
* 優點：根據當前的Q值，讓Actor每次選擇最優的決策，最大化長期獎勵
* 缺點: 不好更新出更好的Q值
若極大化＂選擇最優策略＂，最好的機器會頻繁被選擇→重近利，不顧長遠回報

#### (三) 經驗討論：優點 & 缺點
* 優點
* 經驗足夠：已經推薦了k遍（獲取了k次反饋），我們就可以算出菜做的好吃的概率
* 缺點
* 經驗不足：初步的學習中，Q值會不准確
* 經驗足夠：學習一段時間後，機器人的路線會固定，則無法對環境有效探索。

### epsilon-greed：邊學邊賺
#### (一)定義 : 貪婪度 greedy(決策策略)

因此我們需要一種辦法，來解決如上的問題：
1. 希望能夠在盡力「開發Exploitation」的同時：一部分的概率隨機選擇動作
2. 偶爾也試著去「探索Exploration」：一部分的概率按照最優的Q 值選擇動作

#### (二) 探索(Exploration vs. 利用(Exploitation)

* **隨機-探索(Exploration) ϵ=10%**
* 探索(概率小)：有時選擇隨機選項
* **最佳化-利用(Exploitation) 1-ϵ=90%**
* 利用(大多數)：選擇當前最佳選項（貪婪）
#### (三) epsilon : 一般是一個很小的值，作為選取隨機動作的概率值
* 變動值：epsilon不斷變小 = 隨機性不斷變小。
* INITIAL_EPSILON = 0.5 # starting value of epsilon
* FINAL_EPSILON = 0.01 # final value of epsilon
> 怎麼理解呢？
> 一開始需要更多的探索，所以動作偏隨機
> 慢慢的我們需要動作能夠有效，因此減少隨機。也就是越來越貪婪。
* 固定值：epsilon = 0.1
* 用來控制貪婪程度的值
* 10%的時間來探索, 90%的時間是選擇最優策略.
---
* alpha = 0.1 ,學習率
* gamma = 0.8 ,獎勵遞減值
* 1: 能清楚看到之後所有步驟的全部價值，愈接近1愈有遠見

## Q-Table

## 參考資料
:::success

### epsilon-greed

1. 【轉】強化學習（一）Deep Q-Network
* https://www.itread01.com/content/1545365596.html
* https://www.cnblogs.com/hhh5460/p/10154874.html
2. Multi-Armed Bandit: epsilon-greedy
https://zhuanlan.zhihu.com/p/32335683
3. 賭徒的人工智慧1：吃角子老虎 (Bandit) 問題
https://blog.yoctol.com/%E8%B3%AD%E5%BE%92%E7%9A%84%E4%BA%BA%E5%B7%A5%E6%99%BA%E6%85%A71-%E5%90%83%E8%A7%92%E5%AD%90%E8%80%81%E8%99%8E-bandit-%E5%95%8F%E9%A1%8C-62da60b58e3e
4. 用Q-learning算法實現自動走迷宮機器人
https://segmentfault.com/a/1190000019212182?utm_source=tuicool&utm_medium=referral
5. 研究了一堆Q-learning資料後，寫了這份指南https://zhuanlan.zhihu.com/p/36119355
6. Epsilon-Greedy算法
https://blog.csdn.net/lafengxiaoyu/article/details/102634543
7. 真正具有學習能力的----強化學習
http://www.feiguyunai.com/index.php/2018/01/07/pythonai-dl-rl01/

### 強化學習
1. 蔡炎⿓ 政治⼤學應⽤數學系 強化學習 Deep Learning
https://www.slideshare.net/yenlung/reinforcement-learning-90737484
:::