---
# System prepended metadata

title: '[DL] Q-Learning 簡介'
tags: [Deep Learning]

---

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

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

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

![](https://i.imgur.com/NVEoTei.png)


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


(二) ![](https://i.imgur.com/TWyUGDq.png =250x)

* **重要觀念：未來只取決於當前**
    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決策
![](https://i.imgur.com/Uga8EFq.png )
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更新
![](https://i.imgur.com/5qTWVDH.png)

![](https://i.imgur.com/OjVeg6o.png)




## 如何選擇動作

### 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
:::