# 強化學習與 Q-Learning 簡介
> 速寫作者：[Tomomi Imura](https://www.twitter.com/girlie_mac)
強化學習涉及三個重要概念：代理人（agent）、一些狀態（states），以及每個狀態下的一組行動。透過在特定狀態執行一個行動，代理人會獲得一個獎勵。再次想像電腦遊戲《超級瑪利歐》。你是瑪利歐，你在一個遊戲關卡中，站在懸崖邊緣。上方有一個硬幣。你扮演的瑪利歐，在關卡內一個特定位置……這就是你的狀態。向右走一步（行動）會讓你掉下懸崖，這會給你一個低分數。然而，按下跳躍鍵會讓你獲得一分，並且你會繼續存活。這是一個正向的結果，應該給予你一個正的數值獎勵。
透過使用強化學習和模擬器（遊戲），你可以學習如何玩遊戲以最大化獎勵，也就是保持存活並盡可能多得分。
[](https://www.youtube.com/watch?v=lDq_en8RNOo)
> 🎥 點擊上方圖片收聽 Dmitry 討論強化學習
## [課前小測驗](https://ff-quizzes.netlify.app/en/ml/)
## 先決條件與設置
在本課程中，我們將用 Python 實驗一些代碼。你應該能在自己的電腦或雲端運行本課的 Jupyter Notebook 代碼。
你可以打開[課程筆記本](https://github.com/microsoft/ML-For-Beginners/blob/main/8-Reinforcement/1-QLearning/notebook.ipynb)並跟隨本課程建構。
> **注意：** 如果你打算從雲端打開這份代碼，也需要下載 [`rlboard.py`](https://github.com/microsoft/ML-For-Beginners/blob/main/8-Reinforcement/1-QLearning/rlboard.py) 文件，此文件在筆記本代碼中會用到。將它放在與筆記本同一目錄下。
## 簡介
在本課，我們將探索[彼得與狼](https://en.wikipedia.org/wiki/Peter_and_the_Wolf)的世界，靈感來自俄羅斯作曲家[謝爾蓋·普羅科菲耶夫](https://en.wikipedia.org/wiki/Sergei_Prokofiev)的音樂童話。我們將使用強化學習讓彼得探索環境，收集美味的蘋果，並避開狼。
強化學習（RL）是一種學習技術，允許我們通過大量實驗來學習代理人在某個環境中最佳行為。代理人在此環境中應有明確的目標，以獎勵函數表示。
## 環境
為簡化起見，我們假設彼得的世界是一個大小為 `寬度` x `高度` 的方形棋盤，如下所示：
棋盤中的每個格子可以是：
* 地面，彼得和其他生物可以行走的地方。
* 水域，你顯然不能走在水上。
* 樹木或草地，可以休息的地方。
* 蘋果，代表彼得會高興找到用來餵食自己的東西。
* 狼，危險需避免。
Python 有一個獨立模組 [`rlboard.py`](https://github.com/microsoft/ML-For-Beginners/blob/main/8-Reinforcement/1-QLearning/rlboard.py)，包含用於此環境的代碼。因為這段代碼對理解本概念不重要，我們將導入模組並用它創建示例棋盤（程式碼塊 1）：
```python
from rlboard import *
width, height = 8,8
m = Board(width,height)
m.randomize(seed=13)
m.plot()
```
這段代碼會印出類似上圖的環境圖。
## 行動與策略
在例子中，彼得的目標是找到蘋果，並避開狼與其他障礙物。為此，他基本上可以四處走動直到找到蘋果。
因此，在任意位置，他可以選擇以下行動之一：上、下、左、右。
我們將定義這些行動為字典，並將它們映射到相應的座標變化對。例如，向右移動 (`R`) 對應於座標變化 `(1,0)`。（程式碼塊 2）：
```python
actions = { "U" : (0,-1), "D" : (0,1), "L" : (-1,0), "R" : (1,0) }
action_idx = { a : i for i,a in enumerate(actions.keys()) }
```
總結來說，此場景的策略與目標如下：
- 策略，代理人（彼得）的策略由所謂的策略函數（policy）定義。策略是一個函數，輸入任一狀態即返回該狀態下的行動。在此，我們的問題狀態由棋盤包括玩家當前位置表示。
- 目標，強化學習的目標是最終學到一個優良策略，能有效解決問題。然而，作為基準，先考慮最簡單的策略稱為隨機漫步。
## 隨機漫步
首先，我們用實作隨機漫步策略解決問題。在隨機漫步中，我們將從允許的行動中隨機選擇下一步行動，直到找到蘋果（程式碼塊 3）。
1. 用以下代碼實作隨機漫步：
```python
def random_policy(m):
return random.choice(list(actions))
def walk(m,policy,start_position=None):
n = 0 # 步數
# 設置初始位置
if start_position:
m.human = start_position
else:
m.random_start()
while True:
if m.at() == Board.Cell.apple:
return n # 成功！
if m.at() in [Board.Cell.wolf, Board.Cell.water]:
return -1 # 被狼吃掉或溺死
while True:
a = actions[policy(m)]
new_pos = m.move_pos(m.human,a)
if m.is_valid(new_pos) and m.at(new_pos)!=Board.Cell.water:
m.move(a) # 進行實際移動
break
n+=1
walk(m,random_policy)
```
`walk` 函式的呼叫應返回相對應路徑長度，該長度可能每次運行都不同。
1. 多次（例如 100 次）運行漫步實驗，並列印結果統計數據（程式碼塊 4）：
```python
def print_statistics(policy):
s,w,n = 0,0,0
for _ in range(100):
z = walk(m,policy)
if z<0:
w+=1
else:
s += z
n += 1
print(f"Average path length = {s/n}, eaten by wolf: {w} times")
print_statistics(random_policy)
```
注意平均路徑長度約為 30-40 步，考慮到最近蘋果平均距離約 5-6 步，這數量相當大。
你還可以看到彼得隨機漫步的移動樣貌：
## 獎勵函數
為了讓策略更聰明，我們需要了解哪些移動比其他「好」。為此，我們需要定義目標。
目標可用獎勵函數定義，該函數會對每個狀態回傳某分數值。數值越高，獎勵函數越好。（程式碼塊 5）
```python
move_reward = -0.1
goal_reward = 10
end_reward = -10
def reward(m,pos=None):
pos = pos or m.human
if not m.is_valid(pos):
return end_reward
x = m.at(pos)
if x==Board.Cell.water or x == Board.Cell.wolf:
return end_reward
if x==Board.Cell.apple:
return goal_reward
return move_reward
```
有趣的是，獎勵函數多數情況下，我們只會在遊戲結束時得到顯著的獎勵。這意味著我們的算法應該記憶導致結束時正面獎勵的「好」步驟，並加強它們的重要性。類似地，所有導致壞結果的移動應被削弱。
## Q-Learning
我們將介紹一個稱為 **Q-Learning** 的算法。在此算法中，策略由一個函數（或資料結構）稱為Q-表格定義。它記錄在給定狀態中各行動的「優劣」。
它稱為 Q-表，因為通常會以表格或多維陣列形式呈現。由於我們的棋盤是 `寬度` x `高度`，可用 numpy 陣列表示 Q-表，形狀為 `寬度` x `高度` x `len(actions)`：（程式碼塊 6）
```python
Q = np.ones((width,height,len(actions)),dtype=np.float)*1.0/len(actions)
```
注意我們以相同數值初始化 Q-表的所有值，在此為 0.25，對應「隨機漫步」策略，因為每狀態的行動同樣優劣。我們可以將 Q-表傳給 `plot` 函數，在棋盤中視覺化：`m.plot(Q)`。
每格中心有一個「箭頭」指示偏好的移動方向。若所有方向相等，則顯示點。
現在我們要運行模擬，探索環境，學習較佳的 Q-表值分布，讓我們更快找到蘋果路徑。
## Q-Learning 的本質：Bellman 方程式
一旦開始移動，每個行動會有相應獎勵，即理論上可依最高即時獎勵選擇下一行動。但在多數狀態，行動無法馬上達成找蘋果目標，因此無法立即決定較佳方向。
> 請記住，不是即時結果重要，而是模擬結束時取得的最終結果。
為了考慮此延遲獎勵，我們需使用[動態規劃](https://en.wikipedia.org/wiki/Dynamic_programming)的原理，讓我們以遞迴思考問題。
假設我們處於狀態 *s*，想移動到下一狀態 *s'*；此時會得到即時獎勵 *r(s,a)* 為函數定義，再加上一些未來獎勵。若假設 Q-表正確反映每行動「吸引力」，則在狀態 *s'* 會選擇行動 *a*，使 *Q(s',a')* 達最大值。故狀態 *s* 可取得的最佳未來獎勵定義為 `max`a'*Q(s',a')*（此處最大化運算涵蓋狀態 *s'* 所有可能行動 *a'*）。
這給出在狀態 *s*、行動 *a* 下計算 Q-表值的 **Bellman 公式**：
這裡的 γ 是所謂的折扣因子，決定你應多偏好當前獎勵還是未來獎勵。
## 學習算法
基於上述方程式，我們現在可以寫出學習算法的伪代碼：
* 用相同數值初始化 Q-表 Q，涵蓋所有狀態和行動
* 設定學習率 α ← 1
* 重複多次模擬
1. 從隨機位置開始
1. 重複
1. 在狀態 *s* 選擇行動 *a*
2. 執行行動，移動到新狀態 *s'*
3. 若遇遊戲結束條件或總獎勵過小，退出模擬
4. 計算新狀態的獎勵 *r*
5. 根據 Bellman 方程更新 Q 函數：*Q(s,a)* ← *(1-α)Q(s,a)+α(r+γ maxa'Q(s',a'))*
6. *s* ← *s'*
7. 更新總獎勵並降低 α。
## 利用（exploit）與探索（explore）
在上述算法中，我們未指定在 2.1 步驟如何選擇行動。若隨機選擇行動，我們會隨機探索環境，可能經常死亡且探索不常去的區域；另一方法是利用我們已知的 Q-表值，在狀態 *s* 選擇最佳行動（Q-表值高）。但此舉會阻礙探索其他狀態，可能無法找到最優解。
因此，最佳策略是在探索和利用間取得平衡。可根據 Q-表值按比例選擇狀態 *s* 下的行動。起初當 Q-表值均等時，行為視同隨機選擇；隨著我們對環境了解加深，代理人較可能沿最優路徑前進，且偶爾嘗試未探索路徑。
## Python 實作
現在我們準備實作學習算法。在此之前，我們還需要一個將 Q-表中任意數值轉換為相應行動概率向量的函數。
1. 創建 `probs()` 函數：
```python
def probs(v,eps=1e-4):
v = v-v.min()+eps
v = v/v.sum()
return v
```
我們在原始向量中加一些 `eps`，以避免初始所有分量相同時除以 0。
通過 5000 次實驗（稱為 **epoch**）執行學習算法：（程式碼塊 8）
```python
for epoch in range(5000):
# 選擇初始點
m.random_start()
# 開始移動
n=0
cum_reward = 0
while True:
x,y = m.human
v = probs(Q[x,y])
a = random.choices(list(actions),weights=v)[0]
dpos = actions[a]
m.move(dpos,check_correctness=False) # 我哋容許玩家移出棋盤，會終止回合
r = reward(m)
cum_reward += r
if r==end_reward or cum_reward < -1000:
lpath.append(n)
break
alpha = np.exp(-n / 10e5)
gamma = 0.5
ai = action_idx[a]
Q[x,y,ai] = (1 - alpha) * Q[x,y,ai] + alpha * (r + gamma * Q[x+dpos[0], y+dpos[1]].max())
n+=1
```
執行此算法後，Q-表將更新為定義各步驟不同行動吸引力的值。我們可以嘗試視覺化 Q-表，在每格畫出指向期望移動方向的向量。為簡便起見，改以小圓圈代替箭頭頭部。
## 檢查策略
由於 Q-表列出每狀態下行動的「吸引力」，我們很容易用它定義有效的導航。在最簡單情況下，我們可以選擇對應最高 Q-表值的行動：（程式碼塊 9）
```python
def qpolicy_strict(m):
x,y = m.human
v = probs(Q[x,y])
a = list(actions)[np.argmax(v)]
return a
walk(m,qpolicy_strict)
```
> 如果你多次嘗試上述代碼，你可能會注意到有時它會「卡住」，你需要按下筆記本中的停止按鈕來中斷它。這是因為可能存在兩個狀態在最佳 Q 值方面「互相指向」的情況，在這種情況下，代理會無限地在這些狀態之間移動。
## 🚀挑戰
> **任務 1：** 修改 `walk` 函數，使路徑的最大長度限制為一定步數（例如 100 步），並觀察上述代碼時不時返回該值。
> **任務 2：** 修改 `walk` 函數，使其不返回之前已經去過的地方。這將防止 `walk` 進入循環，但代理仍可能被困在一個無法逃脫的位置。
## 導航
一個更好的導航策略是我們在訓練時使用的，結合了利用和探索。在這個策略中，我們會以一定的概率選擇每個動作，概率與 Q 表中的值成比例。這種策略仍可能導致代理返回之前已經探索過的位置，但正如你從下面代碼中看到的，它能使到達目標位置的平均路徑非常短（記住 `print_statistics` 會運行模擬 100 次）：(代碼塊 10)
```python
def qpolicy(m):
x,y = m.human
v = probs(Q[x,y])
a = random.choices(list(actions),weights=v)[0]
return a
print_statistics(qpolicy)
```
執行此代碼後，你應該會得到比之前小得多的平均路徑長度，約在 3-6 步之間。
## 探討學習過程
如我們所述，學習過程是在問題空間結構的探索與利用間的平衡。我們已見到學習結果（幫助代理找到目標短路徑的能力）有所提升，但觀察平均路徑長度在學習過程中的變化同樣有趣：
學習總結如下：
- 平均路徑長度增加。我們看到一開始平均路徑長度增加。這可能是因為當我們對環境一無所知時，容易陷入不良狀態，如水域或狼群。隨著學習更多並開始利用這些知識，我們能更長時間探索環境，但對蘋果的位置還不夠清楚。
- **隨著學習增多，路徑長度下降**。一旦學習足夠，代理達成目標變得更容易，路徑長逐漸縮短。然而，我們仍保持探索，因此常偏離最佳路徑，嘗試新選項，導致路徑比理想的更長。
- 路徑長度突然增加。圖中也可觀察到某些時候路徑長度突然增加，這顯示出過程的隨機特性，某些時刻我們可能會透過新值覆寫而「破壞」Q 表係數。理想中應透過降低學習率（如訓練後期僅修正 Q 表的值很小）來減少這種情況。
總的來說，重要的是記住學習過程的成功與質量嚴重依賴於參數，比如學習率、學習率衰減和折扣因子。這些通常稱為 超參數，以區別於我們在訓練中優化的 參數（例如 Q 表係數）。尋找最佳超參數值的過程稱為 超參數優化，是個值得獨立討論的主題。
## [課後小測驗](https://ff-quizzes.netlify.app/en/ml/)
## 作業
[一個更現實的世界](assignment.md)
---
**免責聲明**：
本文件使用 AI 翻譯服務 [Co-op Translator](https://github.com/Azure/co-op-translator) 進行翻譯。雖然我們力求準確，但請注意，自動翻譯可能包含錯誤或不準確之處。原始文件的母語版本應被視為權威來源。對於重要資訊，建議尋求專業人工翻譯。我們不對因使用本翻譯而引起的任何誤解或曲解承擔責任。