Proximal Policy Optimization （PPO）

作者：由春天裡的小草發表于攝影時間：2019-04-16

Proximal Policy Optimization，簡稱PPO，即近端策略最佳化，是對Policy Graident，即策略梯度的一種改進演算法。Importce Sampling的方法，將Policy Gradient中On-policy的訓練過程轉化為Off-policy，即從線上學習轉化為離線學習。

Policy Gradient是一種基於策略迭代的強化學習演算法。

Policy Gradient直接地透過取樣狀態、動作、獎勵，然後期望直接最大化獎勵的期望。

當取樣足夠充分時，獎勵的期望可以近似為N回合的獎勵的平均值：

$\bar{R}{\theta} = \sum_{\tau} R(\tau) P(\tau \lvert \theta) \approx \frac{1}{N} \sum^{N}_{n=1} R(\tau^{n})$

上式中的第n回合的獎勵值之和

$R(\tau^n)$

被定義為如下形式：

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

PolicyGradient （策略梯度）：

設計一個網路，其輸入是state，輸出是對應各個action的機率，並策略梯度（PolicyGradient）進行迭代訓練。

我們首先定義

$\tau$

為一次回合的跡：

$\tau = {s_1, a_1, r_1, \cdots, s_T, a_T, r_T } \$

$R(\tau)$

是這次跡的獎勵值之和：

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

直觀地，我們希望最大化：

$\bar{R}_{\theta} = \sum_{\tau} R(\tau) P(\tau \lvert \theta) \approx \frac{1}{N} \sum^{N}_{n=1} R(\tau^{n})$

則首先對

$\bar{R}_{\theta}$

求梯度：

$\begin{align} \nabla \bar{R}_{\theta} &= \sum_{\tau} R(\tau) \nabla P(\tau \lvert \theta) \\ &= \sum_{\tau} R(\tau) P(\tau \lvert \theta) \cdot \frac{\nabla P(\tau \lvert \theta)}{P(\tau \lvert \theta)} \\ &= \sum_{\tau} R(\tau) P(\tau \lvert \theta) \cdot \nabla \log P(\tau \lvert \theta) \\ &\approx \frac{1}{N} \sum^{N}_{n=1} R(\tau^n) \cdot \nabla \log P(\tau^n \lvert \theta) \end{align}$

而對於

$P(\tau^n \lvert \theta)$

，則可以展開成以下形式：

$\begin{align} p(\tau^n \lvert \theta) &= p(s_1)p(a_1 \lvert s_1, \theta)p(r_1, s_2 \lvert s_1, a_1)p(a_2 \lvert s_2, \theta) \cdots p(a_t \lvert s_t, \theta)p(r_t, s_{t+1} \lvert s_t, a_t) \\ &= p(s_1) \prod_{t} p(a_t \lvert s_t, \theta)p(r_t, s_{t+1} \lvert s_t, a_t) \end{align}$

將上式帶入

$\log P(\tau^n \lvert \theta)$

中：

$\begin{align} \nabla \log P(\tau^n \lvert \theta) &= \nabla \log \left (p(s_1) \prod_{t} p(a_t \lvert s_t, \theta)p(r_t, s_{t+1} \lvert s_t, a_t) \right) \\ &= \nabla \log p(s_1) + \sum^{T}_{t=1} \nabla \log p(a_t \lvert s_t, \theta) + \sum^{T}_{t=1} \nabla p(r_t, s_{t+1} \lvert s_t, a_t) \\ &= \sum^{T}_{t=1} \nabla \log p(a_t \lvert s_t, \theta) \end{align}$

最終

$\nabla \bar{R}_{\theta}$

將改寫為：

