強化學習

study

強化學習 Reinforcement Learning §

• 代理人 Agent : 使用策略，根據觀測的狀態選擇動作，與環境互動

• 環境 Environment : 根據 Agent 的動作，改變狀態

• 獎勵函數 Reward Function : 根據 Agent 執行動作後的結果，給予的回饋的函數

• 策略 Policy ${\pi }_{\theta }$ : 由參數 $\theta$ 決定的神經網路，輸入狀態，輸出動作的機率分佈

• 狀態 State $s$ : 環境的觀測值

• 動作 Action $a$ : 策略在狀態 $s$ 下輸出的動作

• 軌跡 Trajectory $\tau$ : 狀態與動作的序列

$$\tau =(s_1,a_1,s_2,a_2,\dots ,s_T,a_T)$$

• 軌跡機率 $p_{\theta }(\tau )$ : 在策略 ${\pi }_{\theta }$ 下產生某軌跡 $\tau$ 的機率
  • $p(s_1)$: 初始狀態的機率，環境決定
  • ${\pi }_{\theta }(a_t|s_t)$: 策略，在狀態 $s_t$ 下，代理人選擇動作 $a_t$ 的機率，可透過調整 $\theta$ 來改變
  • $p(s_{t+1}|s_t,a_t)$: 狀態轉移機率，在狀態 $s_t$ 做動作 $a_t$ 後，狀態變成 $s_{t+1}$ 的機率，由環境決定

$$p_{\theta }(\tau )=p(s_1)\prod _{t=1}^T{\pi }_{\theta }(a_t|s_t)p(s_{t+1}|s_t,a_t)$$

• 獎勵 Reward $r_t$ : 獎勵函數根據單一步動作或狀態給出的獎勵
• 回報 Return $R(\tau )$ : 軌跡 $\tau$ 的總回報，各時間步的獎勵總和
  • 通常會引入折扣因子 $\gamma \in [0,1]$，計算累積折扣回報 $G_t={\sum }_{k=0}^{T-t}{\gamma }^k{r}_{t+k}$

$$R(\tau )=\sum _{t=1}^T{r}_t$$

• 期望回報
  • 策略在參數 $\theta$ 下，對於所有可能軌跡的回報期望值
  • 通常作為要最大化的目標函數 $J(\theta )$

$$J(\theta )={\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}[R(\tau )]=\sum _{\tau }{p}_{\theta }(\tau )R(\tau )$$

• 方法: 在訓練的過程中，計算策略梯度，接著做梯度上升，目標最大化期望回報
• 策略梯度 Policy Gradient
  • 目標函數的梯度 ${\nabla }_{\theta }J(\theta )$
  • 期望回報的梯度
  • 推導後可發現是透過對策略 ${\pi }_{\theta }$ 微分來獲得

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}\left[\left(\sum _{t=1}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\right)R(\tau )\right]\approx \frac{1}{N}\sum _{i=1}^N\left(\sum _{t=1}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_{i,t}|s_{i,t})\right)R({\tau }_i)$$

• 在 $t$ 時刻的動作只能影響 $t$ 之後的獎勵，因此 $R({\tau }_i)$ 可以替換為 $G_{i,t}$ (從 $t$ 開始的累積回報)，能減少梯度的變異數
• 梯度上升 Gradient Ascent
  • 使用計算出的梯度來更新策略參數 $\theta$

$$\theta \leftarrow \theta +\eta {\nabla }_{\theta }J(\theta )$$

---

策略梯度推導 §

1. 對 $J(\theta )$ 微分 §

$$\begin{array}{rl}J(\theta )& ={\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}[R(\tau )]=\sum _{\tau }{p}_{\theta }(\tau )R(\tau )\\ ⟹{\nabla }_{\theta }J(\theta )& ={\nabla }_{\theta }\sum _{\tau }{p}_{\theta }(\tau )R(\tau )=\sum _{\tau }{\nabla }_{\theta }{p}_{\theta }(\tau )R(\tau )\end{array}$$

• 這裡只有 $p_{\theta }(\tau )$ 與 $\theta$ 有關，$R(\tau )$ 對於一固定的軌跡是常數
• $\nabla p_{\theta }(\tau )$ 很難直接算

$$\begin{array}{rl}{p}_{\theta }(\tau )& =p(s_1)\prod _{t=1}^T{\pi }_{\theta }(a_t|s_t)p(s_{t+1}|s_t,a_t)\\ ⟹\nabla p_{\theta }(\tau )& =?\end{array}$$

• 連乘積的微分展開
  • 微積分乘法法則 $(fgh{)}^{\prime }=f^{\prime }gh+f{g}^{\prime }h+fg{h}^{\prime }$，結果會變成一長串原本式子的變形加總，計算非常繁瑣
  • 結果包含環境的轉移機率 $p(s_{t+1}|s_t,a_t)$，這通常是未知的
