Ⅶ. Policy Gradient Methods

• 2020 年 11 月 25 日
• 筆記
• Reinforcement Learning

Dictum:

 Life is just a series of trying to make up your mind. — T. Fuller

不同於近似價值函數並以此計算確定性的策略的基於價值的RL方法，基於策略的RL方法將策略的學習從概率集合\(P(a|s)\)變換成策略函數\(\pi(a|s)\)，並通過求解策略目標函數的極大值，得到最優策略\(\pi^*\)，主要用的是策略梯度方法(Policy Gradient Methods)。

策略梯度方法直接對隨機策略\(\pi\)進行參數化為\(\pi(a|s,\theta)=\Pr\{A_t=a|S_t=s,\theta_t=\theta\}\)，其中\(s\in\mathcal{S}\)，\(a\in\mathcal{A}(s)\)，權重參數向量\(\theta\in\mathbb{R}^{d^\prime}(d^\prime<<|\mathcal{S}|)\)，參數化後的策略不再是一個概率集合，而是一個近似函數。

相比於基於價值的RL方法，策略梯度方法的優勢如下：

• 基於價值的RL方法依賴於價值函數的估計；而對策略梯度方法，價值函數可以用於學習策略的參數，但沒有直接的依賴關係
• 基於價值的RL方法為了尋找最優策略，使用了\(\epsilon\)-貪心策略以\(\epsilon\)的概率選擇隨機動作；而策略梯度方法可以直接近似一個確定的策略，因此，具有更好的收斂性
• 基於價值的RL方法更適用於離散的動作、狀態空間，即使一些改進也需要將連續的動作空間離散化，但這樣的映射呈指數形式，增加求最優解的難度；而策略梯度方法在高維或連續動作空間中有效
• 基於價值的RL方法通常只能學習最優策略是確定的，而策略梯度方法可以學習本身就具有隨機性的最優策略

缺點如下：

• 策略梯度方法使用梯度上升，容易收斂到局部最優解
• 同時，對策略難以進行有效評估，因為它具有很高的方差

策略梯度定義

策略函數

策略函數是在確定在時序\(t\)的狀態\(s\)下，採取任何科恩那個動作的具體概率，可以看作概率密度函數。假設策略被參數化為\(\pi(a|s,\theta)\)，要求\(\pi(a|s,\theta)\)對參數\(\theta\)的偏導存在，則策略梯度

\(\triangledown \log\pi(a|s,\theta)\)是得分函數(score function)。

1. Softmax Policy

針對離散且有限的動作空間，可以使用softmax策略，對每一個「狀態-動作」二元組估計一個參數化的數值偏好\(h(s,a,\theta)\in\mathbb{R}\)，然後利用softmax函數對動作加權，如

此時，每個動作的概率正比於指數權重\(\pi(a|s,\theta)\propto e^{h(s,a,\theta)}\)。若參數化的偏好值為特徵\(x(s,a)\)的線性組合，則\(h(s,a,\theta)=\theta^\top x(s,a)\)，此時得分函數為

2. Gaussian Policy

針對龐大或連續的動作空間，不能直接計算每一個動作的概率，但可以學習概率分布的統計。通常可以使用Gaussian策略，即對應的動作服從高斯分布\(a\sim\mathcal{N}(\mu,\sigma^2)\)，則策略可以表示為

其中，均值\(\mu:\mathcal{S}\times\mathbb{R}^{d^\prime}\to\mathcal{R}\)和方差\(\sigma:\mathcal{S}\times\mathbb{R}^{d^\prime}\to\mathcal{R}^+\)是兩個參數化的函數近似器。因此，參數向量可以分為兩部分\(\theta=[\theta_\mu,\theta_\sigma]^\top\)，同時特徵向量也分為兩部分\(x=[x_\mu,x_\sigma]\)，均值部分可以直接使用線性函數近似，而標準差部分要求為正數，可以使用線性函數的指數形式近似

此時得分函數為

性能度量

有了策略函數，還要定義性能度量來衡量策略的好壞。一般將智慧體累積折扣獎勵的期望作為目標函數，用\(J(\theta)\)表示。利用相關策略的目標函數\(J(\theta)\)的梯度上升更新\(\theta\)，從而最大化獎勵的期望：

在幕式任務和連續任務這兩種不同的情況下，性能度量的定義是不同的：

1. 起始價值(start value)

針對幕式任務，將性能度量定義為該幕起始狀態的價值，即

其中，\(v_{\pi_\theta}\)是執行策略\(\pi_\theta\)的真實的價值函數。適用於能夠產生完整經驗軌跡的環境，即從狀態\(s_0\)開始，以一定的概率分布達到終止狀態時序段內，智慧體獲得的累積獎勵。