$\begin{align} \nabla \bar{R}_{\theta} &\approx \frac{1}{N} \sum^{1}_{N} R(\tau^n) \cdot \nabla \log P(\tau^n \lvert \theta) \\ &= \frac{1}{N} \sum^{N}_{n=1} R(\tau^n) \sum^{T_n}_{t=1} \nabla \log p(a_t \lvert s_t, \theta) \\ &= \frac{1}{N} \sum^{N}_{n=1} \sum^{T_n}_{t=1} R(\tau^n) \nabla \log p(a_t \lvert s_t, \theta) \end{align}$

本質上是最小化N回合取樣出的action與網路輸出的action的交叉熵的基礎上乘以

$R(\tau^n)$

：

$- \sum^{N}_{n=1} R(\tau^n) \cdot a_i \log p_i$

需要注意的是，

$R(\tau^n)$

對於不同的問題計算方式是不同的，在CartPole中，我們更關注回合開始時的獎勵，因為他們直接影響了我們是否有機會進行更可能多的動作，所以在這個問題中，

$R(\tau^n)$

是這樣計算的：

# Copy r_buffer

r_buffer = self。r_buffer

# Init r_tau

r_tau = 0

# Calculate r_tau

for index in reversed（range（0， len（r_buffer）））：

r_tau = r_tau * self。gamma + r_buffer［index］

$R(\tau^n)$

的正負直接決定了梯度下降的方向，對於訓練過程的收斂至關重要。

Policy Gradient文章中，已經詳細地推導了關於

$\nabla \bar{R}_{\theta}$

的計算方法，所以在這裡的具體推導過程將略過，最後關於其計算公式將有如下形式：

$\nabla \bar{R}_{\theta} = \frac{1}{N} \sum^{N}_{n=1} \sum^{T_n}_{t=1} R(\tau^n) \nabla \log p(a_t \lvert s_t, \theta)$

本質上是最小化N回合取樣出的動作與網路輸出的動作的交叉熵的基礎上乘以#FormatImgID_24#，獎勵值給了梯度下降的方向，推匯出了#FormatImgID_25#，其實就已經可以根據梯度下降法反向傳播改進網路進行訓練了，但是通常情況下我們會根據具體的問題對其做一些修正。

Actor-Critic Model

第一個改進：需要針對每一個狀態、動作元組對

$R(\tau^n)$

進行如下替換：

$R(\tau^n) \rightarrow \sum^{T_n}_{t=t^{\prime}} \gamma^{t} r^{n}_{t}$

這樣原來的梯度公式將會被改寫為以下形式：

$\nabla \bar{R}_{\theta} = \frac{1}{N} \sum^{N}_{n=1} \sum^{T_n}_{t=1} \sum^{T_n}_{t=t^{\prime}} \gamma^{t} r^{n}_{t} \nabla \log p(a_t \lvert s_t, \theta)$

但是這樣還存在一個稱之為Overestimate，即過估計的問題。因為在實際情況中，我們的狀態-動作取樣通常是不充分的，這會導致一些一些動作或者狀態幾乎不會被取樣，這樣在進行梯度下降訓練網路時，在這些狀態對應的動作將可能被極大的放大或者縮小。由於輸出層是soft-max，這些機率會此消彼長，這顯然不是我們想看到的。所以我們需要做第二個改進：引入Baseline，通常可能是一個待調整的常超引數，或者Critic，通常是一個待訓練的網路。

如果引入的是一個Critic，這樣的模型將會被稱之為Actor-Critic Model，即演員-評論家模型，而N回合平均獎勵值的梯度將會被改寫為以下形式：

$\nabla \bar{R}_{\theta} = \frac{1}{N} \sum^{N}_{n=1} \sum^{T_n}_{t=1} A^{\theta}(a_t \lvert s_t) \nabla \log p(a_t \lvert s_t, \theta)$

在一次訓練過程中，我們會按順序同時更新這兩個網路，目前這樣的模型已經被廣泛使用，並在實驗上證明了較好的效果。

Importance Sampling

在前面提到，PPO的一個核心改進是將Policy Gradient中On-policy的訓練過程轉化為Off-policy，即從線上學習轉化為離線學習，這個轉化過程被稱之為Importance Sampling，是一種數學手段。如果我們有連續隨機變數X，它的機率密度函式記作