• 無法轉換為期望值
  • 強化學習依賴蒙地卡羅採樣 (Monte Carlo Sampling)
  • 要能採樣估算，算式必須是期望值的形式 ${\mathbb{E}}_{x\sim p(x)}[f(x)]=\sum p(x)f(x)$
  • 原始式子 $\sum \nabla {\mathbf{p}}_{\theta }(\tau )R(\tau )$，沒有 $p_{\theta }(\tau )$，只有它的微分。$\nabla p$ 不是機率分佈（它可能有負值，總和也不為 1），所以無法透過採樣來直接估算這一項

2. 使用 Log-Derivative Trick §

Log-Derivative Identity: $\nabla f(x)=f(x)\nabla \log f(x)$ 推導： $\nabla \log f(x)=\frac{1}{f(x)}\nabla f(x)⟹\nabla f(x)=f(x)\nabla \log f(x)$

• 將梯度的值轉換為機率密度 $\times$ 對數機率的梯度，使我們能夠計算期望值的梯度
• 對於無法直接微分的隨機系統（如強化學習中的環境獎勵）是唯一的解法
• 用這個方式把 ${\nabla }_{\theta }{p}_{\theta }(\tau )$ 替換掉

$${\nabla }_{\theta }{p}_{\theta }(\tau )=p_{\theta }(\tau ){\nabla }_{\theta }\log p_{\theta }(\tau )$$

代回原本的式子：

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& =\sum _{\tau }{p}_{\theta }(\tau ){\nabla }_{\theta }\log p_{\theta }(\tau )R(\tau )\\ & ={\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}[{\nabla }_{\theta }\log p_{\theta }(\tau )R(\tau )]\end{array}$$

這條式子又變回了期望值的形式（因為出現了 $\sum p(\tau )\dots$）

3. 展開軌跡機率 §

將軌跡機率 $p_{\theta }(\tau )$ 以連乘積形式展開，取對數後微分：

$$\begin{array}{rl}{p}_{\theta }(\tau )& =p(s_1)\prod _{t=1}^T{\pi }_{\theta }(a_t|s_t)p(s_{t+1}|s_t,a_t)\\ ⟹\log p_{\theta }(\tau )& =\log p(s_1)+\sum _{t=1}^T\log {\pi }_{\theta }(a_t|s_t)+\sum _{t=1}^T\log p(s_{t+1}|s_t,a_t)\\ ⟹{\nabla }_{\theta }\log p_{\theta }(\tau )& =0+\sum _{t=1}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)+0\end{array}$$

環境的初始狀態機率 $p(s_1)$ 和轉移機率 $p(s_{t+1}|s_t,a_t)$ 都與 $\theta$ 無關，所以它們的對 $\theta$ 的微分都是 0，代回期望值公式，得到了最終的策略梯度公式：

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& ={\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}\left[\left(\sum _{t=1}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\right)R(\tau )\right]\\ & \approx \frac{1}{N}\sum _{i=1}^N\left(\sum _{t=1}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_{i,t}|s_{i,t})\right)R({\tau }_i)\end{array}$$

此公式描述如何更新參數：

• ${\nabla }_{\theta }\log {\pi }_{\theta }(a_{i,t}|s_{i,t})$ : 參數更新的方向向量
• $R({\tau }_i)$ : 每個軌跡的回報，作為該方向的權重

---

梯度上升 Gradient Ascent §

利用計算出的策略梯度 ${\nabla }_{\theta }J(\theta )$ 來更新神經網路參數 $\theta$，以最大化期望回報

$$\begin{array}{rl}\theta & \leftarrow \theta +\eta \cdot {\nabla }_{\theta }J(\theta )\\ ⟹\theta & \leftarrow \theta +\eta \cdot \frac{1}{N}\sum _{i=1}^N\sum _{t=1}^T\underset{\text{方向向量}}{\underbrace{{\nabla }_{\theta }\log {\pi }_{\theta }(a_{i,t}|s_{i,t})}}\cdot \underset{\text{權重分數}}{\underbrace{R({\tau }_i)}}\end{array}$$

• 若回報 $R(\tau )>0$（表現好）：
  • 梯度 $\times$ 正數，參數沿著梯度方向更新
  • 增加該軌跡中動作出現的機率
• 若回報 $R(\tau )<0$（表現差）：
  • 梯度 $\times$ 負數，參數沿著梯度反方向更新
  • 減少該軌跡中動作出現的機率

---

基線 Baseline §

若所有軌跡的獎勵 $R(\tau )$ 都是正數（例如最低分是 +10，最高分是 +100），會發生

• 當下採樣到哪個軌跡就朝那個方向更新，所有動作都會被鼓勵，機率提升
• 梯度變異數大，訓練不穩定

