---
tags: Knock Knock! Deep Learning
---
Day 24 / DL x RL / 決策與 RL
===

結束了 CV 子系列，接下來要來介紹完全不同於 supervised / unsupervised learning 的訓練方法 —— **reinforcement learning（RL，強化學習）**。

2013 年 Google DeepMind 團隊發表遊戲 Atari 基於 DL 和 RL 訓練出能打敗人類的 AI，也是 DL 與 RL 成功結合的先端。此後 deep RL 受到關注，在遊戲界和機器人界陸續有了新的斬獲，其中最舉世皆知的突破莫過於 2016 年同樣也是 DeepMind 團隊發表的圍棋 AI AlphaGo，以 4:1 戰勝當時世界上最厲害的圍棋高手李世石。這些成果也讓人非常期待 RL 未來能在其他應用領域帶來更多突破。

那就讓我們先從 RL 的基本架構看起，再帶到經典的 Atari AI 怎麼運用 DL 和 RL 做結合，來認識 RL 這個有趣的訓練方法。

## The Experience-Based Reinforcement Learning

之前介紹過的 task 大部分是 supervised / unsupervised learning，他們大都基於 data 做訓練，從大量資料中找尋特徵以利於預測。Reinforcement learning 則走另一條路，是一種藉由和**環境大量互動汲取經驗，從錯誤中學習**的方法。

Reinforcement learning 的目標是 **decision making（決策）**。任何任務只要能夠轉換成這個目標，就可以用 RL 來訓練，非常有彈性。從遊戲中下一個動作、圍棋下一手的落點、機器人的下個控制動作，到廣告投放、影片推薦等等，都是在做決策，也因此都能成為 RL 的客戶，但好不好訓練又是另一件事了。

> 這跟人類的學習模式很接近。舉例來說，今天你參與一個社交場合，發現坐著很被動等人聊天會根本沒人理你，那你下次參加可能會想主動找人搭話。下次主動找人搭話了，卻發現聊的東西根本不著邊際，你就會想說啊算了，下次默默吃餐點可能更好。結果後來又發現錯過認識很多人的機會，非常可惜，那你可能又決定以後還是要在社交場合偽裝自己一下。事實上你的任何決定並沒有對錯（有別於 supervised learning 有正確答案），每個人對每個決定感受到的價值也不同，這種根據價值調整決策模式尋找平衡點的過程，其實就是 reinforcement learning。

那麼這個跟環境互動汲取經驗的框架，具體來說怎麼 formulate 呢？

## RL 框架

RL 是建立在 Markov decision process (MDP) 的架構之上來模擬決策過程以進行訓練的，大致長這樣：

*—— RL 框架。*

這個框架包含了以下要素：

- $s$：**state**，環境狀態。
- $a$：**action**，動作。
- $r$：**reward**，獎勵。
- $o$：**observation**，環境觀察。

舉例來說，你想要用 RL 訓練一台自駕車（agent），讓他在某個環境（environment）中學習自動駕駛。在每個時間點 $t$：

1. 環境的狀態為 $s_t$（哪些位置有什麼物體、自己在哪裡等等）。
2. Agent 會因為處在 $s_t$ 獲得 reward $r_t$（例如撞到車子會有 negative reward，沒有碰撞則有 positive reward），並從環境觀察到 $o_t$（自己前方可以看到的物體等等）。
3. 並以此選擇能 maximize 未來 reward 的 $a_t$（例如方向向右）。
4. 做出 action 後，環境狀態會被更新成 $s_{t+1}$。
5. 且獲得 reward $r_{t+1}$，同時獲取新的 observation $o_{t+1}$。
7. 繼續選擇下一個動作 $a_{t+1}$。
8. ⋯⋯

### State Transition and Reward Function

上面只是模擬決策過程中的要素。這個環境還需要定義 state 與 state 之間怎麼轉換，以及每次轉換的 reward：

- **State transition probability $P_{sa}$**：在 state $s$ 選擇 action $a$ 後，轉換到每個 next state $s'$ 的機率。
- **Reward function**：在 state $s$ 選擇 action $a$ 後獲得的 reward $R(s, a)$，或在 state $s$ 時的 reward $R(s)$。