，則

的期望透過如下公式計算：

$E_{x \sim p} \left[ f(x) \right] = \int^{}_{} f(x)p(x)dx$

若我們對於連續隨機變數X，有另一個機率密度函式記作$q（x）$，那麼他們將有以下關係：

$E_{x \sim p} \left[ f(x) \right] = \int f(x) \cdot p(x)dx = \int f(x) \frac{p(x)}{q(x)} \cdot q(x) dx = E_{x \sim q} \left[ f(x) \frac{p(x)}{q(x)} \right]$

在上式中最右邊的項中，

$\frac{p(x)}{q(x)}$

被稱之為Importance Weight，類比到我們的問題，

是

$A^{\theta}(a_t \lvert s_t)$

，而

$\frac{p(x)}{q(x)}$

，則是

新老策略對於當前狀態採取當前動作對應的機率之比

，這句話比較費解，更加具體一些，對於小車倒立杆為例，動作是離散的，在網路的輸出是一組離散的機率分佈，以這個機率分佈選擇動作，這個動作在新老策略中，在當前狀態中都對應了一個機率值，

#FormatImgID_38# 即是他們的比值。

透過這一操作，在取樣充分的情況下，我們可以認為：

$E_{x \sim p} \left[ f(x) \right] = E_{x \sim q} \left[ f(x) \frac{p(x)}{q(x)} \right]$

Proximal Policy Optimization

最終我們將推匯出PPO，Importance Sampling將給我們將On-policy的訓練過程轉化為Off-policy以基礎，即我們可以透過老策略，即

進行充分取樣，然後改進新策略

，這個過程可以在一回合重複N次，而不再是1次，這樣大幅度減少了原始PG演算法線上學習進行取樣狀態-動作-獎勵元組對時間，同時保證了訓練效果，而N回合平均獎勵值的梯度也將被改寫為以下形式：

$\nabla \bar{R}_{\theta} = \frac{1}{N} \sum^{N}_{n=1} \sum^{T_n}_{t=1} \frac{p_{\theta}(a_t \lvert s_t)}{p_{\theta^{\prime}}(a_t \lvert s_t)} A^{\theta}(a_t \lvert s_t) \nabla \log p(a_t \lvert s_t, \theta)$

在實際訓練過程中，會有一個對

$\frac{p_{\theta}(a_t \lvert s_t)}{p_{\theta^{\prime}}(a_t \lvert s_t)}$

的clip的操作：

$clip(\frac{p_{\theta}(a_t \lvert s_t)}{p_{\theta^{\prime}}(a_t \lvert s_t)}, 1 - \epsilon, 1 + \epsilon)$

相當於一個正則化的操作，其中

$\epsilon$

是一個可調整的超引數，至此，PPO也就介紹完了。

Clipped 方法

除了上面的方法，其實還有一個更見簡潔的方法，既然想要控制更新的“步伐”，那乾脆控制

$\frac { \pi _ { \theta } \left( a _ { t } | s _ { t } \right) } { \pi _ { \theta _ { \mathrm { old } } } \left( a _ { t } | s _ { t } \right) }$

的大小。自然而然的就衍生出了下面clipped版本的“surrogate”函式：

首先令

$r _ { t } ( \theta ) = \frac { \pi _ { \theta } \left( a _ { t } | s _ { t } \right) } { \pi _ { \theta _ { \text { old } } } \left( a _ { t } | s _ { t } \right) }$

，然後令：

$\\L ^ { C L I P } ( \theta ) = \hat { \mathbb { E } } _ { t } \left[ \min \left( r _ { t } ( \theta ) \hat { A } _ { t } , \operatorname { clip } \left( r _ { t } ( \theta ) , 1 - \epsilon , 1 + \epsilon \right) \hat { A } _ { t } \right) \right]$