引入一個基線 $b$（通常設為平均獎勵，或由另一個網路估計的狀態價值 $V(s)$），將回報減去基線

• 不在意絕對分數，而是這個動作表現得比平常好還是差，
• 若 $G_t>b$：表現比平常好，梯度 $\times$ 正數，機率增加
• 若 $G_t<b$：表現比平常差，梯度 $\times$ 負數，機率減少
• 不會改變梯度的期望值，但能顯著降低變異數，讓訓練更穩定

$${\nabla }_{\theta }J(\theta )\approx \frac{1}{N}\sum _{i=1}^N\sum _{t=1}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_{i,t}|s_{i,t})\cdot (G_{i,t}-b)$$

• 由於 $b(s_t)$ 與動作 $a_t$ 無關，利用 Log-Derivative Trick 可證明其期望值為 0

$$\begin{array}{rl}{\mathbb{E}}_{a\sim \pi }[{\nabla }_{\theta }\log \pi (a|s)\cdot b(s)]& =b(s)\sum _a\pi (a|s)\frac{{\nabla }_{\theta }\pi (a|s)}{\pi (a|s)}\\ & =b(s){\nabla }_{\theta }\sum _a\pi (a|s)=b(s)\cdot {\nabla }_{\theta }(1)=0\end{array}$$

---

On-Policy vs. Off-Policy §

在強化學習中，這兩者的區別在於與環境互動的 Agent 和要學習（更新參數）的 Agent 是否相同

• On-Policy (同策略)

  • 互動者：${\pi }_{\theta }$
  • 學習者：${\pi }_{\theta }$
  • 用 ${\pi }_{\theta }$ 去蒐集資料（Trajectory $\tau$）
  • 根據資料更新參數 $\theta \to {\theta }^{\prime }$
  • 參數更新後，原本蒐集的資料機率分佈就變了，不能再用
  • 每次更新參數後，都必須重新與環境互動採樣

• Off-Policy (異策略)

  • 互動者：${\pi }_{{\theta }^{\prime }}$ (固定或是上一輪的參數)
  • 學習者：${\pi }_{\theta }$
  • ${\pi }_{{\theta }^{\prime }}$ 蒐集一次資料後，${\pi }_{\theta }$ 可以利用這批資料進行多次梯度上升更新
  • 資料使用效率高

---

From On-Policy to Off-Policy via Importance Sampling §

為了從 On-Policy 轉換到 Off-Policy

• 需要計算在策略 ${\pi }_{\theta }$ 下的期望回報，但使用 ${\pi }_{{\theta }^{\prime }}$ 蒐集的資料
• 使用重要性採樣，將在一個分佈下的期望值轉換為另一個分佈下的期望值

$$\begin{array}{rl}{\mathbb{E}}_{x\sim p}[f(x)]& =\int p(x)f(x)dx\\ & =\int q(x)\frac{p(x)}{q(x)}f(x)dx\\ & ={\mathbb{E}}_{x\sim q}\left[\frac{p(x)}{q(x)}f(x)\right]\end{array}$$

• 機率比率 $\frac{p(x)}{q(x)}$
  • 修正兩個分佈的差異
  • 環境的轉移機率 $p(s_{t+1}|s_t,a_t)$ 會互相消去，因此不需要環境的動力學模型，只計算策略的比率即可

$$\frac{p_{\theta }(\tau )}{p_{{\theta }^{\prime }}(\tau )}=\frac{p(s_1){\prod }_{t=1}^T{\pi }_{\theta }(a_t|s_t)p(s_{t+1}|s_t,a_t)}{p(s_1){\prod }_{t=1}^T{\pi }_{{\theta }^{\prime }}(a_t|s_t)p(s_{t+1}|s_t,a_t)}=\prod _{t=1}^T\frac{{\pi }_{\theta }(a_t|s_t)}{{\pi }_{{\theta }^{\prime }}(a_t|s_t)}$$

• 將互動者從 $\theta$ 換成 ${\theta }^{\prime }$ 的目標函數
  • 假設狀態分佈 $p(s)$ 差異不大，主要針對動作機率 $\pi (a|s)$ 做修正
  • 若 $p$ 與 $q$ 分佈差異太大，雖然期望值一樣，但變異數大，導致訓練不穩定
  • 優勢函數 $A^{{\theta }^{\prime }}(s,a)$：即前述的 $G_t-b(s_t)$，代表在狀態 $s$ 下執行動作 $a$ 相較於平均表現的好壞

$$J^{{\theta }^{\prime }}(\theta )={\mathbb{E}}_{(s,a)\sim {\pi }_{{\theta }^{\prime }}}\left[\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }^{\prime }}(a|s)}{A}^{{\theta }^{\prime }}(s,a)\right]$$