不過 reward 的計算方法需要嚴謹一點。當你在 state $s$，只考慮當下能獲得的 reward 來選擇 action 的話，未免有點短視近利。如果剛好這一步能離終點直線距離最近，但會走進死路呢？那顯然現在走別條路更好。

因此考慮 action 時，也需要考慮**未來所獲得的總 reward**，而非只有當下立刻能獲得的 reward。除此之外，總 reward 的計算需要包含 **$\gamma$ discount factor** 來讓當前 reward 比未來的 reward 更受重視。方法如下：

$$
R(s_0, a_0) + \gamma R(s_1, a_1) + \gamma^2 R(s_2, a_2) + \dots
$$

如此一來，太遙遠以後的 reward 比重較低，但如果他本身影響巨大，還是能左右現在的選擇。

### Policy and Value Function

環境中能影響 agent 學習的要素都準備好了，接著就是進入 agent 的腦袋。

Agent 最主要的目標就是學習到好的 policy $\pi$，也就是在 state $s$ 選擇 action $a$，以完成任務：

$$
a = \pi(s)
$$

可以想像一個 agent 可以有無限種合法的 policy，但是我們想學的當然是最好的。不同 policy 可以用 **value function** 來評判好壞，有以下兩種形式：

#### State Value Function

第一種 value function $V^{\pi}$ 是 state-based，計算**在 state $s$ 時，根據 policy $\pi$ 走的話能獲得的 total expected reward**：

$$
V^{\pi}(s) = \mathbb{E}[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \dots]
$$