2. 平均價值(average value)

在連續任務中，智慧體沒有明確的起始狀態，可以基於智慧體在時序\(t\)的狀態分布，針對每個可能的狀態計算從\(t\)開始持續與環境交互所能獲得的獎勵，並按其狀態的概率分布求和，即

其中，\(s\sim d_{\pi_\theta}(s)\)表示狀態\(s\)服從根據策略\(\pi_\theta\)生成的馬爾科夫鏈的狀態分布。

3. 每時序平均獎勵(average reward per time-step)

平均價值使用時序\(t\)下狀態的平均價值，而每個時序的平均獎勵使用時序\(t\)的狀態下所有動作的期望，即在時序\(t\)先計算出智慧體所有狀態的可能性，然後計算出在每一種狀態下採取所有可能動作獲得的即時獎勵，並按其對應的概率求和，即

其中，\(d_{\pi_\theta}(s)=\lim_{t\to\infty}\Pr\{s_t=s|s_0,\pi_\theta\}\)是策略\(\pi_\theta\)下狀態的穩態分布，\(s_0\)獨立於所有策略，\(r_{s,a}\)是狀態\(s\)下執行動作\(a\)得到的即時獎勵。它實際上是單步MDPs，也就是從狀態\(s\sim d(s)\)開始，根據策略\(\pi\)執行動作\(a\)，此時得到了一個獎勵值\(r\)，完成了一個時序後結束。

策略梯度定理

已經給出了策略函數和性能度量，但通過調整策略參數\(\theta\)來保證性能得到改善仍存在疑點，主要在於策略的性能既依賴於動作的選擇，也依賴於動作選擇時所處的狀態分布，而策略\(\pi(a|s)\)的定義是已知狀態\(s\)下動作\(a\)的概率，因此策略對狀態分布的影響未知。這裡就引出了策略梯度定理(policy gradient theorem)。

Policy Gradient Theroem
對任何可微策略\(\pi(a|s,\theta)\)，任意目標函數\(J(\theta)\)的梯度都可以表示為

\begin{aligned}
\triangledown J(\theta)
&\propto\sum_s\mu(s)\sum_a\triangledown\pi(a|s,\theta)q_\pi(s,a) \
&=\mathbb{E}\pi \bigg[\sum_a q\pi (S_t,a) \triangledown \pi(a|S_t,\theta)\bigg] \
&=\mathbb{E}\pi \bigg[\sum_a \pi(a|S_t,\theta)q\pi(S_t,a)\frac{\triangledown \pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}\bigg] \
&(A_t\sim\pi，因此\sum_a \pi(a|S_t,\theta)q_\pi(S_t,a)可以用q_\pi(S_t,A_t)代替)\
&=\mathbb{E}\pi\bigg[q\pi(S_t,A_t)\frac{\triangledown \pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}\bigg]\
&(根據q_\pi的定義，q_\pi(S_t,A_t)=\mathbb{E}\pi[G_t|S_t,A_t]，G_t是回報值)\
&=\mathbb{E}\pi\bigg[G_t\frac{\triangledown \pi(A_t|S_t,\theta)}{\pi(A_t|S_t,\theta)}\bigg]
\end{aligned}

\begin{aligned}
\theta_{t+1}
&\leftarrow \theta_t+\alpha G_t\frac{\triangledown \pi(A_t|S_t,\theta_t)}{\pi(A_t|S_t,\theta_t)} \
&\leftarrow\theta_t+\alpha G_t\triangledown \ln \pi(A_t|S_t,\theta_t) \
\end{aligned}

基準線\(b(s)\)不會影響策略的梯度，因為梯度方向的單位向量之和為0，即\(\triangledown_\theta \sum_a\pi(a|s,\theta)=\triangledown_\theta 1=0\)。通常可以將狀態價值函數近似\(\hat{v}(S_t,w)\)，\(w\in\mathbb{R}^m\)作為基準線，改良後的REINFORCE演算法參數更新為

Append

策略梯度定理(證明)

1. 幕式情況

其中，\(\Pr(s\to x,k,\pi)\)表示在策略\(\pi\)下的\(k\)步內，狀態\(s\)轉移到狀態\(x\)的概率。

2. 連續情況

由上可以得到

目標函數的梯度為

References

Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction (Second Edition). 2018.
Csaba Szepesvári. Algorithms for Reinforcement Learning. 2009.
Richard S. Sutton et al. Policy Gradient Methods for Reinforcement Learning with Function Approximation. 2000.
Course: UCL Reinforcement Learning Course (by David Silver)