兩類AC的改進算法

整理了動手學強化學習的學習內容

1. TRPO 算法（Trust Region Policy Optimization）

1.1. 前沿

策略梯度算法即沿著梯度方向迭代更新策略參數(shù) 。但是這種算法有一個明顯的缺點：當策略網(wǎng)絡沿著策略梯度更新參數(shù)，可能由于步長太長，策略突然顯著變差，進而影響訓練效果。

針對以上問題，考慮在更新時找到一塊信任區(qū)域（trust region），在這個區(qū)域上更新策略時能夠得到某種策略性能的安全性保證，這就是信任區(qū)域策略優(yōu)化（trust region policy optimization，TRPO）算法的主要思想。

1.2. 一些推導

首先，最常規(guī)的動作價值函數(shù)，狀態(tài)價值函數(shù)，優(yōu)勢函數(shù)定義如下：
接著，一個策略的好壞可以期望折扣獎勵$J({\pi }_{\theta })$表示：
$$J({\pi }_{\theta })=E_{s_0,a_0,...}[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)]=E_{s_0}[V^{{\pi }_{\theta }}(s_0)]$$

其中，$s_0～{\rho }_0(s_0)$，$a_t～{\pi }_{\theta }(a_t|s_t)$，$a_{t+1}～P(s_{t+1}|s_t,a_t)$。
由于初始狀態(tài)$s_0$的分布${\rho }_0$和策略無關，因此上述策略${\pi }_{\theta }$下的優(yōu)化目標$J({\pi }_{\theta })$可以寫成在新策略${\pi }_{{\theta }^{\prime }}$的期望形式：
從而，推導新舊策略的目標函數(shù)之間的差距：
將時序差分殘差定義為優(yōu)勢函數(shù)A：
所以只要我們能找到一個新策略，使得$J({\theta }^{\prime })?J(\theta )>=0$，就能保證策略性能單調遞增。

但是直接求解該式是非常困難的，因為${\pi }_{{\theta }^{\prime }}$是我們需要求解的策略，但我們又要用它來收集樣本。把所有可能的新策略都拿來收集數(shù)據(jù)，然后判斷哪個策略滿足上述條件的做法顯然是不現(xiàn)實的。

于是 TRPO 做了一步近似操作，對狀態(tài)訪問分布進行了相應處理。具體而言，忽略兩個策略之間的狀態(tài)訪問分布變化，直接采用舊的策略的狀態(tài)分布，定義如下替代優(yōu)化目標：
當新舊策略非常接近時，狀態(tài)訪問分布變化很小，這么近似是合理的。其中，動作仍然用新策略${\pi }_{{\theta }^{\prime }}$采樣得到，我們可以用重要性采樣對動作分布進行處理：
為了保證新舊策略足夠接近，TRPO 使用了KL散度來衡量策略之間的距離，并給出了整體的優(yōu)化公式：
這里的不等式約束定義了策略空間中的一個 KL 球，被稱為信任區(qū)域。在這個區(qū)域中，可以認為當前學習策略和環(huán)境交互的狀態(tài)分布與上一輪策略最后采樣的狀態(tài)分布一致，進而可以基于一步行動的重要性采樣方法使當前學習策略穩(wěn)定提升。

1.3. 近似求解

直接求解上式帶約束的優(yōu)化問題比較麻煩，TRPO 在其具體實現(xiàn)中做了一步近似操作來快速求解。
對目標函數(shù)和約束在${\theta }_k$進行泰勒展開，分別用 1 階、2 階進行近似：
于是我們的優(yōu)化目標變成了：
此時，我們可以用KKT條件直接導出上述問題的解：

1.4. 共軛梯度

一般來說，用神經(jīng)網(wǎng)絡表示的策略函數(shù)的參數(shù)數(shù)量都是成千上萬的，計算和存儲黑塞矩陣的逆矩陣會耗費大量的內存資源和時間。