這個 value function 也可以用 [Bellman equation](https://en.wikipedia.org/wiki/Bellman_equation) 來表示，變成類似遞迴的計算：

$$
V^{\pi}(s) = R(s) + \gamma \sum_{s' \in S} P_{s\pi(s)}(s')V^{\pi}(s')
$$

這樣的形式表示 value 是當下 reward $R(s)$ 和所有進入 next state $s'$ 的機率 $P_{s\pi(s)}(s')$ 乘上到達 next state 後的 discounted value $\gamma V^{\pi}(s')$ 的總和。別忘了後面不過是期望值的計算方法。

畫了一個簡易圖，可以想像因為遞迴關係，我們會先從最後一個 timestep 計算 value（最後一步的 value 就是當下的 reward），一步步往前加總，直到遞迴到 timestep $t$ 時，未來的 $t+1$ 所有狀態都已經有了 value。Discount 以後加上現在獲得的 reward $R(s)$，即可取得這個 state 的 value $V^{\pi}(s)$：

*—— Value function as Bellman equation。*

這樣的遞迴關係，方便我們用一個 model approximate $V^{\pi}$，訓練時就用同一個 model 預測 $V^{\pi}(s)$ 和 $V^{\pi}(s')$ 的值，並慢慢調整 model 讓 $V^{\pi}$ 越來越 optimal、Bellman equation 能夠成立。

#### State-Action Value Function

第二種 value function 稱為 **Q-value function**，計算**在 state $s$ 時，選擇 action $a$ 後，再根據 policy $\pi$ 走的話能獲得的 total expected reward**，同樣也能寫成 Bellman equation：

$$
Q^{\pi}(s, a) = R(s, a) + \gamma \sum_{s' \in S} P_{sa}(s') \max_{a'} Q^{\pi}(s', a')
$$

注意到這個式子和 $V^{\pi}(s)$ 其實是同樣的意思，因為 $V^{\pi}(s') = \max_{a'} Q^{\pi}(s', a')$。

#### 差異

$V^{\pi}(s)$ 和 $Q^{\pi}(s, a)$ 看起來頗像，但 Q-value 會更適合用找出最佳 policy。為什麼呢？

首先看到如果訓練出 optimal value function $V^*(s)$，最佳 policy 會是：

$$
\pi^*(s) = {\arg \max}_{a \in A} \sum_{s' \in S} P_{sa}(s')V^*(s')
$$

而訓練出 optimal Q-value function $Q^*(s, a)$，最佳 policy 會是：

$$
\pi^*(s) = {\arg \max}_{a \in A} Q(s, a)
$$

訓練 $Q(s, a)$ 的話，policy 等於挑最大 Q-value 的 action 就好。但訓練 $V(s)$，卻沒辦法很方便地轉換成我們要的 action，因為還需要 state transition probability。

### Q-Learning

從上面我們知道，要找出 policy，首先要先 approximate Q-value function。但是根據上面的數學，似乎需要知道環境的 state transition probability $P_{sa}$ 才能計算 Q-value 並訓練 Q-value function。

這次來介紹簡單一點的訓練方法 **Q-learning**，不用 $P_{sa}$ 即可訓練，這種方法稱為 model-free learning。

> 這裡的 model 是指環境 model，不是 machine learning model。

Q-learning 大致流程如下：

1. **定義 model 來 approximate Q-value function**，可以是簡單的 lookup table，當然還可以是我們最會的 neural network。Model input 會是 state $s$，output 會是 $|A|$ 個 Q-value $Q(s, a)$，$A$ 為 action space，包含所有可能動作。
2. 訓練前隨機 **initialize model parameters**。同時 intialize 所處環境，從 $s_0$ 開始。
3. 開始**跟環境互動**。Model 預測 $|A|$ 個 Q-value，選擇最大 Q-value 的 action $a_0$。做出 action 後，環境 transition 到 $s_1$，並收穫 reward $R_1$。
4. **更新 parameters**：$Q(s_0, a_0) = Q(s_0, a_0) + \alpha (R_1 + \gamma \max_a Q(s_1, a) - Q(s_0, a_0))$。
5. 重複 3.4. 直到 Q-value function 收斂。

其中最關鍵的是第四步：

$$
Q(s_t, a_t) = Q(s_t, a_t) + \alpha (R_{t+1} + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t))
$$

$\alpha$ 是 learning rate。這個方法其實很直覺，$R_{t+1} + \gamma \max_a Q(s_{t+1}, a)$ 是下個 state 實際上的 expected reward，但 model 一開始預測的是 $Q(s_t, a_t)$，因此差距為 $R_{t+1} + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t)$，update 時把這個差距藉由 $\alpha$ 慢慢補上。

> 說是實際上的 expected reward，但 $R_{t+1} + \gamma \max_a Q(s_{t+1}, a)$ 中的 $Q$ 在訓練中也只是估計值，主要是以環境真正返回的 $R_{t+1}$ 為目標邁進。

## Deep Atari

[(Mnih et al., 2013) Playing Atari with Deep Reinforcement Learning](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf)
[(Mnih et al., 2015) Human-level control through deep reinforcement learning](https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf)

介紹完 RL 的原理和 Q-learning 的學習方法，我們再藉由經典的 Atari paper 稍微統整一下剛剛的知識，還有 deep learning 如何和 Q-learning 結合。

### Problem

Atari 是一套經典的電玩機遊戲，裡面包含的遊戲大多只需要簡單幾個控制：

*—— Atari 遊戲畫面。*

這篇 paper 主要目的是用 deep learning 結合 reinforcement learning 訓練這套遊戲的 AI。這在當時（2013 年）是一項創舉，開了 DL 結合 RL 的先河。

### RL 架構

首先是 RL 框架的定義：

- Agent：Atari AI。
- Environment：Atari 模擬器。
- State：遊戲畫面。
- Action：控制動作，上下左右等等。
- Reward：動作後遊戲分數的改變。

這可以說是 RL 最簡單的設定：現有的模擬器、簡單的控制動作、容易定義的 reward。新手想玩 RL 可以先從這類的任務下手。

### 訓練方法：Deep Q-Network (DQN)

**Deep Q-network (DQN)** 是 Q-learning 的一種，其中 Q-value function 用 neural network 來 approximate。

Model 是個簡單的 CNN model。Input 遊戲畫面作為 state $s$，經由 CNN 提取特徵，預測 $|A|$ 個 $Q(s, a)$。Policy 會選擇使 $Q(s, a)$ 最大的 $a$ 當作控制動作。動作後由遊戲模擬器返回分數作為 reward，藉由 Q-learning update rule 更新 model 參數。

*—— DQN model。*

比較值得一提的是一些訓練技巧：

- **$\epsilon$-greedy**：一種平衡 **exploration 和 exploitation** 的技巧。當 agent 在玩遊戲時，保守一點可能會永遠選擇 Q-value 最大的 action 來穩穩獲得 reward，這個稱為 **exploitation**。但是太保守的話，他可能會錯失一些可以帶來極大 reward 的動作，因為他從來都不敢嘗試，也就不知道這些動作值得做。**Exploration** 就是讓 agent 能跳脫現有的 policy，不根據 Q-value 隨機選擇下個動作。在訓練時需要平衡兩者，而 $\epsilon$ 是介於 0 到 1 的值，定義跳脫 Q-value 隨機選擇動作的機率。
- **Experience replay**：把所有跟環境互動的經驗記在一個 buffer 裡面，訓練時從 buffer 隨機抽取經驗學習。這樣做可以有效重複利用以前的經驗進行訓練，同時打散不必要的時間關係。
- **Target network**：在 Q-learning 中，每一次 $Q$ 的 update 都包含了下一步過後的 Q-value $Q'$。但如果 $Q$ 和 $Q'$ 都是從同一個 model 預測的話，那麼等於更新完 model 之後，剛剛的 $Q'$ 同時失效了。這樣會造成訓練不穩定，有點像一隻狗頭追著尾巴跑。所以 paper 中用了兩個 network，一個訓練用，另一個是 target network，每隔一段時間從訓練用的 network 複製過來，接著靜置一段時間，讓這段期間的 update 更穩定一點。

### Results

簡單秀一下 value function 的 visualization：

*—— Game Breakout value function visualization。*

上圖 Breakout 遊戲，左右控制下方的板子，讓球反彈打碎上方的方塊。y 軸 $V$ 代表每個 state 的 total expected reward。右方 4 球彈到最上面後，可以預期會在上面反彈一陣子，能獲得很高的分數。

*—— Game Pong Q-value function visualization。*

上圖 Pong 遊戲，上下控制左右方塊，將球反彈到對面。y 軸 $Q$ 代表每個 state 之下進行 action No-Op、Up、和 Down 的 total expected reward。中間 2、3 顯示右邊的方塊應該要往上走，才能接到球反彈到對面。

## 結語

RL 的框架很彈性，可以套用在很多任務上進行訓練。但就算是 Atari 這麼基本的 task 都還需要很多額外的訓練技巧才能成功訓練，所以其實 RL 最困難的就是訓練的穩定性，還有訓練不成功時怎麼找出改進方法。

這次篇幅有點緊湊，一把從 RL 原理、value function、Q-learning，帶到 DQN 的 paper，內容偏學術一點。下一篇會藉由實作經典的 CartPole 問題帶大家更實際理解 RL。

## Checkpoint

- Reinforcement learning 和 supervised / unsupervised learning 比，最大的差異在於從何學習。請問兩者的學習來源分別為何？
- 能否畫出 reinforcement learning 中 agent 和 environment 的互動過程？
- Discount factor $\gamma$ 用途為何？
- Policy 簡單來說是什麼？
- Value function 和 Q-value function 主要是在計算什麼？
- Q-learning 中的 model，input 和 output 為何？Agent 會怎麼選擇下一步 action？
- DQN 中的 neural network 主要負責做什麼？
- 請解釋何謂 exploitation v.s. exploration。
- 請看一下 Q-learning 的 update rule。在 DQN 中使用 target network，是為了穩定 update rule 中的哪一項？

## 參考資料

1. [👍 CS229 Lecture Notes: Reinforcement Learning and Control](http://cs229.stanford.edu/summer2020/cs229-notes12.pdf)
2. [CS230 Lecture Slides: Deep Reinforcement Learning](https://cs230.stanford.edu/spring2020/lecture9.pdf)
3. [CS231n Lecture Slides: Reinforcement Learning](http://cs231n.stanford.edu/slides/2020/lecture_17.pdf)
4. [MIT 6.S091 Lecture Slides: Introduction to Deep Reinforcement Learning](https://www.dropbox.com/s/wekmlv45omd266o/deep_rl_intro.pdf?dl=0)
5. [CS234 Lecture Slides: Tabular RL policy evaluation](http://web.stanford.edu/class/cs234/slides/lecture3_post.pdf)
6. [CS234 Lecture Slides: Q-learning](http://web.stanford.edu/class/cs234/slides/lecture4_postd.pdf)
7. [MIT 6.S191 Lecture Slides: Deep Reinforcement Learning](http://introtodeeplearning.com/slides/6S191_MIT_DeepLearning_L5.pdf)
8. [(Arulkumaran et al., 2017) A Brief Survey of Deep Reinforcement Learning](https://arxiv.org/pdf/1708.05866.pdf)