TRPO 通過共軛梯度法（conjugate gradient method）回避了這個問題，它的核心思想是直接計算$x=H^{?1}g$，$x$即參數(shù)更新方向。假設滿足 KL距離約束的參數(shù)更新時的最大步長為$\beta ={\theta }^{\prime }?\theta$。
于是，根據(jù) KL 距離約束條件$\frac{1}{2}({\theta }^{\prime }?{\theta }_k{)}^{T}H({\theta }^{\prime }?{\theta }_k)<=\delta$，有$\frac{1}{2}(\beta x{)}^{T}H(\beta x)=\delta$。求解$\beta$，得到$\beta =\sqrt{\frac{2\delta }{x^{T}Hx}}$。因此，此時參數(shù)更新方式為
${\theta }_{k+1}={\theta }_k+\sqrt{\frac{2\delta }{x^{T}Hx}}x$，
因此，只要可以直接計算$x=H^{?1}g$，就可以根據(jù)該式更新參數(shù)，問題轉化為解$Hx=g$。實際上$H$為對稱正定矩陣，所以我們可以使用共軛梯度法來求解。
共軛梯度法的具體流程如下：
在共軛梯度運算過程中，直接計算${\alpha }_k$和$r_{k+1}$需要計算和存儲海森矩陣$H$。為了避免這種大矩陣的出現(xiàn)，我們只計算$Hx$向量，而不直接計算和存儲$H$矩陣。這樣做比較容易，因為對于任意的列向量$v$，容易驗證：
即先用梯度和向量$v$點乘后計算梯度。

    def hessian_matrix_vector_product(self, states, old_action_dists, vector):# 計算黑塞矩陣和一個向量的乘積new_action_dists = torch.distributions.Categorical(self.actor(states))kl = torch.mean(torch.distributions.kl.kl_divergence(old_action_dists,new_action_dists))  # 計算平均KL距離kl_grad = torch.autograd.grad(kl,self.actor.parameters(),create_graph=True)kl_grad_vector = torch.cat([grad.view(-1) for grad in kl_grad])# KL距離的梯度先和向量進行點積運算kl_grad_vector_product = torch.dot(kl_grad_vector, vector)grad2 = torch.autograd.grad(kl_grad_vector_product,self.actor.parameters())grad2_vector = torch.cat([grad.view(-1) for grad in grad2])return grad2_vectordef conjugate_gradient(self, grad, states, old_action_dists):  # 共軛梯度法求解方程x = torch.zeros_like(grad)r = grad.clone()p = grad.clone()rdotr = torch.dot(r, r)for i in range(10):  # 共軛梯度主循環(huán)Hp = self.hessian_matrix_vector_product(states, old_action_dists,p)alpha = rdotr / torch.dot(p, Hp)x += alpha * pr -= alpha * Hpnew_rdotr = torch.dot(r, r)if new_rdotr < 1e-10:breakbeta = new_rdotr / rdotrp = r + beta * prdotr = new_rdotrreturn x

1.5. 線性搜索

由于 TRPO 算法用到了泰勒展開的 1 階和 2 階近似，這并非精準求解，因此，$\theta$可能未必比${\theta }_k$好，或未必能滿足 KL 散度限制。TRPO 在每次迭代的最后進行一次線性搜索，以確保找到滿足條件。具體來說，就是找到一個最小的非負整數(shù)$i$，使得按照
$${\theta }_{k+1}={\theta }_k+{\alpha }^i\sqrt{\frac{2\delta }{x^{T}Hx}}x$$

求出的${\theta }_{k+1}$依然滿足最初的 KL 散度限制，并且確實能夠提升目標函數(shù)，這KaTeX parse error: Undefined control sequence: \apha at position 1: \?a?p?h?a? ?\in (0,1)其中是一個決定線性搜索長度的超參數(shù)。

1.6. 總結

至此，我們已經(jīng)基本上清楚了 TRPO 算法的大致過程，它具體的算法流程如下：

2. PPO 算法（Trust Region Policy Optimization）

2.1. 前沿

PPO 算法作為TRPO算法的改進版，但是其算法實現(xiàn)更加簡單。并且大量的實驗結果表明，與TRPO相比，PPO能學習得一樣好（甚至更快），這使得PPO成為非常流行的強化學習算法。如果我們想要嘗試在一個新的環(huán)境中使用強化學習算法，那么 PPO 就屬于可以首先嘗試的算法。

PPO 的優(yōu)化目標與 TRPO 相同，但 PPO用了一些相對簡單的方法來求解（TRPO 使用泰勒展開近似、共軛梯度、線性搜索等方法直接求解）。具體來說，PPO 有兩種形式，一是 PPO-懲罰，二是 PPO-截斷，接下來對這兩種形式進行介紹。

2.2. PPO-懲罰

PPO-Penalty用拉格朗日乘數(shù)法直接將 KL 散度的限制放進了目標函數(shù)中，這就變成了一個無約束的優(yōu)化問題，在迭代的過程中不斷更新 KL 散度前的系數(shù)。即：
令$d_k=D_{KL}^{{\pi }_{{\theta }_k}}({\pi }_{{\theta }_k},{\pi }_{\theta })$，$\beta$的更新規(guī)則如下：

1. 如果$d_k<\delta /1.5$，那么${\beta }_{k+1}={\beta }_k/2$
2. 如果$d_k>\delta \times 1.5$，那么${\beta }_{k+1}={\beta }_k\times 2$
3. 否則${\beta }_{k+1}={\beta }_k$

其中，$\delta$是事先設定的一個超參數(shù)，用于限制學習策略和之前一輪策略的差距。

2.3 PPO-截斷

PPO的另一種形式 PPO-截斷（PPO-Clip） 更加直接，它在目標函數(shù)中進行限制，以保證新的參數(shù)和舊的參數(shù)的差距不會太大，即:
其中$clip(x,l,r):=max(min(x,r),l)$ ，即把$x$限制在$[l,r]$內。上式中$?$是一個超參數(shù)，表示進行截斷（clip）的范圍。

如果$A^{{\pi }_{{\theta }_k}}(s,a)>0$，說明這個動作的價值高于平均，最大化這個式子會增大$\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_k}(a|s)}$，但不會讓其超過$1+?$。反之，如果$A^{{\pi }_{{\theta }_k}}(s,a)<0$，最大化這個式子會減小$\frac{{\pi }_{\theta }(a|s)}{{\pi }_{{\theta }_k}(a|s)}$，但不會讓其超過$1??$。如下圖所示。

代碼

最后，兩個算法的代碼可參考GitHub，Good Night!